L15: Distributed System Design Example (Unique ID)

To master the skill of designing distributed systems, it is helpful to learn about how existing systems were designed. In this video I talk through the thought process of designing a system to assign unique identifiers to transactions in a very large scale distributed database. We start by designing a function which can generate globally unique IDs (GUIDs). We then extend that solution to adapt to a new requirement: that the IDs be monotonically increasing over time.

Music: Getz Me to Brazil from the YouTube Audio Library.
===

[DistributedSystems]

Aarrrgh. The code in this video has a couple of bugs: (a) I'm missing a comma between arguments in one code snippet; and (b) the if() guarding the call to save_counter() should have a "!" so it is only called once every 1000 invocations... (Are there more bugs? Bring it on!)

[solomonxie]

Best GUID tutorial I can find! Been programming for years and finally get to really understand why people get struggle at this

[ycyish]

Awesome the way you walk through the thought process and various alternatives. Learning a lot here.

[siddharthabiswas]

One of the best introductory distributed systems video I have ever seen

[shir]

This is such a good, well-organized explanation! Thank you so much. After a couple of years not doing distributed systems but rather dealing with more monolith-focused problems (and leadership ones😉), I was looking for materials relevant for system design interviews, and this hits the nail on the head. Thanks again 🙏

[ahsannasir]

I'm a student studying full-time master's program on Distributed Systems in Dresden, Germany. I must say i really love your videos. Even though you've made just a few videos, but still these concepts are really the key to understanding a Distributed System. Thanks for the videos! i hope you keep 'em coming :))

[defenestrated]

This is why ULIDs are great. They have a timestamp in front, so sorting lexicographically sorts chronologically. They have a large random component, so they can be safely created in parallel without communication. And they also have a sequential component for rapid in-process generation of monotonic IDs.

It also uses a denser base32 encoding. Been using them in prod for over a year now and they are great!

[lechindianer]

To quote Joe Armstrong here as I've reached the conclusion: “Make it work, then make it beautiful, then if you really, really have to, make it fast. 90% of the time, if you make it beautiful, it will already be fast. So really, just make it beautiful!”

[qpmyvhy]

Could someone explain how the counter at 4:55 works?

Let's say the counter written on disk is 0.

We boot up, static int counter = 0 + 1000 = 1000.
(For sake of example, I'm ignoring computer_id)

We start giving out IDs: 1000, 1001, 1002

Then we crash. We haven't written anything to disk, because our counter hasn't reached 1000 yet.

We boot up again, static int counter = 0 + 1000 = 1000.

We start giving out IDs: 1000, 1001, 1002...

Aren't we giving out IDs we already gave out?

[tarunpahuja]

The way you are engaging with viewers, its wonderful. Nice content. Thank you.

[MohammadTariq]

You rocks sir..I have seen it thrice, but feels fresh every time I come here..Thank you!

[javiervera]

Hey great work on this videos. I really like your humor, it merges perfectly with the class, and makes it more fun to learn.

[kudoamv]

Wow, such a nice video for real Computer Science thinking.

[Trails]

Loved this video. Especially in the insight at the end. Simplicity sometimes really is the key.

[Kutlutr]

Great content and talk, I am glad to find this channel. Besides for this one I do not think that simple single server would fulfill the non-functional requirements of the need for such a system. In my case for instance, I need to build a solution for relatively high rps/tps, and I do not see it consistent to go for a vertical scaling as that usage of this service grows in time. I'd love to hear your comments on that @DistributedSystems. Thanks.

[akashagarwal]

also would having a counter even ensure atomicity, no right? since updating it everytime is a multi-instructions procedure right

[tqwewe]

Perhaps having an ID generator service which is replicated with the raft consensus?

[niksu]

totally nailed it learned a lot about brainstorming too

[akashagarwal]

cant we use some sort of random number gen? assuming if there exists a legit non pseudo generator actually IRL/practise?

[_sudipidus_]

3:03 Time always doesn't go monotonically forward on computers (mind blown) Yes I had some idea about NTP but never thought of it this way