Papers

Algorithms

• Leapfrog Triejoin: A Simple, Worst-Case Optimal Join Algorithm
• Skew Strikes Back: New Developments in the Theory of Join Algorithms

Data Structures

• Modern B-Tree Techniques
• The Log-Structured Merge-Tree (LSM-Tree)
• Fast and Lock-Free Concurrent Priority Queues for Multi-Thread Systems
• 🟠 The Bw-Tree: A B-tree for New Hardware Platforms

Distributed Systems and Databases

• In Search of an Understandable Consensus Algorithm (Extended Version)
• 🟠 ARC: Analysis of Raft Consensus
• Viewstamped Replication Revisited
• Providing High Availability Using Lazy Replication
• Raft Refloated: Do We Have Consensus?
• ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging
• Tango: Distributed Data Structures over a Shared Log
• Wormhole: Reliable Pub-Sub to Support Geo-replicated Internet Services
• All Aboard the Databus!
• Unreliable Failure Detectors for Reliable Distributed Systems
• Life beyond Distributed Transactions: an Apostate’s Opinion
• Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases
• Amazon Aurora: On Avoiding Distributed Consensus for I/Os, Commits, and Membership Changes
• G. Graefe. Instant recovery for data center savings.
• Y. Saito and M. Shapiro. Optimistic replication
• MapReduce: a flexible data processing tool
• David K. Gifford. Information Storage in a Decentralized Computer System.
• J. Levandoski, D. Lomet, S. Sengupta. LLAMA: A cache/storage subsystem for modern hardware. PVLDB
• M. Aguilera, J. Leners, and M. Walfish. Yesquel: scalable SQL storage for web applications.
• J. Levandoski, D. Lomet, S. Sengupta, R. Stutsman, and R. Wang. High performance transactions in deuteronomy. In CIDR 2015
• P. Bernstein, C. Reid, and S. Das. Hyder – A transactional record manager for shared flash. In CIDR 2011.
• M. Aguilera, A. Merchant, M. Shah, A. Veitch, and C. Karamanolis. Sinfonia: A new paradigm for building scalable distributed systems. ACM Trans. Comput. Syst
• CockroachDB: The Resilient Geo-Distributed SQL Database
• Contention-Aware Lock Scheduling for Transactional Databases
• Bridging the Archipelago between Row-Stores and Column-Stores for Hybrid Workloads
• The Case for Automatic Database Administration using Deep Reinforcement Learning
• Query-based Workload Forecasting for Self-Driving Database Management Systems
• Efficient Autoscaling in the Cloud Using Predictive Models for Workload Forecasting
• Automated Demand-driven Resource Scaling in Relational Database-as-a-Service
• SASH: a self-adaptive histogram set for dynamically changing workloads
• LEO - DB2’s LEarning Optimizer
• Continuous resource monitoring for self-predicting DBMS
• Oracle’s SQL Performance Analyzer
• Automatic Performance Diagnosis and Tuning in Oracle
• Adaptive self-tuning memory in DB2
• Integrating vertical and horizontal partitioning into automated physical database design
• Automated Selection of Materialized Views and Indexes in SQL Databases
• An Efficient Cost-Driven Index Selection Tool for Microsoft SQL Server
• A heuristic approach to attribute partitioning
• An Empirical Evaluation of In-Memory Multi-Version Concurrency Control
• Fast Serializable Multi-Version Concurrency Control for Main-Memory Database Systems
• High-Performance Concurrency Control Mechanisms for Main-Memory Databases
• Rethinking Database System Architecture: Towards a Self-Tuning RISC-Style Database System
• Decentralizing Distributed Consensus with Faster Paxos
• INDEX SELECTION IN ASELF-ADAPT WE RELATIONAL DATA BASE MANAGEMENT SYSTEM
• CRUSH: Controlled, Scalable, Decentralized Placement of Replicated Data
• Ocean Vista: Gossip-Based Visibility Control for Speedy Geo-Distributed Transactions
• Schema-Agnostic Indexing with Azure DocumentDB
• A comprehensive safety engineering approach for software- intensive systems based on STPA
• Meerkat: Multicore-Scalable Replicated Transactions Following the Zero-Coordination Principle
• Strong consistency is not hard to get: Two-Phase Locking and Two-Phase Commit on Thousands of Cores
• SLOG: Serializable, Low-latency, Geo-replicated Transactions
• Noria: dynamic, partially-stateful data-flow for high-performance web applications
• Noria A New Take on Fast Web Application Backends
• Calvin: Fast Distributed Transactions for Partitioned Database Systems
• Weighted Voting for Replicated Data
• Capturing global transactions from multiple recovery log files in a partitioned database system
• SSS: Scalable Key-Value Store with External Consistent and Abort-free Read-only Transactions
• What Goes Around Comes Around
• The BUCKY object-relational benchmark
• The Implementation of Postgres
• What’s Really New with NewSQL?
• Squall: Fine-Grained Live Reconfiguration for Partitioned Main Memory Databases
• Towards scalable real-time analytics: An architecture for scale-out of olxp workloads
• Rethinking main memory oltp recovery
• The end of an architectural era: (it’s time for a complete rewrite)
• NonStop SQL, a distributed, high-performance, high-availability implementation of sql

Hardware

• 🟢 What Every Programmer Should Know About Memory
• Meltdown: Reading Kernel Memory from User Space
• Spectre Attacks: Exploiting Speculative Execution

Linux

• Interrupt Handling in Linux
• New Scheduling Approaches for Linux OS
• Unikernels: The Next Stage of Linux’s Dominance

Network Protocols

• Is it Still Possible to Extend TCP?
• Fitting Square Pegs Through Round Pipes Unordered Delivery Wire-Compatible with TCP and TLS
• The QUIC Transport Protocol: Design and Internet-Scale Deployment

Testing

• Experiences with QuickCheck: Testing the Hard Stuff and Staying Sane
• Finding Race Conditions in Erlang with QuickCheck and PULSE
• Simple Testing Can Prevent Most Critical Failures: An Analysis of Production Failures in Distributed Data-Intensive Systems
• All File Systems Are Not Created Equal: On the Complexity of Crafting Crash-Consistent Applications

Blogs

Data Structures

• The Log: What every software engineer should know about real-time data’s unifying abstraction

Concurency

• Writing a seqlock in Rust
• Spinlocks Considered Harmful
• Mutexes Are Faster Than Spinlocks
• Measuring Mutexes, Spinlocks and how Bad the Linux Scheduler Really is
• I’m not feeling the async pressure
• Bounded Concurrent Time-Stamp Systems Are Constructible

Distributed Systems

• Turning the database inside-out with Apache Samza
• Change Data Capture: The Magic Wand We Forgot
• Bottled Water: Real-time integration of PostgreSQL and Kafka
• Using logs to build a solid data infrastructure (or: why dual writes are a bad idea)
• Eventually Consistent
• Strong consistency models
• Jepsen: MongoDB
• Consensus Protocols: Two-Phase Commit
• Exactly-once or not, atomic broadcast is still impossible in Kafka - or anywhere
• Exactly-once Semantics are Possible: Here’s How Kafka Does it
• Transactional Messaging in Kafka
• The Case Against Queues
• DBMS Musings
• Gray Failures
• Network Load Balancing with Maglev
• Living without atomic clocks

Linux

• How are Unix pipes implemented?

Software Development

• Revenge of the Nerds
• A Senior Engineer’s CheckList

Programming Languages

• No, dynamic type systems are not inherently more open
• Parse, don’t validate

Books

Distributed Systems

• Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems
• Database Internals: A Deep Dive into How Distributed Data Systems Work

After reading Database Internals

Papers

• Consistency Tradeoffs in Modern Distributed Database System Design: CAP is Only Part of the Story
• Heartbeat: a Timeout-Free Failure Detector for Quiescent Reliable Communication
• Atomic commit protocols, their integration, and their optimisations in distributed database systems
• Sequential consistency versus linearizability
• Coordination Avoidance in Database Systems
• Ubiquitous B-Tree
• On scalable and efficient distributed failure detectors
• On the relationship between the atomic commitment and consensus problems
• The Φ Accrual Failure Detector
• Crash Recovery in a Distributed Data Storage System
• Implementing linearizability at large scale and low latency
• ARIES: a transaction recovery method supporting fine-granularity locking and partial rollbacks using write-ahead logging
• A Quorum-Based Commit Protocol
• Consistent and Durable Data Structures for Non-Volatile Byte-Addressable Memory
• 🟠 The Many Faces of Consistency
• 🟠 Understanding Non-Blocking Atomic Commitment
• 🟠 Cache-Oblivious B-Trees
• 🟠 Cache-Oblivious Algorithms and Data Structures
• 🟠 Write-Optimized B-Trees
• 🟠 Architecture of a Database System
• 🟠 Efficient locking for concurrent operations on B-trees
• 🟠 Algorithms for scalable synchronization on shared-memory multiprocessors
• 🟠 Design Principles for Scaling Multi-core OLTP Under High Contention
• 🟠 Implementing a Better Cache Replacement Algorithm in Apache Derby Progress Report
• 🟠 A majority consensus approach to concurrency control for multiple copy databases
• 🟠 An Efficient Design and Implementation of LSM-tree based Key-Value Store on Open-Channel SSD
• Scalable Atomic Visibility with RAMP Transactions
• The promise, and limitations, of gossip protocols
• Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web
• The part-time parliament
• Paxos Made Simple
• Memory Ordering in Modern Microprocessors, Part I
• Memory Ordering in Modern Microprocessors, Part II
• A Digital Signature Based on a Conventional Encryption Function
• 🟢 LightNVM: the Linux open-channel SSD subsystem
• 🟢 Paxos made live: an engineering perspective
• 🟢 Spanner: Google’s Globally-Distributed Database
• 🟢 Memory Consistency Models of Modern CPUs
• 🟢 Flexible Paxos: Quorum intersection revisited
• 🟢 Redesigning LSMs for Nonvolatile Memory with NoveLSM
• 🟢 Generalized Consensus and Paxos
• 🟢 A Proof of Correctness for Egalitarian Paxos
• 🟢 Replicated State Machines without logs
• 🟢 Consistency in Non-Transactional Distributed Storage Systems
• 🟢 Don’t stack your Log on my Log

Blogs

• Distributed consistency at scale: Spanner vs. Calvin.
• 🟠 Linearizability versus Serializability
• Best of both worlds: Raft’s joint consensus + Single Decree Paxos
• 🟢 Sequential Consistency
• 🟢 Strong consistency models

Books

• Database System Concepts
• Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery
• Concurrency Control and Recovery in Database Systems
• Understanding the Linux Kernel. Third Edition
• Fundamentals of Database Systems
• Database Management Systems
• 🟠 Introduction to Reliable and Secure Distributed Programming
• 🟠 Distributed Operating Systems: Concepts and Design
• 🟠 Modern Operating Systems
• 🟠 Distributed Systems: Principles and Paradigms