Single-machine data stores cannot support the scale and ubiquity of data
today. The Internet applications and services must process a huge number
of concurrent requests and events per second. So, they use distributed (or
replicated) data stores which store and process data on multiple machines,
offering key advantages in performance, scalability, and reliability. The
purpose of the talk is to present a selective and biased choice of
techniques and results which can be used for building an efficient
distributed data store. Biased, because I only present solutions and
results developed within a research project that I did with my PhD
students. Selective, because an exhaustive description would be too
exhausting to fit into a single talk. Therefore I will be discussing just
the design of our novel database index for key-value data store systems,
and only skim our other contributions that are directly related to
distributed systems. The index, called Jiffy, has been designed with
performance and scalability in mind. Therefore it has been designed as a
lock-free concurrent data structure, which can dynamically adapt to the
changing workload. It achieves superior performance despite built-in
atomic operations (batch updates, snapshots, and range scans). During the
talk I will be presenting Jiffy's architecture, the algorithms for
inserting and looking up the key-value pairs, and the operations used for
resizing the data structure dynamically. The other contributions of our
project include: efficient support for replica state recovery after
failures, either by extending the classic Paxos consensus algorithm, or
through the use of persistent memory, and a bit surprising theoretical
results which are applicable to distributed data store systems that
compromise consistency in favour of high availability and speed, but also
support operations ensuring strong consistency (which requires consensus
among replicas). (Based on a keynote talk at DEBS '23)
