15619 Project3.2 Guide

Posted on | In

Project3.2 Partitioning (Sharding) And Replication

Basics

Replication: keep multiple copies of data to improve GET performance and recover from database outages.
Partitioning(Sharding): separate data among many nodes to improve PUT performance. Horizental partitioning: shard by rows, vertical partitioning: shard by columns.

Part 1: Implementing Replication with Strong Consistency

Strong consistency:

  1. Strict Consistency: same key has same value all the time
  2. Strict Ordering: fulfill requests in the order they arrive
  3. Atomic Operations: one fails all fail
  4. Controlled Access: lock the item while writing is being fulfilled

Create a lockshop HashMap<String, ReentrantReadWriteLock> lockShop to set lock for each key

Part 2: Implementing Sharding with Even Distribution

Consistency hashing: assign keys to nodes evenly with fault tolerance. The hashing algorithm must return the same value for the same key at all times.