How Key value Stores Work (Redis, DynamoDB, Memcached)?

Key Concepts

Key-value stores, hashing, modulo, consistent hashing, data replication, consistency vs. availability, eventual consistency, vector clocks, gossip protocol, distributed systems.

Key-Value Stores: The Foundation

• Definition: A key-value store is a type of database that stores data as a collection of key-value pairs, similar to a dictionary.
• Example: A user's shopping cart can be represented as a key-value pair, where the key is the user ID (e.g., "user12345cart") and the value is the list of items in the cart.
• Scale: Companies like Amazon store terabytes of data per region, with billions of key-value pairs accessed millions of times per second. This necessitates distribution across thousands of servers.

The Hashing Challenge and Consistent Hashing

• Problem: Distributing data across multiple servers requires a mechanism to determine which server holds a specific key-value pair.
• Naive Approach (Hashing and Modulo): Hash the key, divide by the number of servers, and use the remainder to select a server.
  • Issue: Adding or removing servers changes the divisor, causing almost every key to map to a different server, requiring massive data movement.
• Consistent Hashing: A solution to minimize data movement when servers are added or removed.
  • Concept: Map both keys and servers to a circular space (e.g., a clock face with millions of positions).
  • Server Placement: Servers are placed at random positions on the circle.
  • Key Mapping: Hash the key to a position on the circle and move clockwise until the first server is encountered. That server is responsible for the key.
  • Advantage: Adding a server only requires moving data from the server that now follows the new server on the circle. Only a fraction of the data needs to be moved.

Data Replication and Consistency

• Problem: Server failures can lead to data loss.
• Solution: Data Replication: Store multiple copies of each key-value pair on different servers.
  • Implementation: After hashing a key to a position on the circle, store the data on the next n servers clockwise (e.g., the next two servers).
• Consistency vs. Availability Trade-off: In distributed systems, it's impossible to guarantee perfect consistency, perfect availability, and perfect network reliability simultaneously. You must choose two.
  • Consistency: Ensures all clients see the same, most up-to-date data. May require refusing requests during network partitions. Banks prioritize consistency.
  • Availability: Ensures the system remains operational even during failures. May serve stale data. Most web applications prioritize availability.
• Eventual Consistency: A compromise where all data copies will eventually converge to the same value, but may be temporarily inconsistent.

Handling Conflicting Versions

• Problem: Concurrent modifications to the same data on different servers can lead to conflicting versions.
• Vector Clocks: A versioning mechanism that tracks which server modified a piece of data and when.
  • Functionality: Every time data is modified, it's tagged with information about the server and the timestamp of the modification.
• Conflict Resolution Strategies:
  • Automatic Merging: Combine conflicting versions (e.g., merging shopping carts).
  • User Choice: Ask the user to resolve the conflict.
  • Last Write Wins: Choose the most recent version.

Failure Detection and Gossip Protocol

• Problem: Detecting server failures in a large distributed system.
• Naive Approach (All-to-All Pings): Each server pings every other server.
  • Issue: Doesn't scale well. With thousands of servers, the number of connections becomes unmanageable.
• Gossip Protocol: A decentralized failure detection mechanism.
  • Mechanism: Each server maintains a list of other servers and periodically shares this list with a few random neighbors.
  • Failure Detection: If a server stops responding, the information spreads through the cluster like a rumor.
  • Advantage: Scalable and efficient, as it doesn't require every server to communicate with every other server.

Conclusion

Key-value stores, while seemingly simple, involve complex distributed systems engineering challenges. Consistent hashing, data replication, consistency management, and failure detection are crucial for building scalable and reliable systems. The trade-offs between consistency and availability must be carefully considered based on the application's requirements. The next time you interact with a system that uses a key-value store, remember the intricate processes happening behind the scenes to ensure data integrity and availability.