‫Few months ago.
‫Shopify's engineering have posted this interesting blog and brilliant in fact, talking about Top ten
‫tips for Building Resilient Payment System.
‫And I'll reference the blog for you guys and the description and the show notes.
‫But each of these ten tips is absolutely well crafted just for their use cases.
‫And in this particular episode, I'd like to focus on just one of these tips, because, frankly speaking,
‫each one of these steps is its own content.
‫It is on article no, and there is not much details, but boy, you can extract so much if you understand
‫the fundamentals.
‫So for this particular show, I'll focus on the database engineering aspects, specifically step number
‫six, which is to use item potency keys.
‫Right.
‫And how they.
‫Use a unique key that optimizes their inserts and select and queries for ident potency keys.
‫How about we jump into it?
‫All right.
‫So I talked about what I dub Potency is in another video.
‫Basically in a nutshell, either important request or other important backend is when you send a request
‫and this request is repeatable such that it doesn't change the state on the back end.
‫An example is a gift request.
‫A gift request by definition must be out important because if I do a read on a specific endpoint, if
‫I send that read twice, it doesn't matter.
‫Nothing changes on the backend.
‫Nothing should change.
‫Right?
‫Post, on the other hand, by definition is always not important, right?
‫Unless you make it to be.
‫If you post, if you insert a row repeating that insert is basically will change the state.
‫You don't want that.
‫It's not a desired behavior.
‫So if your endpoint says, okay, slash post and that creates a new entry, for example, let me fix
‫my mike.
‫And of course Shopify being a payment system, you want the ability to retry a payment without actually
‫causing a double spend.
‫You don't want to pay for something twice.
‫That's never fun, right?
‫And the opposite side for merchants you don't want if that happens, you don't want an accidental twice
‫or a refund.
‫Right.
‫So that's why I don't want is here as a critical concept.
‫I'm going to reference the video for you guys if you're interested to learn more about that item.
‫Potency is a very critical concept.
‫You have to build it yourself.
‫You have to configure your back in to be it important doesn't it's not for free.
‫That's why something called an absurd is a thing, right where you insert.
‫But if this exist, it becomes an update.
‫An absurd is an important concept.
‫So let's go ahead and read this blurb.
‫And in this particular blurb they talk about the importance of item potency, blah, blah, blah.
‫We know, right?
‫But here's the important thing that I am going to spend the most of the show about just talking about
‫that particular thing because.
‫It fascinated me the brilliance of Shopify engineering when it comes to database level tuning and data
‫modeling, which is very underrated.
‫All right.
‫Let's go ahead and read this.
‫An item potency key needs to be unique.
‫Well, that's that's important, right?
‫Because in this particular case, when they send a request, they add a key to uniquely identify payment
‫requests.
‫That's how you identify a payment or a request, Right.
‫If someone retried the same request with the same key that, you know, this is an actual retry.
‫That's whether happening from the user or from a proxy or for a reverse proxy or from API gateway,
‫some any middle layer that does that retried.
‫It doesn't matter.
‫We know that a retrial has happened right sometimes the user go back and then forward and then hit refresh
‫and then you get this message or do you want to resend it again?
‫You say yes.
‫And that sends the same technical request ID unless you went all the way and generated a brand new request
‫ID and physically wanted to pay.
‫Again, that's a different story.
‫But most of the the item potency key requests are sent within within a few seconds.
‫Right.
‫But what they do here is another point.
‫The key needs to be unique for the time.
‫We want the request to be retrievable, and that's a very critical use case for them.
‫They don't want the request to be retrievable infinitely.
‫Right.
‫If you send a request in 2018, a payment request in 2018, it's not going to live until 2022.
‫That doesn't make any sense.
‫It should live within, they estimate, a payment request to live within a 24 hour.
‫If you never made a payment within a 24 hour.
‫It was a failed, for example, on the back end for any reason.
‫We can try to retry it within this amount.
‫But if after that it says, hey, you know what, all bets are off, just do it again, right?
‫We will email you and say, hey, we could not retry that.
‫So typically 24 hours or less, that's say that's something you add as a as a designer, an architect.
‫We prefer using.
‫And here's the interesting part.
‫We prefer using an end universally that sounds like a typo, a universally unique lexis graphically
‫sortable identifier, or this thing that's called the U.
‫L IDs.
‫Right?
‫So this is called ul ID, right for these item potency keys instead of a random version for UID.
‫So if you don't know universal unique identifiers is or sometimes in Microsoft, we call them guedes
‫or globally unique identifier is a certain number of bits for gas.
‫Then 128 bits random mistaken 128 bits.
‫And these ones are guaranteed to be unique if you can generate them on the device.
‫And then you are 99% sure that's going to be unique, which is powerful concept.
‫Why do you want to use those?
‫You want to use those because you want the client to generate a unique ID as opposed of a database or
‫a back end to generate a sequential unique identifier.
‫Because you see, sequential identifiers are very powerful because sequence is beautiful in databases,
‫database is liked or like order things.
‫It likes things that are ordered because they can put them on the same page and you can query them and
‫you can they be tucked in nicely to each other and problems generating sequences of expensive because
‫you have to talk to the database to give you a unique sequence, right?
‫So there is a central point to generating like almost a central point of failure where we ask someone
‫to give us a unique ID versus the client just generates it and we know it's unique.
‫So that's why you UID is are very powerful.
‫The problem with the UID is or they are random or why does that why is that a problem?
‫Let's continue reading and continue and explain that a little bit more.
‫You will ID's contain a 48 bit stamp time stamps followed by 80 bit.
‫So I was right.
‫128 is that right?
‫Yeah.
‫128 if I can do math.
‫So.
‫Followed by 80 bits of random data.
‫So you'll ID's.
‫Ellie ID has some sort of an order to them.
‫So the first 48 bit has a time stamp and this time stamp.
‫Well, I.
‫Uh.
‫Will inject some sort of an order to these random UI IDs.
‫What is the benefit of these?
‫The time stamp allow u l IDs to be sorted, unlike random UI IDs which are not sorted.
‫Which works much better with ab3 data structure databases user for indexes in one high throughput system.
‫As Shopify, we've seen a 50% decrease in insert statement duration by switching from a UUID version
‫four to a u UL IDs for item keys.
‫And that's all what they say.
‫They don't tell you how.
‫They don't tell you why.
‫But I'm here to actually explain why this is the case and why it is faster because everything once you
‫understand how databases work and how the fundamentals of first principle of databases, this is just
‫like reading one plus one equal to.
‫So let's explain that.
‫Yeah.
‫So you see, you, you they're databases here.
‫They don't spell it out, but it's my SQL.
‫My SQL.
‫Primary keys are called a clustered index, which means that if you pick a primary key, that is, for
‫example, an integer.
‫A clustered primary key index is the table itself.
‫So what does that mean?
‫If you're integer as the primary key, then the index structure.
‫At the end there is the leaf pages where basically the pointers of where this integer points to is the
‫actual pages of data.
‫So if you have a row, one row to row three or four or five or six or seven, eight, nine, ten, these
‫are tucked in nicely together in a single page.
‫And not only there are the values, but every single column in the table is in the leaf page.
‫So if you search for the value of seven, right, you will find seven and you will find the row seven.
‫You find that all the columns that belongs to row seven.
‫That's how clustered indexes work.
‫Mm hmm.
‫And not only you find row seven, you get a four hour, find row eight, row nine, ten.
‫If 11 doesn't exist, you can find 12 next to it.
‫And not only just the values, 12 at ten and 12 and 13, you're going to find all the columns.
‫And because of this order, if you look up four rows seven, you will traverse the B three.
‫You find row seven and you're going to find any rows that is next to it.
‫So if you're doing range scans.
‫It is really beautiful because it's like how?
‫Give me all the rows between seven and 12.
‫Oh, that's that's a cheap query for B-plus trees.
‫And because we all searching on an indexed clustered index, not only we find it's almost like an index
‫only scan, it is an index only scan in this particular case.
‫All right.
‫That's nice.
‫We're reading an integer value.
‫Right?
‫And integer values are ordered in this particular clustered index.
‫So nice.
‫I get all the next values next to it.
‫But what if I'm inserting if you're inserting rows one and then.
‫Ten and then 1000.
‫They are not ordered and you're inserting 20,000 and then you turn around and insert.
‫Three.
‫The database must insert the row three in the same page that has the one right because it needs to order
‫them.
‫And not only it needs to order the index, it needs to order the whole row, right?
‫So the pages must be ordered and the.
‫That's the, that's the both the.
‫Advantages, disadvantages of a clustered index.
‫So now if we take if we move this into the primary key concept with a UUID, which is a random one,
‫you generate a UID, which is random, it's the table is empty, you get an insert in the first page,
‫create a brand new page, and you insert it right.
‫And then the second UID is also random.
‫Well, we don't have anything else.
‫We just have this one and we order it.
‫And this one happened to be right after it.
‫And then you keep inserting and inserting random, random goods.
‫Right.
‫And shifting the results as you find out as the table starts to grow, as you start inserting these
‫random codes, you will find yourself pointing to random pages.
‫Because guess what?
‫There is no order of the way you're inserting these things.
‫They are not ordered at all, so you need to find where this random goods should live based on their
‫order and it's exactly identical to inserting random integer values.
‫Identical.
‫So if you insert value one and then value thousand and then value of 3 million and then 7 million,
‫and then you turn around, insert two.
‫You need to find the page where two lives exactly next to the one.
‫Right.
‫So random insertion will just.
‫Be will cause random iOS.
‫So we will do an IO, fetch that page, get an memory, which is called also the buffer pool in my SQL
‫and then put it nicely in memory and let's just hope that this page will receive another write which
‫will never write, which will almost never receive another write because everything is random, right?
‫So you're going to get this page, you insert, insert that random word, and then you insert another
‫random UUID.
‫And guess what?
‫It's not on the same page.
‫You have to fetch the page that needs to live in.
‫You fetch another page, you write it and put it in memory.
‫So now we have two pages in memory and then another random, I guess it's not in these pages, it's
‫another page.
‫So you end up filling the buffer pool, which is the memory with pages that almost receive just one
‫or two writes.
‫That's bad because what happens is you will fill up your memory, the buffer pool, with pages that
‫are almost never used.
‫It's almost you going to read the entire data with with UID.
‫That's why it's bad.
‫That's why it's inserts or slow.
‫Right.
‫And I'm focusing on inserts because reads are also bad, but inserts are the worst because now inserts
‫you have to read the page and then write to the page and then write to the wall, which is the right
‫ahead lock and then flush the page with checkpoints.
‫So not only you slowed down rights because to receive a write, you have to read, put it in memory
‫and then right way.
‫And if it's not in memory, you have to go and do an IO.
‫So inserts are always almost causing an IO write.
‫And guess what?
‫What if the buffer pool fills up, which will.
‫And give it a few million requests, which Shopify easily do in an hour.
‫Right.
‫And then this buffer will fill up.
‫So what does that mean?
‫If it fills up, you can't even write.
‫Right.
‫So what does that mean?
‫You have to flush existing buffer pool pages back to disk.
‫That is a cost that is an expensive thing called check pointing.
‫And it's not exactly check pointing, but it's part of the writing.
‫Flushing back.
‫The changes that you do in the data pages to disk check pointing is something else.
‫But when you flush these things, you have to flush them to disk, persist them and.
‫And then now that we wrote, wrote these dirty pages to this, now we have some free memory on the buffer.
‫Let's read now that random page that this good has happened to live in and then insert it.
‫And you see this thrashing that the database keeps doing, which is awful.
‫So what those guys did was Shopify.
‫It is like they realized this big problem with the UID.
‫So it said, Hey, we still like you.
‫It is we, we like the uniqueness of the OIDs.
‫I'm not going to introduce a centralized system for to generate unique IDs.
‫That's just an I mean, you can but you created a bottleneck, right?
‫All these requests you can create a microservice that its sole job is to generate unique IDs that aren't
‫integers that works right?
‫And it will guarantee that no to services or or to request will get the same unique ID.
‫You can do that, but you have to serialize them, right?
‫And it becomes a bottleneck.
‫So they still want to use the UID, but they will use the UL ID which has a time stamp base.
‫So these there is, there is there is an order to this request and the order by time.
‫And it works perfectly for Shopify y when you generate a request, they are time based.
‫They are absolutely time based requests that are generated is definitely time based.
‫So if I generate a new request and I want to write it right in t zero, the next request is PT one.
‫Then this request is RT three.
‫The next request for these requests will definitely will be one after the other.
‫What does that mean?
‫And B three speak in.
‫B three speak.
‫If I my primary key is the UL IDs then.
‫I generate the t zero request.
‫Right.
‫And again, I'm saying t zero, but it's t zero followed by a random number, which the most important
‫part is the first part for the database.
‫Right.
‫It's always left to right.
‫And just like indexes combine indexes, compound indexes have to go left to right as well.
‫Right.
‫Same thing.
‫So now you generate request to zero request RT one request RT three RT 45 and all of these T zero Guess
‫what?
‫Go to this page.
‫And then where is T one goes right in the same page, which is exactly what you want.
‫So t zero first we'll say, okay, I don't have this page.
‫Let me fetch it from disk, put it there and then write to it.
‫And then t request t one comes in.
‫It's not random.
‫It's ordered.
‫So t one.
‫All the requests that comes in almost always goes to the tail.
‫Of the big three.
‫Right.
‫Which is.
‫Which is good.
‫But there's also another problem that I'm going to mention, that they don't talk about it here.
‫That page will receive many rights.
‫So t one will go to a t, three will go to a T for all of these budget pages will until it gets full
‫done.
‫Leave it.
‫It's almost impossible.
‫Improbable.
‫Let's say that another request in in the past will just come in out of the blue and then.
‫Fitch is a page from the past and you cannot insert a request in the past.
‫Right?
‫All requests will come real time.
‫And I guess I suppose there is there might be a bug.
‫I will call it a bug in the client where the client generates the UL ID, but it got disconnected,
‫right?
‫And then later it was connected after an hour and then use that ID.
‫That's fine, right?
‫That's fine.
‫Sure.
‫That is kind of an anomaly where an old request ID with an old timestamp will pull an old page to write
‫to it because we have moved on already.
‫But the goal here is all the request that comes in will be nicely ordered.
‫The buffer pool will almost have one or two or three pages.
‫Right.
‫And we'll get right to the tail.
‫Always right to the tail.
‫So right or fast.
‫How about reads?
‫Reads are also fast.
‫Because guess what?
‫If you're going to read a request, chances that this request you ID that you just generated is just
‫you just generated it.
‫So if you just generated it, chances that it is almost always in memory, it's a dirty page, right?
‫So yeah, you're going to read this page that is effectively it's committed in the wall, but it's still
‫in the memory so you're going to read it from.
‫So it's already there.
‫So it reads out fast as opposed to random your IDs, which you just random.
‫They have no absolutely no order to them.
‫And then you're going to query that and then you have to find the page where it lives and then pull
‫it in memory and just hope that someone else will ask for the same page.
‫But what, because of their unique use case.
‫So before, because of this request, the order of the request and the order they are come in and the
‫fact that it's 24 hours or less, they built this so tight such that this works perfectly for them,
‫other IDs work perfectly for them.
‫What's the problem here?
‫The other problem is a little thing called the mutex and.
‫Suppose it's an operating system thing.
‫It's a computer science thing where it's a lock.
‫I talk about pages in my medium and I'm like, I'm making another video about it.
‫Just talk about database pages.
‫Very critical concept to understand whether it's not equal graph doesn't matter.
‫Every database has a concept of a page and.
‫It's different from the file system page and it's different from the PSD page has nothing to do with
‫each other, and page is nothing but an in-memory structure.
‫And if you have multithreading in your database, which almost you do, then multiple threads will try
‫to write on the same page.
‫Right.
‫And if you don't do it correctly, you can corrupt your page, write, raise conditions and all.
‫So unless you build your structure, set that such that you can have two threads right in the same memory
‫location, which is very hard, you have to acquire something called a mutex.
‫And I think if I'm mistaken in my SQL, they call them latches or there might be SQL Server I can't
‫remember.
‫So you have to latch on the page.
‫If a thread wants to write something, it latches to it and then writes and then an UN latches.
‫All right, I'll release the mutex.
‫Right.
‫And that constant if you're writing to the tale always, if you're like there's like thousands of requests
‫always competing for the tail, you're going to start seeing serialization, right?
‫As as as threads being serialized.
‫So you'll see slight slow down for that particular problem.
‫But it's not as bad as having the buffer pool filled up.
‫I think they already realize this problem where this latching happen in the tail.
‫I don't know if there's a solution to it, to be honest.
‫Right.
‫I guess solutions to me having a little bit of randomness to it.
‫But for for this particular case.
‫Yeah.
‫Maybe make the make the page size a little bit smaller so that you have a little bit more pages.
‫But I don't know.
‫So that if you have a large page size, I mean, because my SQL, A.B. is 16 and I have no idea if they
‫configure that and changed it.
‫16 KB So Skip can fill up really quick with with UI IDs.
‫UL IDs, I suppose.
‫And I have no idea what their table structure looks like.
‫But yeah, it's, it's interesting looking at all these things, right?
‫They actually took full advantage of ul ID the first time I've seen a full advantage of you all IDs
‫right now we're going to be careful with this.
‫Right?
‫So now we know there is something called ul ID, a new UID is.
‫Is usually you.
‫You.
‫But what I want to say is.
‫Don't just use your ID because it's a new thing.
‫I think you still need to.
‫Fix, make sure that it's your use case actually fits it right nicely.
‫Let's take an example.
‫So let's say I want to make a URL shorter such that I don't want the user to select anything.
‫Right.
‫I just wanted.
‫To generate a unique short URL based on the utility.
‫So when you tell me, Hey, this is wrong, you ought to make it short, I'll generate a utility for
‫you.
‫And based on that, this is now the short order.
‫This is if you use normal random UI IDs.
‫Inserts, right?
‫A fleet of people will be creating short URLs.
‫Right.
‫And in that particular case, randomness will hurt performance, especially in write performance.
‫If you use UL IDs, then you can control the inserts because you know that people who generate the short
‫yardage will be generated in game one after the other.
‫You're going to get a nice boost and insert performance with your slides generating short URLs.
‫Again, if you have like.
‫Many, many thousands of requests because this early will come in and.
‫And the beauty here is actually you can either have the client generate them or have the database generate
‫them.
‫And if you do that, all these keys that come in will, we'll look up where should they fit?
‫And most probably they're going to be ordered because right requests to generate new URLs will be in
‫order and as a result they can all fit in in the nice nicely tucked in page instead of randomly.
‫Right.
‫So that's nice.
‫But reads.
‫I don't think it's going to benefit you at all.
‫Just the same thing as you ID read.
‫Or will be so random.
‫You have absolutely no guarantee in this case to optimize read requests.
‫Unlike Shopify.
‫Shopify actually optimize both write and read because reading they will almost read requests that are
‫within this 24 hours.
‫There's no point reading request from seven years right ago.
‫Doesn't make sense because hey, we're building an item potency token.
‫Here you are.
‫Else you have no control over that.
‫Someone might request a URL that you have created a year ago.
‫Right.
‫And in that case, you're going to pull that page.
‫So with your ID unfortunately short, you are a short note.
‫This randomness, the use case is random and there is absolutely no way I can think of to make it better
‫for read request.
‫Time.
‫Because.
‫Because the the.
‫The use case is random.
‫The read request is random.
‫You have no control of you.
‫What users you are else visit.
‫Right.
‫So this is a result.
‫It's just a random and I have you have to configure your hardware based on that so just this is just
‫an understanding of this.
‫I don't don't think that you will you will fix everything for you.
‫Right.
‫So another disadvantage, if you will, is the size, right?
‫128.
‫Is huge.
‫And if you are using my SQL in particular, not necessarily postcodes, but my school will secondary
‫indexes.
‫Point back to the.
‫To the to the primary index key.
‫So if you are like indexing another field, that has nothing to do with Euclid.
‫Right.
‫But I don't know.
‫You're interested in the date on which this created, then this date will create an index and the values,
‫the keys is the date.
‫The values is what is the UID ID because that's how my SQL.
‫Actually cluster indexes work right as this is the same recently in MongoDB as well with clustered collections.
‫So if you're using MongoDB and you decided to turn on cluster collections on your collections, that
‫is identical to MySQL right now.
‫So the secondary indexes can blow it up.
‫Based on the size of the primary key.
‫So just just something a fruit of thought to understand these things.
‫What's the problem of large indexes like I have all the space in the world.
‫Well, you have all the space in the world, but you don't have all the all the memory in the world,
‫Right.
‫If you do, kudos.
‫But large indexes effectively need to be in memory to be effective in reading.
‫So if you have a large indexes with a lot of bloated secondary indexes and you have ten indexes can
‫really add up and it can slow down writes as well and reads mostly, but right guys.
‫So this is what I wanted to discuss.
‫Very interesting concept.
‫You alluded and I'll keep thinking more about it is like where can this break?
‫But most probably you will.
‫It is almost always better than you uid right.
‫But I'm yet to think about a case where.
‫Both are actually not a good idea.
‫Size is one of them, I suppose.
‫But yeah, but this is one of the first use cases that I saw that actually takes full advantage of your
‫IDs, Right.
‫Brilliantly, might I say.
‫So again, good article.
‫I'm going to reference it below the shownotes.
‫I hope you enjoy this video podcast.
‫See you in the next one.
‫You guys stay.
‫Awesome.
‫Goodbye.