Database design
Data Partitioning using Consistent Hashing:
Data partitioning is crucial for distributing data across multiple nodes in a distributed key-value store system to achieve scalability and efficient data access. Consistent hashing is a popular technique used for data partitioning in distributed systems.
- Consistent Hashing Overview:
- Consistent hashing is a hashing technique that minimizes the need for rehashing when the number of slots or nodes in the system changes.
- It provides a way to map keys to nodes in a distributed system in a consistent manner, ensuring that each key is assigned to a specific node regardless of changes in the system's topology.
- Consistent hashing achieves this by mapping both keys and nodes onto a common hash ring, where each node and key is associated with a point on the ring.
- Using Consistent Hashing for Data Partitioning:
- In a distributed key-value store system, consistent hashing can be used to partition data across a cluster of nodes.
- Each node in the cluster is assigned a range of hash values on the hash ring, forming a virtual "token" space.
- When a key needs to be stored or retrieved, its hash value is computed, and the corresponding node responsible for that hash range is determined.
- This ensures that each key is consistently mapped to the same node, allowing for efficient data access and distribution across the cluster.
- Advantages of Consistent Hashing:
- Load Balancing: Consistent hashing distributes data evenly across nodes, preventing hotspots and ensuring balanced load distribution.
- Scalability: As the cluster size changes (nodes added or removed), only a fraction of keys need to be remapped, minimizing the impact on the system.
- Fault Tolerance: In case of node failures or additions, consistent hashing allows the system to redistribute data efficiently without significant data movement.
- Considerations for Consistent Hashing:
- Replica Handling: Consistent hashing can be extended to handle data replication by assigning multiple replicas for each key across different nodes.
- Virtual Nodes: To improve load balancing and reduce data movement during node additions or failures, virtual nodes can be used, where each physical node is represented by multiple virtual nodes on the hash ring.
Data Replication Strategies:
Data replication ensures fault tolerance and high availability by storing multiple copies of data across different nodes in the system. Common data replication strategies include:
- Full Replication:
- Every piece of data is replicated across all nodes in the system.
- Provides strong fault tolerance but may lead to high storage overhead and network traffic.
- Partial Replication:
- Each piece of data is replicated only on a subset of nodes.
- Reduces storage overhead compared to full replication but may require careful placement of replicas to ensure fault tolerance.
- Quorum-based Replication:
- Data is replicated across a subset of nodes, and read/write operations require a quorum (a minimum number of replicas) to be successful.
- Provides a balance between fault tolerance, consistency, and performance by allowing tunable consistency levels.
For our design we will go with Quorum-based replication, this will be explained in detail in the detailed component design section.
Consistency and Types of Consistency:
Consistency in a distributed key-value store system refers to the agreement of data across multiple replicas. Different consistency models offer varying levels of guarantees:
- Strong Consistency:
- All replicas return the same value for read operations, ensuring that clients always see the most up-to-date data.
- Achieved through synchronous replication and coordination mechanisms such as distributed transactions or strict quorums.
- Eventual Consistency:
- Replicas may temporarily diverge but eventually converge to a consistent state.
- Allows for higher availability and better performance but may lead to temporary inconsistencies visible to clients.
- Read Consistency Levels:
- Read operations can be tuned to provide different consistency guarantees, such as strong consistency, eventual consistency, or read-your-writes consistency, where a client always sees its own writes.
Strong consistency is usually achieved by forcing a replica not to accept new reads/writes until every replica has agreed on current write. This approach is not ideal for highly available systems because it could block new operations. Dynamo and Cassandra adopt eventual consistency, which is our recommended consistency model for our key-value store.