Papers
Snowflake (Twitter, 2010) e Ticket Servers: Distributed Unique Primary Keys on the Cheap (Flickr, 2010)
Twitter (snowflake repository), Flickr Engineering · twitter/snowflake repository (tag snowflake-2010; blog announcement not verified) and code.flickr.com, 2010
The problem: unique IDs when a single database counter is not enough
When data is spread across many databases, each table's auto-increment column is no longer enough, because two different databases hand out the same number without knowing it. The Flickr post describes exactly this: Flickr shards MySQL (several databases, each with part of the data) and sometimes needs to migrate data between them; so primary keys must be unique across the whole site. In addition, each shard is a master-master pair, so uniqueness must also be guaranteed within the shard to avoid key collisions. The author says he would like to keep using auto-increment like everyone else, but MySQL does not guarantee uniqueness across physical and logical databases. The obvious question then arises: why not use GUIDs? According to the post, GUIDs are large and index poorly in MySQL; Flickr indexes everything it queries and only queries by indexes, so index size matters, and an index that does not fit in memory makes the database slow. The post also appreciates that sequential IDs make reporting and debugging easier. The problem, therefore, has three demands in tension: global uniqueness, small keys that behave well in indexes, and not depending on a single database for every insert. Snowflake's code, published by Twitter in 2010, addresses the same need in a different way, which we will see next.
The Snowflake idea: the ID itself carries what guarantees its uniqueness
In Snowflake, each generator creates IDs locally, without consulting other generators, because the ID is assembled from fields that make it distinct. From reading the 2010 IdWorker.scala code (the source used here; the text of the original announcement was not read), the 64-bit ID is composed, from the highest bit to the lowest, of: a timestamp in milliseconds counted from a custom epoch (the code fixes this epoch at 1288834974657 ms), a 5-bit datacenter ID, a 5-bit worker ID, and a 12-bit sequence number. The timestamp sits in the high bits, which is why IDs generated later tend to be numerically larger. The 12-bit sequence distinguishes IDs created by the same worker within the same millisecond; if it overflows (wraps back to zero), the code waits for the next millisecond before continuing. As long as each generator is given a distinct datacenter/worker pair (the code only validates that each field is between 0 and 31), two different machines do not produce the same ID. While the same generator is running, it does not repeat either: time advances or the sequence changes, and if the clock goes backwards the generator refuses to issue IDs (the last timestamp is kept only in memory, so this protection does not cover process restarts). Thus there is no coordination between generators at generation time. The split of the machine field into datacenter and worker is the one from the 2010 code; the archived repository states that the initial version used Apache Thrift and was replaced by an internal rewrite at Twitter.
The trade-off: uniqueness depends on the clock and the configuration
Generating IDs without coordination has a price: the scheme relies on the machine's clock. The 2010 code stores the last timestamp used and, if the current clock reads lower than it (the clock went backwards), the generator logs an error and refuses to issue IDs, throwing an exception that reports for how many milliseconds it is refusing; it only resumes working when the clock catches up with the last value used again. In other words, the system prefers to be unavailable on that machine rather than risk a duplicate ID. Within the same millisecond, uniqueness comes from the sequence counter; when it overflows, the generator busy-waits for the next millisecond. The second risk point is configuration: workerId and datacenterId are generator parameters, and the code only validates that they are in the range 0 to 31. Nothing in the code read prevents two instances from receiving the same pair, which would break the uniqueness argument; ensuring that each pair is distinct is the responsibility of whoever operates the system. Finer ordering guarantees (such as the precision of ordering across different machines) do not appear in the code read and are therefore not claimed here; what the code shows is that the numeric order follows the timestamp, and the timestamp comes from each machine's local clock.
The contrast: Flickr's ticket servers
Flickr chose the opposite path, deliberately simple and centralized. A ticket server is a dedicated database server with a single database containing tables such as Tickets32 and Tickets64. Tickets64 has an auto-increment id column and a one-character stub column with a unique key; the table holds a single row. To obtain a 64-bit global ID, the client runs a REPLACE INTO on that table and then reads LAST_INSERT_ID(). REPLACE works like INSERT, but deletes the old row when there is a primary or unique key conflict, which makes it possible to update a single row in place and still receive a new auto-incremented value. To avoid a single point of failure, Flickr runs two ticket servers that split the ID space into even and odd numbers (auto-increment-increment equal to 2, with offset 1 on one server and 2 on the other), and clients alternate between them in round robin, which balances load and tolerates one server being down. The author says that replicating between the two would be problematic at that volume and that locks would hurt performance. The two sides drift slightly out of sync (the author estimated, at the time, a few hundred thousand more odd objects), and that does no harm. There are also separate sequences for Photos, Accounts, OfflineTasks and Groups. The post calls the design inelegant, and it had been in production since January 2006. Compared with Snowflake, each ID costs a write to a central database (REPLACE INTO), in exchange for sequential, compact numbers; in the 2010 Snowflake the client also called a service (Thrift), but the generators did not coordinate with each other to generate the ID.
See the ideas at work
Practice the designs that use this paper in the System Design school.