Data Storage, Replication, and Integrity Syllabus

Reading list designed to help programmers understand the domain of storage, replication, and integrity. There are basically no modern books on the topic as a whole.

The study of transactions is very well covered so that a section on transactions is explicitly not a part of this reading list.

THIS IS WORK IN PROGRESS. Send me suggestions.

Part 1: Data structures

Reading list:

• B-Tree
  • Modern B-Tree Techniques
  • More Modern B-Tree Techniques
  • An Introduction to B epsilon trees and Write Optimization
  • B-Tree Visualization
  • B-Trees Are Back: Engineering Fast and Pageable Node Layouts
• LSM Tree
  • LSM-based Storage Techniques: A Survey
  • A Critical Survey on Log-Structured Merge Trees
  • Towards Flexibility and Robustness of LSM Trees
  • Dissecting, Designing, and Optimizing LSM-based Data Stores
  • RocksDB: Evolution of Development Priorities in a Key-value Store Serving Large-scale Applications
• Btree vs LSM
• Revisiting B+-tree vs. LSM-tree

Key topics: LSM Tree, B-Tree

Part 2: Dealing with failure

Reading list:

• Enhancing File System Integrity Through Checksums
• End-to-end Data Integrity for File Systems: A ZFS Case Study
• Can Applications Recover from fsync Failures?
• An Analysis of Latent Sector Errors in Disk Drives
• Gray Failure: The Achilles' Heel of Cloud-Scale Systems
• The Tail at Store: A Revelation from Millions of Hours of Disk and SSD Deployments
• The Tail at Scale
• An Analysis of Data Corruption in the Storage Stack
• A Study of SSD Reliability in Large Scale Enterprise Storage Deployments

Key topics: torn writes, torn reads, misdirected writes, misdirected reads, use of checksums, fsync

Part 3: IO models

Reading list:

• Understanding Modern Storage APIs: A systematic study of libaio, SPDK, and io_uring
• What Modern NVMe Storage Can Do, And How To Exploit It: High-Performance I/O for High-Performance Storage Engines
• Asynchronous I/O — With Great Power Comes Great Responsibility
• Characteristics of multithreading models for high-performance IO driven network applications

Key topics: thread-per-core, io_uring, epoll, aio, spdk

Part 4: Replication

Reading list:

• Data Replication Design Spectrum
• Quorums and leaderless consensus
  • Cassandra - A Decentralized Structured Storage System
  • EPaxos Revisited
  • Fast General Purpose Transactions in Apache Cassandra
• Reconfiguration
  • Object Storage on CRAQ
    • 6.824 FAQ for Object Storage on CRAQ
  • FoundationDB: A Distributed Unbundled Transactional Key Value Store
  • Taurus Database: How to be Fast, Available, and Frugal in the Cloud
  • PacificA: Replication in Log-Based Distributed Storage Systems
• Leader-based consensus
  • In Search of an Understandable Consensus Algorithm (Extended Version)
    • Consensus: Bridging Theory and Practice
    • Paxos vs Raft: Have we reached consensus on distributed consensus?
    • Paxos Made Live - An Engineering Perspective
    • A TiKV Source Code Walkthrough – Raft Optimization
    • Simplifying Redpanda Raft implementation
  • Viewstamped Replication Revisited

Key topics: raft, paxos, chain replication, viewstamped replication