Contents

Part I  Foundations of Data Systems

Chapter 1  Reliable, Scalable, and Maintainable Applications／可靠性、可扩展性、可维护性应用 3

Thinking about Data Systems／数据系统深思 5

Reliability／可靠性 8

Hardware Faults／硬件错误 10

Software Errors／软件错误 11

Human Errors／人为错误 13

How Important Is Reliability?／可靠性有多重要? 14

Scalability／可扩展性 15

Describing Load／负载描述 15

Describing Performance／性能描述 19

Approaches for Coping with Load／应对负载的方法 24

Maintainability／可维护性 27

Operability: Making Life Easy for Operations／可操作性：人生苦短，关爱运营 28

Simplicity: Managing Complexity／简单性：复杂度管理 30

Evolvability: Making Change Easy／可演化性：拥抱变化 31

Summary 32

References 34

Chapter 2  Data Models and Query Languages／数据模型与查询语言 37

Relational Model Versus Document Model／关系模型与文档模型 39

The Birth of NoSQL／NoSQL的诞生 40

The Object-Relational Mismatch／对象关系不匹配 41

Many-to-One and Many-to-Many Relationships／多对一和多对多的关系 45

Are Document Databases Repeating History?／文档数据库是否在重蹈覆辙？ 49

Relational Versus Document Databases Today／如今关系数据库和文档数据库的比对 53

Query Languages for Data／数据查询语言 59

Declarative Queries on the Web／Web上的声明式查询 62

MapReduce Querying／MapReduce查询 64

Graph-Like Data Models／图数据库模型 68

Property Graphs／属性图 71

The Cypher Query Language／Cypher查询语言 73

Graph Queries in SQL／SQL中的图查询 76

Triple-Stores and SPARQL／三元组存储和SPARQL 78

The Foundation: Datalog／Datalog基础 84

Summary 88

References 90

Chapter 3  Storage and Retrieval／存储与检索 93

Data Structures That Power Your Database／驱动数据库的数据结构 94

Hash Indexes／哈希索引 97

SSTables and LSM-Trees 102

B-Trees 108

Comparing B-Trees and LSM-Trees 113

Other Indexing Structures 116

Transaction Processing or Analytics? 123

Data Warehousing 125

Stars and Snowflakes: Schemas for Analytics 128

Column-Oriented Storage 131

Column Compression 133

Sort Order in Column Storage 136

Writing to Column-Oriented Storage 138

Aggregation: Data Cubes and Materialized Views 138

Summary 141

References 143

Chapter 4  Encoding and Evolution／编码与演化 147

Formats for Encoding Data／数据编码格式 149

Language-Specific Formats／语言特定格式 150

JSON, XML, and Binary Variants／JSON、XML和二进制变体 152

Thrift and Protocol Buffers 157

Avro 163

The Merits of Schemas／模式的优势 171

Modes of Dataflow／数据流的类型 173

Dataflow Through Databases／数据库中的数据流 174

Dataflow Through Services: REST and RPC／服务中的数据流：REST与RPC 177

Message-Passing Dataflow／消息传递中的数据流 186

Summary 190

References 193

Part II  Distributed Data

Chapter 5  Replication／复制 197

Leaders and Followers／领导者与追随者 199

Synchronous Versus Asynchronous Replication／同步复制与异步复制 200

Setting Up New Followers／设置新的从库 203

Handling Node Outages／宕机节点的处理 204

Implementation of Replication Logs／复制日志的实现 208

Problems with Replication Lag／复制延迟问题 212

Reading Your Own Writes／读写一致性 214

Monotonic Reads／单调读 217

Consistent Prefix Reads／一致前缀读 218

Solutions for Replication Lag／复制延迟的解决方案 220

Multi-Leader Replication／多主复制 221

Use Cases for Multi-Leader Replication／多主复制的应用场景 222

Handling Write Conflicts／处理写入冲突 227

Multi-Leader Replication Topologies／多主复制拓扑 232

Leaderless Replication／无主复制 235

Writing to the Database When a Node Is Down／当节点故障时写入数据库 236

Limitations of Quorum Consistency／仲裁一致性的局限 241

Sloppy Quorums and Hinted Handoff／松散法定人数与带提示的接力 244

Detecting Concurrent Writes／检测并发写入 247

Summary 257

References 260

Chapter 6  Partitioning／分区 263

Partitioning and Replication／分区与复制 265

Partitioning of Key-Value Data／键值数据分区 266

Partitioning by Key Range／根据键的范围分区 267

Partitioning by Hash of Key／根据键的散列分区 269

Skewed Workloads and Relieving Hot Spots／负载倾斜与热点消除 271

Partitioning and Secondary Indexes／分片与次级索引 272

Partitioning Secondary Indexes by Document／文档二级索引 273

Partitioning Secondary Indexes by Term／关键词二级索引分区 275

Rebalancing Partitions／分区再平衡 278

Strategies for Rebalancing／平衡策略 278

Operations: Automatic or Manual Rebalancing／运维：手动平衡VS自动平衡 284

Request Routing／请求路由 285

Parallel Query Execution／执行并行查询 288

Summary 289

References 291

Chapter 7  Transactions／事务 293

The Slippery Concept of a Transaction／事务的难以明确的概念 295

The Meaning of ACID 296

Single-Object and Multi-Object Operations／单对象与多对象操作 302

Weak Isolation Levels／弱隔离级别 309

Read Committed 311

Snapshot Isolation and Repeatable Read／快照隔离与可重复读 315

Preventing Lost Updates／防止丢失更新 323

Write Skew and Phantoms 329

Serializability／可序列化 336

Actual Serial Execution 337

Two-Phase Locking (2PL) 344

Serializable Snapshot Isolation (SSI) 350

Summary 357

References 360

Chapter 8  The Trouble with Distributed Systems／分布式系统的烦恼 365

Faults and Partial Failures／故障和部分失败 367

Cloud Computing and Supercomputing 369

Unreliable Networks／不可靠的网络 372

Network Faults in Practice 375

Detecting Faults 376

Timeouts and Unbounded Delays／超时和无限延迟 378

Synchronous Versus Asynchronous Networks／同步vs异步网络 383

Unreliable Clocks／不可靠的锁 387

Monotonic Versus Time-of-Day Clocks 389

Clock Synchronization and Accuracy 391

Relying on Synchronized Clocks 393

Process Pauses 400

Knowledge, Truth, and Lies／知识、事实和谎言 407

The Truth Is Defined by the Majority 408

Byzantine Faults／拜占庭故障 414

System Model and Reality／系统模型和实际情况 419

Summary 425

References 428

Chapter 9  Consistency and Consensus／一致性和共识 433

Consistency Guarantees 435

Linearizability／线性一致性 437

What Makes a System Linearizable? 440

Relying on Linearizability 446

Implementing Linearizable Systems 450

The Cost of Linearizability 453

Ordering Guarantees 459

Ordering and Causality 460

Sequence Number Ordering 466

Total Order Broadcast 473

Distributed Transactions and Consensus 479

Atomic Commit and Two-Phase Commit (2PC) 481

Distributed Transactions in Practice 490

Fault-Tolerant Consensus 497

Membership and Coordination Services 506

Summary 511

References 515

Part III  Derived Data

Chapter 10  Batch Processing／批处理 523

Batch Processing with Unix Tools／批处理与Unix工具 526

Simple Log Analysis 527

The Unix Philosophy 530

MapReduce and Distributed Filesystems／映射-规约和分布式文件系统 536

MapReduce Job Execution／映射-归纳的任务执行 538

Reduce-Side Joins and Grouping／归约阶段的连接和分组 545

Map-Side Joins 553

The Output of Batch Workflows／批处理流的输出 556

Comparing Hadoop to Distributed Databases 563

Beyond MapReduce／映射-规约之外 569

Materialization of Intermediate State／中间状态的具体化 570

Graphs and Iterative Processing 577

High-Level APIs and Languages 581

Summary 585

References 589

Chapter 11  Stream Processing／流处理 593

Transmitting Event Streams／传递时间流 595

Messaging Systems／消息系统 597

Partitioned Logs／分区日志 606

Databases and Streams／数据库与流 613

Keeping Systems in Sync／保持系统同步 614

Change Data Capture／变更数据捕获 617

Event Sourcing／时间溯源 622

State, Streams, and Immutability／状态、流和不变性 626

Processing Streams／流处理 633

Uses of Stream Processing／流处理的应用 635

Reasoning About Time／时间推理 642

Stream Joins／流式连接 649

Fault Tolerance／容错 655

Summary 660

References 663

Chapter 12  The Future of Data Systems／数据系统的未来 669

Data Integration／数据集成 670

Combining Specialized Tools by Deriving Data／组合使用衍生数据的工具 671

Batch and Stream Processing／批处理与流处理 679

Unbundling Databases／分拆数据库 687

Composing Data Storage Technologies／组合使用数据库存储技术 688

Designing Applications Around Dataflow／围绕数据流设计应用 696

Observing Derived State／观察衍生数据状态 705

Aiming for Correctness／将事情做正确 715

The End-to-End Argument for Databases／为数据库使用端到端的参数 717

Enforcing Constraints／强制约束 724

Timeliness and Integrity／及时性和完整性 730

Trust, but Verify／信任但验证 738

Doing the Right Thing／做正确的事 746

Predictive Analytics／预测性分析 747

Privacy and Tracking／隐私和追踪 752

Summary 764

References 767

XII

设计数据密集型应用

XIII

Contents