‫Hash tables are effective for caching database joins even partitioning distributed databases sharding
‫sets to check if something is there or not.
‫It's very, very effective.
‫Even load balancing a lot of programming languages implement that in-house in natively in the language.
‫You can build these hash tables.
‫However, what I want to discuss in this episode of the back engineering show is the limitations and
‫the cost of using hash tables and, you know, things that we really don't think about.
‫It comes back to the leaky abstractions of a there is a black box, it's fast, let me use it.
‫But we don't understand how it works.
‫And when you don't understand how something works, you can get away with it.
‫But sometimes when it doesn't work, that's where you really get screwed.
‫And, and that's where really a good engineer is.
‫I identify him or herself from the other engineers.
‫How about we jump into it and discuss this all?
‫Come to the back of engineering show with your host Hussein.
‫Arsalan this is our laid back shell discussion podcast, kind of video audio format.
‫If you can listen on the podcast, if you're listening on Spotify and Apple Podcasts, Google Podcasts,
‫you can listen on that.
‫And this is basically I don't I don't include graphics or I don't include anything.
‫It's just a long form discussion about one topic and I try to go as deep as possible to my extent of
‫knowledge on this topic.
‫To tease apart this topic, today's topic is hash tables.
‫In order to discuss what hash tables are, we really need to understand what arrays are.
‫You might say, Hussein, I don't care.
‫I understand what arrays are.
‫And do you think I'm dumb?
‫I know what our arrays and I know how they work.
‫You'll be surprised that you.
‫We take a lot of things for granted are raises one of them the concept of array is a consecutive slots
‫of memory and this is the key word memory.
‫You cannot put an array on disk.
‫It doesn't make any sense.
‫Right.
‫Well, until Ultra Ram is a thing and we can do byte address ability in the disk.
‫But arrays are a property of the random access memory, you know, and the power of this is because
‫it is consecutive.
‫No matter how large the array is given the index.
‫I can go to the first node.
‫The first element of that Ray or I can go to the middle one or I can go to any to the last one or any
‫element in almost constant cost because of one.
‫As the computer science guys say, it's it's so fast because of this byte address ability, because
‫every index is associated with a memory address.
‫And to get the next one is literally just add one to the memory address and we can get there.
‫And if you ask the CPU to fetch a value of that, whatever the the element has, whether an integer
‫or a string or anything, you can immediately go there and fetch the value.
‫And that's the power of the array.
‫And hash tables are nothing but a glorified arrays, to be honest.
‫So you can ask the CPU to fetch a value from an array in memory by giving it its index.
‫From the index we're going to find the first address and going to add X amount of value to find that
‫particular index.
‫So so the cost is really is an addition plus the cost to go to the memory from the CPU.
‫Right?
‫So the first one is constant addition is cheap, it is done in the CPU itself.
‫The other cost to actually jump to the memory is really depending on your architecture of the CPU and
‫we can really dive deep into this.
‫This is probably another episode itself.
‫The cost to fetch a value from the RAM to the CPU really depends on the distance from where the CPU
‫lives.
‫The memory.
‫You know, in multicore architecture you have multiple CPUs and you have a single memory and they compete
‫in the memory.
‫Only one CPU can access the memory at a given time.
‫And so there's there's some sort of a competing computing going on.
‫So what happens is some in some certain architecture, there will be two memory locations.
‫Right?
‫And, and in each CPU access, it's local memory.
‫And that's obviously becomes faster, right?
‫Because there is no competing anymore.
‫No CPU is competing on the memory.
‫The problem with this is now this CPU sometimes might need to access a memory all over there that is
‫that is available that's closer to other CPU.
‫And and that's what it's called a numa architecture, the non-uniform memory access, you know, so
‫this can be slow and this is where guys like Apple is innovating to making the cost of access in the
‫moment as fast as possible by having everything into a single SOC chip, which is the MX one pro.
‫And then they just came up with an M1 ultra which fuses to M1, you know, SOC chips such that the cost
‫to to jump between different memory is negligible.
‫They just made this great, you know, design such that you don't as a programmer, you don't really
‫need to, oh, if my array is all over there and I really have to execute my code on this CPU, you
‫know, this is the normal aware programming.
‫Obviously, this is a little bit of discussion we can go into other day, but.
‫The cost is, you can't call it constant.
‫It's fast.
‫It can be faster than certain architecture.
‫So that's the array.
‫The array.
‫The problem with the array is it's a it's an integer based.
‫So zero one, two, three, four, five.
‫So if you're if you can have your key as that index, you one, right.
‫The problem is like how many applications where the key is actually an integer and it is actually this
‫this particular index that's almost very little.
‫Right.
‫This is where hashing table comes to use the concept of arrays in a very intelligent manner.
‫What do they do?
‫Second example.
‫So I have.
‫I don't know.
‫I have an ID student, you know, and I want to find their name.
‫Let's say this is a key value store, you know?
‫The ID is obviously a large number has nothing to do with the index.
‫So what you do is you want giving the ID.
‫I want immediately to find the name of the students.
‫So the value is the name, the the, the, the integer, the key as the ID of the student.
‫So given that ID student, what do you do as you build a hash table?
‫What do you do?
‫You effectively take the IDs and you create a hash of of them using a hash function that gives you a
‫garbage value, right?
‫So that if you hash the same value again, you're going to get the same hash.
‫Given that hash, you then take that value and then.
‫Calculate an index that points to an array.
‫That's the trick.
‫And.
‫The most easy way is to do a modular function.
‫So let's say your hash table size, your array size is ten, you know.
‫So if you calculate, if you give it this ID, you do modulo ten, you do a hash and then you do a modular
‫ten and you get a value between zero and nine.
‫And that's the power because you eventually have an index, you can immediately go to that array value
‫in that index and fetch the value, which is the name of the student in this particular case.
‫And that's the power of hash, hash tables.
‫And so now given an actual key, I can find the value using the power of array.
‫Well, you might say there are problems with this.
‫Obviously, it's like about collision.
‫You know, sometimes I might get to student IDs that maps to the same hash, which then maps to the
‫same index.
‫Well, that's your responsibility to solve.
‫And we're going to talk about this and the limitations option or portion of this video.
‫So now we know we no hash hash tables.
‫So now we understand hash table the idea of hashing something to get eventually get an index, which
‫we're going to use to point to an array which has our values.
‫So one popular use cases database joining.
‫So if you have two relations and you want to join these relations based on a foreign key, you know,
‫you're going to use the idea of.
‫Hashing hash tables.
‫Let's say you want to join the company table to the employee table where you have a company ID field.
‫So this employee belongs to this company, right?
‫So in order to join the two tables, you're going to pick one of the relations and you're going to create
‫a hash table and focus on this word.
‫Create a hash table.
‫The hash table doesn't exist.
‫You create it.
‫And there is a cost to creating a hash table.
‫So.
‫Usually in a joint you pick the smaller relation because creating hash table is expensive because you
‫get a loop through every single one and take their value, hash it and get the index and then go to
‫that array that you hopefully you have already pre allocated and then store the value for that index
‫in that particular array and you going to do the every thing for every single value.
‫So that's that means the hash table really has to have a fixed value to start with.
‫You start with Ayano I'm going to create I think this relation is around 1000, right?
‫It's going to increase 1000 if you know the size that's even better and you say okay, I want 1000,
‫a thousand array element and so, so you ask the ram, hey give me 1000 integer consecutive array values
‫and then you start building the hash tables and you fill all those thousand.
‫So the first value might go to index 999.
‫The second value might go to the index 78.
‫The third value might go to index zero and you start failing.
‫It's start filling this hash table.
‫So now once you build that hash table, you have a beautiful array in memory with with indexes, right?
‫But your hash values mean something.
‫There is a mapping between the hash, between the key to the hash, obviously, and then between the
‫hash to the index.
‫And that mapping is what's critical now.
‫Okay.
‫We have this hash table.
‫What do I do with it?
‫Now, you go to the other relation, whether whatever it is, is the company there or the employee,
‫whichever is larger in this case and you loop through it.
‫You pick the first one?
‫First entry of the company.
‫ID So at this point you don't really know the value is just picking one variable at a time.
‫Oh, this is company number 705.
‫Let's hash it and let's get the index by using a modulo right.
‫And then, oh, it's an index number 773.
‫Oh, let's go to the memory.
‫Right, let's go to the array.
‫So ask the CPA to fetch that value.
‫And then when you reach the value, you give that company complete row, which is the name of the company,
‫the whatever, how many employees, whatever you put the entire row that you need.
‫Obviously you don't put the entire row you put exactly based on the select query that joined, you know,
‫so that there is like a blob fields you don't just put it if the user didn't ask for it, right.
‫So that's why it select star sometimes kills the performance because look at all this stuff that it
‫needs to do, right?
‫It has to put in the hash table, has to fetch it from the database, from disk.
‫So select store is really harmful, starting to do it if you don't need to and yeah.
‫And you saw just.
‫Probing the second.
‫This is the second.
‫So it's called probing your probe.
‫And this probe is closed.
‫Big of one, big old one because it's very fast, because the hash has a cost is constant and the go
‫and give me that index also has a fixed cost.
‫Again, depends on whether you are numa versus not numa architecture and your CPU and how far your severe
‫from the ram all that jazz.
‫But it's almost let's say it's constant, right?
‫If you're at that stage, that's where you basically optimize.
‫That's a different level altogether.
‫Frankly, above my head, you know, it's just so, so much details.
‫But yeah, that's you go there and you fetch the value.
‫So now if you find the value, that means there is a match.
‫If you didn't, that means, hey, this value doesn't exist, so I don't join it and you create an output
‫relation as a result.
‫That's how you join.
‫That's a hash joint.
‫Obviously, there is optimisation and different hash joints, and I think I'm going to make another
‫episode talking about hash joints because they're like my methods.
‫What I just explained is the classic old hash joint, you know.
‫It becomes a problem because what happened if if the I cannot fit this stuff in memory, you know,
‫that's what a part of the limitation.
‫Hash tables are useless if you can't fit them in memory.
‫Right.
‫Because the whole point is because the whole thing is in array, you have to fit the array into memory
‫so you can use the byte address ability of the ram again.
‫Unless someone invents a byte addressable desk, all of these problems will go away hopefully.
‫I think there are a lot of attempts.
‫Ultra Ram was the latest that I'm aware of, you know, which is basically a persistent disk value that
‫is just as fast as the RAM, but it's also persistent.
‫You know, I'm going to reference the video that I talk about Altra Ram.
‫But yeah, a lot of the storage people, you know, they talk about this, they eat this for dinner
‫effectively.
‫But yeah, this is the idea of hash tables, hash joins, very, very popular concept.
‫Now I want to talk about the limitations of hash tables.
‫And this is where you really kind of link to the previous topic or hash joints.
‫Basically, watch out again.
‫Hash tables have to fit the memory.
‫To be utilized.
‫And that's the biggest, biggest problem, I guess.
‫You know, it's like what happened if you.
‫Because that's the first thing people will say is, hey, I'm going to build my entire key value store
‫as a hash table.
‫Hey, let's put that into our customer database, a hash table.
‫You can't how what kind of how how much memory do you need to put the entire thing in memory?
‫Because that's what you need to do, right?
‫Let alone just building that God -- thing.
‫You know, you need to build it first.
‫And to build it is costly because to build it, you have to scan the entire thing.
‫That's a big of when you're just scanning the entire thing, pull it in memory to build it, and that's
‫a cost.
‫Maybe you can consider this a fixed cost, right?
‫And then once you build that, then you have to do all of that, get it in memory.
‫Otherwise, if it's not a memory, you have no idea which parts will be fetched next.
‫I think you can play games here where you can play the idea of having I don't know if you have low level
‫access to the RAM where you say, hey, if if someone asks X is this location and it's not in Ram,
‫go fetch it from disk.
‫You can build.
‫Data structures like that, I believe, but I don't believe is going to be easy to do that.
‫Maybe they do exist and I'm not aware of them.
‫Please let me know if they.
‫If you have worked with such like.
‫Like disk hybrid model.
‫But that's the idea.
‫The limitation is the memory cost.
‫You know, it can't just have a billion size hash table, you know, plus the that's one thing, the
‫key size and the other thing is the actual values which is not really.
‫Might not be as problematic because they can live somewhere else.
‫The actual pointers you know it's just the indices is what what is critical and then the pointers can
‫can live somewhere else can in the heap of the memory.
‫They don't have to be consecutive like a string.
‫It's not really literally a string that lives in the element itself of the array.
‫It's a pointer to some other location that we don't care about.
‫As long as we have that pointer where we can jump to that memory location, then it's fine.
‫Yeah, it's an extra cost of the CPU, but until an AMD and all those people are taking care of these
‫optimizations, well, this is on to limitations.
‫The cost of building the hash table is a cost.
‫Right.
‫That's why you always pick the smallest in case of a join.
‫Right.
‫The other one is the.
‫Is a memory like you have.
‫You have to make sure it fits in the memory.
‫There are workarounds for this, I believe one.
‫One alternative to to hash joins is to avoid probing all over again because you have to scan this other
‫relation to always just go back and jump.
‫Right.
‫And that can be costly if you do it over and over and over again.
‫So you can effectively partition stuff.
‫So say, okay, let me just work with a smaller subset instead of their entire table.
‫Let me just create partitions.
‫Let's any value that I'm scanning, I'm going to create a partition that is closer to each other and
‫then I'm going to store it to disk and then read the partition from disk and then hash table that.
‫This way you don't have to scan the entire bill, the entire hash of the entire relation.
‫You just partition it and chunk it.
‫You work with that smaller, smaller size.
‫So that's another limitation.
‫There are workarounds.
‫Obviously.
‫The final thing is really with the biggest problem with hash tables is what happened.
‫If I want I want to keep adding new keys when I delete a key.
‫I want to add a new one and delete one.
‫Deleting and adding.
‫To a hash table.
‫Really screws up everything.
‫Why?
‫Because, remember, we're we're doing a hash and then we do a module on the size of the hash table.
‫So if you have a value and you hash it and a value of like from 0 to 10, like you should you you do
‫a module on ten, then you get a value from zero and nine, right?
‫So let's say you get eight.
‫But what happens if you add another element?
‫Right now, your hash table is 11.
‫Now the modulo operation.
‫If you do it modular 11, you're going to get a different value.
‫And now you're not pointing to the same index anymore.
‫So you have to do a remapping.
‫After you add or delete.
‫And that is costly, right?
‫So you have to scan the entire thing and then just reshift things.
‫It might not be as expensive.
‫Sometimes it's easy, sometimes it's slow, you know?
‫But but that cost of remapping, you have to keep it in mind.
‫That's why people will just say, okay, I'm going to work with.
‫I don't.
‫I'm not going to resize my hash table.
‫It's always going to be I don't know, it's always going to be ten, you know.
‫And as a result, you you don't you don't you don't anticipate that it's going to be increasing.
‫Right.
‫But again, if you fix it too large, then you're consuming a lot of memory and you have you might have
‫gaps.
‫If it's too small, then you might add values to the hash table, and that will cause remapping.
‫And that's a problem with Cassandra and SHA.
‫Any sharding database, a distributed database.
‫Right.
‫The problem is to do sharding.
‫You kind of use a hash table, right?
‫Because if I'm doing a query and this is my node, right?
‫You don't really specify a node per se, but you're basically based on the key.
‫So like if I'm inserting value eight, you hash that and then the value will map to a node or a shard
‫or a partition even partitioning you can do hash partitioning, right?
‫I'm talking about hash partitioning here, not range partition range is easy for like from 0 to 10000
‫goes to this server from 10001 to 20000.
‫Go to this server from 20,000.
‫You know, you get this idea, but if you are using hash based sharding, then every value is hashed
‫and then you calculate an index and that index pointer are array.
‫And the value of that value of that index in the array gives you the server name.
‫Then you had that server.
‫But what happened?
‫If you add a new server, then the whole thing changes.
‫Right.
‫Then what do you do if the change is then all of a sudden, if you try to read a key and instead of
‫going to that particular server, the the remapping has changed, now you're going to another server
‫and you're not going to find the key.
‫That's why Cassandra sometimes struggle with this.
‫If you when you do a remapping, it's really hard.
‫You know, they solved all these problems.
‫But I'm just discussing the the original problem here.
‫I say struggle.
‫I say initially.
‫Right.
‫So, like, if you add something I know to the ring, then the neighboring rings has to share values
‫because now you're remapping keys.
‫So the oh, if I'm if I'm adding value to a node, I need to join this value to shrink this, this cluster.
‫And now I have to borrow values from the my neighbors based on this remapping, you know, because now
‫oh, I no longer hold this key after this remapping.
‫Oh, this, this guy houses key.
‫So you have to rishard.
‫And this is where another concept was invented in 1997, I believe called consistent hashing, where
‫they try to minimize the effect of this remapping because remapping is expensive.
‫Right.
‫So consistent hashing.
‫Maybe another topic solves this to minimize that the effect after adding or deleting a node.
‫Because remember in a distributed architecture you're going to add and remove nodes all the time.
‫So consistent hashing the idea of having to consistently always hash to the same server no matter what
‫is very, very critical.
‫And maybe that's another topic for another day.
‫I hope you enjoyed this episode.
‫I'm going to see you on the next one, you guys, the awesome goodbye.
‫In a previous episode of the Vector Engineering Show, I talked about hash tables and how.
‫A powerful and very commonly used, they are given a key.
‫We can find its corresponding value in no time, in zero sick time.
‫We're not searching, we're not scanning or not doing anything.
‫It's a single access in memory retrieving that value.
‫The power behind hash tables is the use of the arrays, which is a very common data structure, obviously
‫a very, very common data structure.
‫Knowing the array position, the the index, you can get the value of the array immediately because
‫you know, how how does memory work if you know the address of the ram, where your cell exists, where
‫your values exist, you can get the value immediately.
‫The CPU can fetch the value immediately for you, right?
‫So once you find the index, you find the address, you can the value.
‫So what the hash table guys did, it says, okay, we're going to take your name, your string, your
‫color, your car, your anything.
‫The result, this key, we're going to hash it using a one way function and then convert that into an
‫index using a modulo function based on the array size.
‫So we eventually from the name we convert in getting an index and that will give us the address and
‫the memory and we can get the value.
‫So that's the trick the hash table guys use now.
‫So the only cost you add is like what the hashing function, which is not really that bad, but that's
‫the power of the hash table.
‫But the problem is the moment the size of the array changes, the hash table size changes.
‫This all falls apart because what what if blue, the key blue used to fit in index number 11.
‫If you increase or decrease the array size and you know where I'm going with this, then the blue will
‫fit into index 99 now and as a result, right, you either won't find the value or you're going to start
‫writing the values, duplicate and everything will basically be bad.
‫So you now have to really move things around when you resize and it's really a big problem.
‫So why I'm mentioning that the problem that we are seeing today with Distributed System is as follows
‫If my database are increasing in size and it no longer can fit in a single instance, i.
‫I bumped up the vertical scaling to its maximum.
‫It's now 48 core CPU, three gigahertz, whatever, you know, it's 512 gigabytes or even one terabyte
‫ram.
‫But it's still I have billions of rows.
‫I cannot I added all the indexes.
‫I try to partition it horizontally in the same instance by rain.
‫So but it's still the even the partitions are so large.
‫So I that machine cannot handle the queries throwing at my beautiful database.
‫So what do we do?
‫We just abuse it.
‫We shard the database.
‫That's I really don't like to go there unless I can exhaust all my options.
‫And believe me, people don't even look at the options anymore.
‫People are very quick to follow modern things, you know, without actually going to the basics and
‫trying to tune your database and getting a better performance.
‫But regardless, let's assume your YouTube scale lets you if you Google scale and you run out of ideas
‫that a single instance can't handle anymore, you need to distribute that billions of rows table or
‫key dictionary of collection and to multiple servers.
‫Right?
‫So instead of having billions, let's have a few millions on this server and a few millions in this
‫server.
‫A few millions.
‫And the server phenomenon in the server immediately a problem occur.
‫The problem is like, how do I know, right?
‫If I have a key, I want to look it up.
‫We introduced an intermediately an intermediary problem.
‫Right.
‫That didn't exist before.
‫What?
‫First, if I have a key, I go to my database server and I ask it and I immediately give it to me.
‫I only go to one hop.
‫Now, if you are distributed and you only have the key, you have to answer the first question Which
‫server should I connect to?
‫To retrieve the key, which server hosts my key?
‫And that is the problem here.
‫That is the original and only problem that we have in distributed system.
‫Which server should I connect to to fetch that key?
‫So the trick was always.
‫Let's figure out the server from the key, and that is the concept of hashing.
‫Hashing tables appear here.
‫So in this episode of the show, I'd like to talk about that a little bit.
‫Distributed, hashing and then.
‫What problems did we have and how consistent hashing solved this problem?
‫And obviously nothing is perfect in this hoard.
‫So I'd also like like to talk about the problems, consistent hashing I actually have today.
‫Welcome to the back of the energy show with your host say and also and the concept of distributed system
‫is a must when you get to a certain scale.
‫Yeah I always try as much as possible to, you know, push people against being distributed if they
‫can do things to have their single instance, you know, be more performant when it comes to query.
‫Because you see a lot of a lot of people are engineers hurry up to scale, right.
‫And spend more money to start to work with a distributor without actually while their query is actually
‫using 500% of their CPU and then doing like a million logical reads, you know, where they can tweak
‫it a little bit and tweak it and tune the database a little bit, understand their queries so they can
‫have or even, you know, lower that cost, you know, as a result.
‫But we don't think this way anymore.
‫We always take the shortcut, unfortunately.
‫But regardless.
‫So usually advance and adept DBA is try to optimize a single query.
‫As a result, if you if you can get a query to consume less CPU, even if it's a small query is scaling
‫that query right.
‫Will eventually gives you a better scaling on your instance.
‫But that's not our topic.
‫That's not today.
‫But let's say you reached a state where you exhausted all your options.
‫You know, when it comes to a single instance, right?
‫Then you moved, it says, hey, I have to move to a distributed system.
‫It's just too large.
‫You got to move.
‫So people what they did.
‫So it's okay.
‫I have a key.
‫And no, I don't know which.
‫I have ten servers.
‫I don't know where this QI lives in this ten server environment.
‫So say, all right, so we're going to do let's say I have four server, I cluster with four servers
‫and I want to distribute my values across these four servers.
‫So server as zero as one is two and three, right.
‫What are we going to do is like giving the key.
‫I need to know the server name, the server IP, and that's something that we are introducing as a problem.
‫Like we introduced a friction that didn't exist before first previously.
‫So I just one server we know the server, right?
‫But now we have to figure out from the key, we have to figure out the IP address of the server to connect
‫to in order where our key actually exists.
‫And that answer can be answered using a very simple hashing function.
‫So we're going to hash the value.
‫Let's say I have value number four, going to hash it, get some value and then def value.
‫We're going to do modulo number four and that gives you server zero.
‫So.
‫Server server zero right here in this case.
‫So four modulo four is zero.
‫And then, okay, how about key number five, right.
‫Or even whatever the key used to be.
‫There may be let's say it's a blue or red.
‫Right, red.
‫You're going to hash it, get that value number five, which is a number and then five, modulo four
‫will give you a swan and it's one.
‫We'll go right here.
‫Right.
‫So five.
‫Right lives in this one and same thing.
‫Six will live in a stew and seven will live in as three.
‫We're just go to the module four because four is your server pool size, right?
‫And then let's say going back, let's say eight, then eight, modulo four oh, so back to zero and
‫then you get the point which is, which works perfectly from the key.
‫I was able to figure out.
‫The server.
‫So cost is zero is nothing.
‫Here's we solve distributed system right there.
‫Here's one problem, though.
‫As long as you have four servers, you love his beautiful, you don't have to worry about anything.
‫But now even those four servers reached their limit again.
‫Whatever reach the limit.
‫That means your your at the globe scale.
‫You know you have so many users, right.
‫So to me that I need four machine more than four machines database instance that means I am at the global
‫scale and I have users left and right, millions of heads, you know.
‫So that's the scale we're talking about, right?
‫So I'd say, okay, all right, let's just add another server server for S4.
‫So we have s zero as one as two as three and s four.
‫Sounds good.
‫Comes back to the problem of hashing tables.
‫The moment you change the size that whatever value where original so.
‫The values, their original key values are now all shuffled right previously value number for use.
‫You do a for modulo for the key for use to live in server as zero because four modulo four is zero.
‫But now for modulo five which is now the new servers we have five servers is actually gives you a value
‫of four.
‫So it's now as an is four.
‫So now what you need to do is like move the key with value for from the server zero to server four and
‫now you have to move everything else.
‫And this is, this is basically the same thing five modulo five, right?
‫The server five, the key four will move to server four, the key eight will move to server three.
‫The key five will move to server zero.
‫The key six will move to server one and the key seven will move to the key seven will move to S1, right?
‫So everything will be shuffled and the operation of adding a new server will cost us a huge amount of
‫effort to kind of shuffle things around.
‫So look, think of networking, think about database usage just to add another server to not only bothering
‫one server, you're bothering the entire cluster with your operation because you have to shovel things
‫on.
‫Right.
‫Because the key no longer maps.
‫So what what people think, what the smart people say, okay, let's invent something that might solve
‫this problem, which is called constant hashing.
‫So how does it really work?
‫So they go they went back to the idea of having so they went back to idea the core idea.
‫We use the index as the server names here.
‫Right.
‫Let's flip this.
‫Let's change this a little bit.
‫Let's not be very discrete like oh, server zero one, two, three, four, let's build a ring.
‫Let's actually build a ring of these servers.
‫All right.
‫So instead, they think of this idea as an actual ring, as an actual circle.
‫So values go back, right.
‫And.
‫Remember, a lot of people thought a lot of all this to solve this problem.
‫And the key here is instead of the output of the key hash going to a server, we're going to approximate
‫it, you know, by by using this concept of the rank.
‫So let's take an example.
‫So clarify it.
‫The first thing we're going to do is the server rooms themselves.
‫We need to fit them on the rank, which this is something we didn't do before.
‫So the ring is think of this ring as, as a circle.
‫So.
‫The degree is based on the degrees.
‫This is a 360 degrees, right?
‫So a server, let's say server one, you're going to do a module 360.
‫Let's say we're going to get a zero, right?
‫So we're going to put server server one and ask we're going to call it zero based on the degree here.
‫And then let's say server two IP address ten 003 modulo 360.
‫We got 90, right?
‫And again, I'm picking and picking values that are so rounded up.
‫This is just, for example, you never get a gate, you're hardly going to get 90, right?
‫Exactly right.
‫You're going to probably get X as 27.
‫But yeah, x 90.
‫Same thing.
‫Server three or server four are going to get S 180 if after you do that and then server three going
‫to get SW 20 to 70, we have zero S 90, s 180 and SW 270.
‫You know, that's that completes an actual range.
‫And for people listening in the podcast, think of this as an actual ring with the values for servers
‫in each corner effectively.
‫So why are we doing this?
‫The beauty here is we have values and this is the key here.
‫Let's have a key value of 1000.
‫Same thing you're going to do, right?
‫The 1000.
‫The key value thousand.
‫Right.
‫Why over this key exists.
‫Maybe it was blue and then you did a hash and then you got the number thousand.
‫You take that thousand, right?
‫And you do a module of 360.
‫Will you get an actual server immediately?
‫The server index?
‫No, you're not going to get that.
‫So now let's let's actually put it in an action example right here.
‫Right.
‫So now I'm about to insert a value.
‫I'm going to insert a new key.
‫Value 1500.
‫That's.
‫That's my key right there.
‫So what are you going to do?
‫Is you going to do modulo 360, which is the circle again don't don't be very specific on the value
‫360.
‫You can double this and double this and double this to give more values.
‫But again, this is just an example.
‫So 360 here.
‫So if I take 1500, right.
‫And module 360.
‫I'm going to get a value of 60, if you think about it.
‫60 doesn't exist.
‫There is no server marked 60.
‫But here's a trick.
‫We do have a server mark as zero and we have an SX 90.
‫So 60 really fits between the zero and the 90.
‫And what you do is you pick the next one, so 65th between zero and 90 immediately.
‫So the key will go to the next value, which is s 90.
‫And that's, that's how you do it basically now.
‫Visually.
‫This is easy to understand right computationally.
‫This is not as simple, because what does that mean between zero and 90?
‫I have I have four servers.
‫And that's that's easy to find where where your value how 60 fits between zero and 90 is actually computational.
‫And that's another binary search to actually find that value that's a little bit outside us outside
‫the scope of this video.
‫But now once we have that value, we have the 60 now OC oh 60 is like what's right after 60 is 90 now.
‫Okay.
‫So the value of 1500 fits on server is 90.
‫That's how we solve it.
‫So.
‫By doing this scan, what is the next one?
‫We really remove that discreet value lock up.
‫You know, we instead changed it with a scan and the beauty of this scan.
‫It's going to save us a lot of things in the future.
‫Let's continue this example.
‫All right, 1500.
‫Let's take another example as, say, 2000, 2000.
‫Model 360 is 200, 250 between server s 180 and server is 270 again 180 and 270.
‫Think of that as degrees, right?
‫So right there in this case, OC what's exactly right after 200, it's 270, so 2002 70.
‫So think of it like you're looking at clockwise.
‫So whatever is the next value, you're going to get that.
‫And then you put another value, say 3000 modulo 360, that's 121 25th between server 90 and server
‫180.
‫So like move directly to the 180 and then you store the value 3000 there.
‫How about 20,000 modulo 360 is actually gives you 280.
‫Wait a minute.
‫280 is the there are no server after the last server.
‫The largest value is actually is 270.
‫There is no larger after that.
‫Right.
‫There is no larger than two server 270.
‫This is values to 80.
‫So what do you do if there is no larger values?
‫You go back to the circle, right?
‫And this is very nicely.
‫When you actually draw the circle, you see that it's two eight is between is 270 and is zero.
‫So you immediately go and put the value thousand in server zero and that's how you build the ring.
‫Let's take another example for completeness here.
‫4000, 4000, modulo 30, 60 gives you 40, 40 is between zero and 90, right?
‫Oh, that's very nice.
‫So four.
‫So now we have two keys lives in server is 90 in this case.
‫Yeah, that's very interesting.
‫Let's spice things up now.
‫What if I added a new server here?
‫Look at the beauty of this here.
‫Now, if I had a new server here, let's say it's IP address.
‫Is that ten zero zero 13.
‫Right.
‫I do it modulo 360 and I got 50.
‫So now my server is actually s 50 fits right between zero and is 90.
‫Keep that in mind now.
‫Things change because we.
‫Still need to move data around, but not as much.
‫Let's figure that out.
‫How much data?
‫I need to move around?
‫Well, the algorithm goes like this, right?
‫Remember, if you have values, if you add value says 50.
‫In this case, anything between the zero and the 50 really needs to be fed in server 50.
‫Right.
‫Because that's the algorithm.
‫That's the range here that we're looking at right here.
‫And so if you the algorithms look like this, like, okay, so what is the server right after me?
‫Well, the server right after me is right here is 90, right.
‫So let's query that server, find out all the hash values now, all the hash values where the actual
‫hash value is less than 40.
‫Right, because it's 90 would have stored everything between zero and 90.
‫Right.
‫So find out everything that is less than 50 because I should store this now.
‫Right.
‫So we found one entry which is 40 oh 40 doesn't belong 90 anymore.
‫So go ahead and talk to server 90, establish a communication, could be TCP can be anything and then
‫start moving data around.
‫Right?
‫Hey, it's 90 and do you have anything with a hash value that is less than 40?
‫It's less than 50, which is me.
‫Oh yeah.
‫I have this value move it to me.
‫And as a result, we just establish the data here.
‫So now think of it as, as I add another server.
‫The only change is my neighbor.
‫Really, I'm only going to bother my neighbor and only the neighbor right after me.
‫Right.
‫That's that's what I'm going to do in this case.
‫Right.
‫And so instead of actually.
‫Bothering all the servers in my cluster, I'm only bothering one server.
‫So that's much, much, much better than actual hashing.
‫But is still there is a cost to it, right?
‫That is complexity.
‫You need to build all that out.
‫What if the operation failed?
‫How do you roll back?
‫What if do you add the server any way?
‫What if one of the keys didn't transmit?
‫So we're adding so much complexity.
‫So distributed systems are not easy, you guys, right?
‫Even if you think about it, let's take another example where we're removing a server.
‫If we go back to our original case where we have zero as 90 is 180 and it's 27 and let's say I'm about
‫to remove it's 90 altogether.
‫So now what happens here if you remove is 90, then anything that is 90 had must go to S1 80 if you
‫think about it.
‫Right, because any value.
‫So now what happens is the operation should go okay remove server is 90 that the operation that we need
‫to do right I'm going to remove that physically remove it not talking about a crash that's a completely
‫different story, right?
‫Crash.
‫You don't even have time to move anything.
‫Right.
‫So if you that's why you have to have redundancy.
‫That's another complication right there.
‫But if I have a physical operation, let's say, okay, I want to remove this for maintenance, remove
‫this 90 well, it's 90 holes and all that is between zero and 90.
‫So all of those should go directly to the server right after me clockwise, which is 180.
‫So remove all those puppies and stack them to where to server 180.
‫That's a very expensive operation as well.
‫So if you think about it, consistent hashing are powerful is powerful.
‫The algorithm of consistency are very powerful.
‫But the limitation here becomes you still need to move data around and the more data you have, you
‫know, in these instances, then the transmit of these will take more time.
‫So adding or removing server is actually not a trivial operation, you know, and then you really didn't
‫think need to think about that.
‫Another thing that is called replication, you need to duplicate this data as much as possible because
‫a server might crash.
‫So you need to have a backup.
‫So just using this algorithm blindly is not enough.
‫You have to cater for crashes, you know, and as a result, you have to have a backup.
‫Oh, if this sort of wasn't unavailable, let's, let's have a mapping server that actually directly
‫copies that data immediately.
‫Right?
‫So that's what you do.
‫You have to do that.
‫Well, what if two servers mapped to the same hash?
‫You can't have it.
‫If you have a lot of more than 360 servers, you're going to you're bound to have the value that fits
‫in the same server.
‫And I'm not sure what you can do here.
‫You can what you can do is like, I suppose in this case, you can treat it as a as a replication.
‫So you have like a backup scenario where we have this server, you can either put it in both.
‫That was an episode of the consistent hashing.
‫I hope you enjoyed this video.
‫I'm going to see you in the next one, guys.
‫Goodbye.