Databases
StackOverflow2013
Postsdbo
POWhat are the tradeoffs when generating unique sequence numbers in a distributed and concurrent environment?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhat are the tradeoffs when generating unique sequence numbers in a distributed and concurrent environment?
    text
    copied!<p>I am curious about the contraints and tradeoffs for generating unique sequence numbers in a distributed and concurrent environment.</p> <p>Imagine this: I have a system where all it does is give back an <strong>unique sequence number</strong> every time you ask it. Here is an ideal spec for such a system (constraints):</p> <ul> <li>Stay up under high-load.</li> <li>Allow as many concurrent connections as possible.</li> <li>Distributed: spread load across multiple machines.</li> <li>Performance: run as fast as possible and have as much throughput as possible.</li> <li>Correctness: numbers generated must: <ol> <li>not repeat.</li> <li>be unique per request (must have a way break ties if any two request happens at the exact same time).</li> <li>in (increasing) sequential order.</li> <li>have no gaps between requests: 1,2,3,4... (effectively a counter for total # requests)</li> </ol></li> <li>Fault tolerant: if one or more, or all machines went down, it could resume to the state before failure.</li> </ul> <p>Obviously, this is an idealized spec and not all constraints can be satisfied fully. See <a href="http://www.julianbrowne.com/article/viewer/brewers-cap-theorem" rel="nofollow noreferrer">CAP Theorem</a>. However, I would love to hear your analysis on various relaxation of the constraints. What type of problems will we left with and what algorithms would we use to solve the remaining problems. For example, if we rid of the counter constraint, then the problem becomes much easier: since gaps are allowed, we can just partition the numeric ranges and map them onto different machines.</p> <p>Any references (papers, books, code) are welcome. I'd also like to keep a list of existing software (open source or not). </p> <hr> <p><strong>Software</strong>:</p> <ul> <li><a href="http://github.com/twitter/snowflake" rel="nofollow noreferrer">Snowflake</a>: a network service for generating unique ID numbers at high scale with some simple guarantees.</li> <li><a href="http://karmanebula.com/the-keyspace-project/" rel="nofollow noreferrer">keyspace</a>: a publicly accessible, unique 128-bit ID generator, whose IDs can be used for any purpose</li> <li><a href="http://en.wikipedia.org/wiki/Universally_unique_identifier#Implementations" rel="nofollow noreferrer">RFC-4122 implementations exist in many languages</a>. The RFC spec is probably a really good base, as it prevents the need for any inter-system coordination, the UUIDs are 128-bit, and when using IDs from software implementing certain versions of the spec, they include a time code portion that makes sorting possible, etc.</li> </ul>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload