What is hashing?
Hashing is a process of transforming a arbitrary size object (string of characters) into a fixed-length alphanumeric value.
Algorithms: SHA-256, MD5, SHA-1.
What to do if you want the same requests to go to the same server? Same clients request to go to the same server?
Consistent Hashing
- Consistent hashing solves the problem of rehashing by providing a distribution scheme which DOES NOT directly depend on the number of servers. This allows servers and objects to scale without affecting the overall system.
- In consistent hashing, both the keys and the buckets are hashed onto a circle.
- Consistent hashing is a special kind of hashing where on an average, K/n keys are remapped whenever the list of endpoints changes (K is the total number of keys).
- Searching for the bucket responsible for a key is pretty simple — pre compute the hash values for all buckets and sort them, hash the key and then run a binary search (in O(log(n))) to find the lowest value that’s higher than the hash of the key.
- To balance requests evenly after removing or adding a new server, virtual. servers can be added.
- https://medium.com/system-design-blog/consistent-hashing-b9134c8a9062
Rendezvous Hashing
- Rendezvous Hashing also solves the problem of rehashing.
- Rather than picking a single server, each key generates a randomly sorted list of servers and chooses the first server from the list.
- For example, let's say the hashing algorithm results in such mappings:
- key a - [S1, S2, S3],
- key b - [S2, S3, S3],
- key c - [S3, S1, S2]
- For the case above, a will be mapped to S1, b will be mapped to S2 and c will be mapped to S3.
- If let's say S2 is down, then a will still be mapped to S1, c will still be mapped to S3, and then only b will be mapped to different server, which is S3 since the first option S2 is no longer available.
- https://medium.com/i0exception/rendezvous-hashing-8c00e2fb58b0
- https://randorithms.com/2020/12/26/rendezvous-hashing.html
