Home‎ > ‎

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

Screenshots and videos


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}
}
Ċ
Alexandre Hardy,
Jul 30, 2018, 12:39 AM
Comments