Consistent Hashing Explained for High Schoolers
akshatm.svbtle.com
akshatm.svbtle.com
I did notice one conceptual error near the beginning:
> Computers can pull this trick off too: they take a value, and store it at a location in memory. Then, given a key, they somehow use that key to figure out the address of that memory location, go to that location, and return that value.
> Figuring out the address is called hashing, and maps that work like this under the hood are called hash tables.
That definition isn't right. Looking up a key to get a value isn't called "hashing". Hashing and hash tables are just one out of a number of ways that a program could do this.
For example, given the data objects in the first illustration that have Key and Value properties, you could simply use a linear array of these objects. Then you loop through the array looking for the matching Key, and there you have your Value. Hashing is not involved here.
Of course, as the array gets longer, this simple loop gets slower and slower. That's where you start looking for faster algorithms and data structures such as hash tables. But the hash table isn't fundamental to doing a name/value lookup, it's just one way to do it.
Another example is a trie, very different from a hash table but could be used for the same purpose. Tries are often used where you may want to get a list of values that match a prefix (like an autocomplete) but they can also be used for a full match just like a hash table or a linear array.
Not to detract from the write-up, but I think the claim that the explanation is "accessible to an ordinary high-schooler" is an overly bold one.
This is also a great reminder of how incredibly elegant and powerful the basic data structures (hashmaps and binary trees in this case) really are. It doesn't take a fancy implementation to make this stuff work. Just the basics gets it done.
However, rendezvous hashing is superior to consistent hashing because consistent hashing gets hotspots if you lose a node, unless you are using many virtual nodes (which then adds a large overhead). Also, rendezvous hashing doesn't require all the clients to know the state of all the nodes.
So maybe it would be good to update the lesson for rendezvous hashing. :)
Might at least give you a high level overview. Then you can read this Python which is pretty straightforward:
https://github.com/nikhilgarg28/rendezvous/blob/master/_rend...
I think you'll like it! :)
That said, I think the author does a good job of doing exactly that.
EDIT: I am a teacher.
I tend to think students are capable of learning many more things than people will sometimes give them credit for. Maybe they have to do more background preparation, but I would be reluctant to say someone couldn't learn this.
Now, when it comes to applying it in a novel way, I'd be more inclined to think fewer students get to that point.
I don't know where you went to school, but I've also come to learn that the vast majority of high school students can be spectacularly disappointing with regards to their motivation to learn topics like this, even if they're fully capable of doing so.
>"A glossary, too, is a map - given a word, it can take you to the exact page the word is referenced."
I think the author means index not glossary. I know its a nitpick but its such a well-written post otherwise I thought I would mention it. Cheers.
Other reasons:
- Other blog posts about consistent hashing fall prey to favouring 'clever' implementations, which is great for advanced Pythonistas, but serves to obfuscate for anyone else. Similar arguments hold for many existing BST implementations. - Implementing the custom lookup I sought for this implementation was easier if I went with something hand-rolled, and was fine since I don't expect anyone to actually use this implementation in production (I mean, they can, but there are better implementations out there).
Essentially, my goal was transparency and clarity. This was the best way to do it, all things considered.