What are the tradeoffs when generating unique sequence numbers in a distributed and concurrent environment?

I am curious about the contraints and tradeoffs for generating unique sequence numbers in a distributed and concurrent environment.

Imagine this: I have a system where all it does is give back an unique sequence number every time you ask it. Here is an ideal spec for such a system (constraints):

• Stay up under high-load.
• Allow as many concurrent connections as possible.
• Distributed: spread load across multiple machines.
• Performance: run as fast as possible and have as much throughput as possible.
• Correctness: numbers generated must:
  1. not repeat.
  2. be unique per request (must have a way break ties if any two request happens at the exact same time).
  3. in (increasing) sequential order.
  4. have no gaps between requests: 1,2,3,4... (effectively a counter for total # requests)
• Fault tolerant: if one or more, or all machines went down, it could resume to the state before failure.

Obviously, this is an idealized spec and not all constraints can be satisfied fully. See CAP Theorem. 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.

Any references (papers, books, code) are welcome. I'd also like to keep a list of existing software (open source or not).

Software:

• Snowflake: a network service for generating unique ID numbers at high scale with some simple guarantees.
• keyspace: a publicly accessible, unique 128-bit ID generator, whose IDs can be used for any purpose
• RFC-4122 implementations exist in many languages. 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 ce开发者_运维技巧rtain versions of the spec, they include a time code portion that makes sorting possible, etc.

If you must be sequential (per machine) but can drop the gap/counter requirments look for an implementation of the Version 1 UUID as specified in RFC 4122.

If you're working in .NET and can eliminate the sequential and gap/counter requirements, just use System.Guids. They implement RFC 4122 Version 4 and are already unique (very low collision probability) across machines and requests. This could be easily implemented as a web service or just used locally.

Here's a high-level idea for an approach that may fulfill all the requirements, albeit with a significant caveat that may not match many use cases.

If you can tolerate having two sequence numbers - a logical one returned immediately; guaranteed unique and ordered but with gaps - and a separate physical one guaranteed to be in sequential order with no gaps and available a short while later - then the solution seems straightforward:

• One distributed system that can serve up a high resolution clock + machine id as the logical sequence number
• Stream all the logical sequence numbers into a separate distributed system that orders the logical sequence numbers and maps them to the physical sequence numbers.

The mapping from logical to physical can happen on-demand as soon as the second system is done with processing.