Consistent Hashing

Overview A key-value store (key-value database) is a non-relational database Unique identifier keys can be plain text or hashed value Short keys are more performant than longer keys Values can be strings, lists, or objects, etc Values are usually treated as opaque objects in Amazon Dynamo DB, Memcached, Redis. (Opaque objects are not coded to interfaces) Key-value stores support the following operations: put(key, value) get(key) Scope Keep key size small: less than 10 KB Large storage capacity High availability Automatic scaling (add / remove servers) Tunable consistency Low latency Single server architecture A single server key-value store can be implemented with an in memory hash map Optimization: Compress data Keep frequently used data in memory and store the rest on disc A single server key-value store cannot be scaled to support big data Distributed architecture A distributed key-value store is also called a distributed hash table CAP theorem & distributed systems According to the CAP Theorem, a distributed system can only achieve two of the following properties:...

What is hashing? Hashing is transforming a piece of data of an arbitrary size to another value. If the data is transformed into an integer for example, the hash space is a range of integers from 0 to xn. The smaller the range, the greater the probability of collisions (multiple pieces of data mapping back to the same value). A good hash function reduces the probability of collisions. A data structure called a hash map uses an array of size xn+1 where each element points to a data bucket....