Naïve, lock-free, client-side sharding with online addition of shards

Abstract

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.

Preprint

naive_shards.pdf

BibTeX entry

@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}

}