In this post I will not be solving a problem, instead I will be talking about something I learned by reading chapter 7 Design a Unique ID Generator in Distributed Systems in the book System Design Interview by Alex Wu.
The idea of a unique ID is a requirement in most distributed systems. In my case, some years ago I was developing a storage server and needed to name the objects of different types and sizes a client might wish to store and of course, at some later point in time, retrieve. The idea of a file system path did not make sense because it would be nearly impossible to keep the same immutable configuration among many distributed systems with a huge capacity.
If a client stored an object and a path in the file system, including machine name was returned, nothing could change with such a path during the lifetime of the object. A large portion of the objects we wished to store were permanent so that would add to the configuration of the disks.
Since capacity would grow into petabytes, and the capacity of disks is constantly increasing, we would have to reconfigure storage maintaining the same file paths. I am not sure if such an operation would be feasible. We could map the original file paths to newer ones in each system since with time, the hardware and logical configurations would change.
Many years ago I attended a DMIG (Data Management Interfaces Group) conference in Colorado. One of the speakers mentioned that in the future, a client anywhere in the world would present to this hypothetical system a unique object ID and the system would return the proper object. Such an idea was exactly what I had to architect, design, and implement for the distributed storage system I was working on.
In chapter 7 Alex Wu describes a design of a system to generate unique IDs. The design is based on something called Snowflake designed and implemented by Twitter in 2010. I picked the following reference in the book to the article Announcing Snowflake. If you are interested in the topic I suggest you spend a few minutes reading the entire article. It describes the problem, options, and solution (at least what Twitter came up with).
If you are interested in the Snowflake code by Twitter, you may find it in the GitHub repository at snowflake. There is a second version of the code at snowflake-2010. It is written in Scala and Apache Thrift.
Alex Wu describes the global ID on page 128 in his book. In a nutshell it contains the following:
Twitter Global ID
o zero bit ( 1 bit)
o timestamp (41 bits)
o datacenter ID ( 5 bits)
o machine ID ( 5 bits)
o sequence number (12 bits)
Total bits: 64 bits
The length of the global ID as required by Twitter, uses 64 bits which fits nicely in an unsigned long in the C / C++ programming language. I mention this because I used mainly C / C++ for my storage server implementation.
The sequence number used by Twitter contains 12 bits. Assuming that the clock tick in the timestamp has a granularity of 1 millisecond, a single server could generate up to 1’000 * 4’096 which is about 4M requests per second, which is well above the requirements stated in chapter 7 of the book.
In the storage server case, due to object longevity requirements, I decided to use 128 bits instead of 64.
Storage Server Global ID
o mac ( 48 bits)
o disk drive ID ( 32 bits)
o timeStamp ( 32 bits)
o sequence number ( 16 bits)
Total bits: 128 bits
Initially the timestamp started the layout and the sequence number ended it. The `mac` was included but the `disc drive ID` was not. Instead I had a location ID. After multiple discussions with multiple potential customers, most of which had a copy of the software to experiment with, I made the decision to modify and rearrange the fields. The final layout worked for what I was looking for while keeping the system administrators at the client sites happy.
GUIDGenUnique <<< sizeof(time_t): 4 line: 941
GUIDGenUnique <<< sizeof(__time32_t): 4 line: 942
GUIDGenUnique <<< sizeof(__time64_t): 8 line: 943
GUIDGenUnique <<< mac: 0x14feb5f0be5a size: 48 (bits) line: 1037
GUIDGenUnique <<< diskDriveID: 0x26e887b0 size: 32 (bits) line: 1082
GUIDGenUnique <<< timeStamp: 0x61f00b56 size: 32 (bits) line: 1098
GUIDGenUnique <<< sequenceNumber: 0x00003aa5 size: 16 (bits) line: 1134
UtilityFunctions <<< GUID ==>14FEB5F0BE5A26E887B061F00B563AA5<==
12345678901234567890123456789012
This screen capture illustrates the generation of a GUID (global ID) used by the distributed storage server. It has stored billions of objects in thousands of instances.
SELECT TOP 10 [GUID] FROM [sdmsql].[dbo].[BITFILE_TBL] GUID -------------------------------- 000c29e0aa9556d3a03c5ffca7669100 989096b15cdb1630436860006ba47700 005056891b354c11ed076009e73fd878 14FEB5F0BE5A26E887B06056095E765C 14FEB5F0BE5A26E887B060589E8BAE31 00505689D25C4C11ED076058B07B7FE7 14FEB5F0BE5A26E887B0605A10A4A797 14FEB5F0BE5A26E887B0605A10A4A798 14FEB5F0BE5A26E887B0605A10A4A799 14FEB5F0BE5A26E887B0605A10A4A79A (10 row(s) affected)
This is a query for some GUIDs (global unique IDs) on a test system. The storage servers use a distributed MS SQL Server or MySQL engine. Each instance only knows of the objects it stores locally. When a request comes to a storage node and it does not know about a GUID, it passes on the request to three peers. The first one that holds the object is used to satisfy the request. The process repeats if the object is not found. There is a TTL mechanism in built into the storage server to prevent loops.
One more thing, I designed the distributed unique ID generator in the late-1990s.
If interested in distributed systems I recommend the book by Alex Wu. It covers several design interview questions and at the end of each chapter he has references to extend the material covered.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John