We describe a client-side sharding system which follows the naïve approach of hashing keys in documents to determine the shard that a document belongs to. Our database clients support a limited set of (NoSQL like) operations. We extend this simple approach by describing a scheme for rebalancing data between shards when new shards are added. The rebalancer is a client of each shard similar to the other clients in the system. We describe the algorithms required to present a consistent view to clients of the sharded database system during rebalancing. These algorithms permit a limited set of database operations to be executed in a lock-free fashion. Our clients do not rely on any notion of logical or global clocks to achieve a consistent partial event ordering.
naive_shards.pdf
@misc{Naive,
title = {Na\"ive, lock-free, client-side sharding with online addition of shards},
howpublished = {\url{https://sites.google.com/site/ahardyproject/naive-shards}},
note = {Accessed: 2018-07-30}
}