Scalability through asynchrony in transactional storage systems

Modern storage systems face daunting scalability challenges. The amount of data stored worldwide is doubling every two years. Compounding this problem are growing demands for these storage systems to offer strong correctness guarantees (such as consistency and transactional isolation): these guarantees require a degree of coordination that negatively affects scalability. Prior work has shown, that avoiding coordination is the key to scalability for a variety of systems. This dissertation explores scalability problems due to coordination that is an artifact of the mechanisms used to implement a system rather than a fundamental requirement of the system's correctness guarantees. We call this phenomenon mechanism coordination. We explore how to build scalable storage systems that minimize mechanism coordination while continuing to provide stronger consistency guarantees to their clients. We develop the insight that assuming nothing about how clients access these systems leads to synchronous implementations, which in-turn leads to mechanism coordination and scalability bottlenecks. By letting the design of these systems be informed by how clients are going to access them in the overwhelmingly common case, it is possible to derive asynchronous implementations that minimize mechanism coordination, enabling them to scale. We demonstrate the broad applicability of this insight by building asynchronous client-driven solutions to two different scalability problems in two different classes of storage systems. The first part of the dissertation solves the problem of “slowdown cascades” in large-scale geo-replicated and distributed storage systems that provide causal consistency to their clients. The second part of the dissertation solves the problem of CPU contention on range indexes in multi-core in-memory databases that provide serializable isolation to their clients.Computer Science