What are the tradeoffs in creating unique serial numbers in a distributed and parallel environment?

Question

I am curious what contraindications and trade-offs generate unique serial numbers in a distributed and parallel environment.

Imagine: I have a system where all she does is return a unique serial number every time you ask him. Here is the ideal specification for such a system (restrictions):

• Watch out for high loads.
• Allow as many concurrent connections as possible.
• Distributed: distributed loading across multiple machines.
• Productivity: Work as fast as possible with maximum throughput.
• Correctness: the generated numbers must:
  • not repeated.
  • be unique for each request (it should be able to break ties if any two requests occur at the same time).
  • in (ascending) sequential order.
  • have no spaces between requests: 1,2,3,4 ... (effectively counter for all # requests)
• Fault tolerance: if one or several or all of the machines are down, it can return to the state before the failure.

Obviously, this is an idealized specification, and not all restrictions can be fully implemented. See CAP Theorem . However, I would like to hear your analysis on the various relaxation of restrictions. What problems we will face and what algorithms we will use to solve the remaining problems. For example, if we get rid of the counter limit, the problem becomes much simpler: since valid spaces are resolved, we can simply split the number ranges and match them on different machines.

Any links (documents, books, code) are welcome. I would also like to keep a list of existing software (open source or not).

---

Software

• Snowflake : a network service for generating unique high-level identification numbers with some simple guarantees.
• keyspace : a publicly available unique 128-bit identifier generator whose identifiers can be used for any purpose
• RFC-4122 implementations exist in many languages . The RFC specification is probably a really good base, as it prevents the need for coordination between systems, 128-bit UUIDs, and when using software identifiers that implement certain versions of the specification, they include part of the time code that makes sorting possible, etc.

Answer 1

If you must be consistent (for each machine), but you can refuse the requirements for a space / counter, look at the implementation of Version 1 UUIDs, as specified in RFC 4122 .

If you work in .NET and can eliminate the sequence and space / counter requirements, just use System.Guid s. They implement RFC 4122 Version 4 and are already unique (very low chance of collision) for machines and requests. It can be easily implemented as a web service or simply used locally.

Answer 2

Here there is a high-level idea for an approach that can fulfill all the requirements, albeit with a significant caveat, which may not correspond to many use cases.

If you can tolerate the presence of two serial numbers - the logical one is returned immediately; guaranteed unique and orderly, but with gaps - and a separate physical one, guaranteed in a sequential order without spaces and available after a while - then the solution seems simple:

• One distributed system that can serve a high-resolution signal + machine identifier as a logical sequence number
• The flow of all numbers of a logical sequence into a separate distributed system that orders logical sequence numbers and compares them with the numbers of the physical sequence.

Mapping from logical to physical can occur on demand as soon as the second system is processed.