写在前面
最早听说这本书，是公司一位大拿的推荐，当时还特别提到了微软CTO的推荐语是：
This book should be required reading for software engineers. Designing Data-Intensive Applications is a rare resource that connects theory and practice to help developers make smart decisions as they design and implement data infrastructure and systems.
后来在不同的地方听到不同的人推荐过。这本书读下来总体感觉：
- 覆盖得非常全面、系统，所涉及的知识点不会特别地深入
- 作者对工程上的细节比较清晰
所以推荐给想对数据相关的系统软件（数据库、缓存 、消息队列等等）有一个全面的了解的同学。
这篇笔记主要目的是为了记录一下，避免自己把花了一个多月读完的这本书忘得一干二净了。
全文分为了三章，第一章的题目是Foundations of Data Systems。 这一章的内容作者分为了四个小节：
Reliable, Scalable, and Maintainable Applications。作者认为在软件系统中非常重要的3点，然后在这一小节中详细地描述了这3点。特意地把可维护放到和可靠可扩展一样重要的程度，可维护性里面包含了可运维性，这个和Tair工程团队现在产品开发的哲学是相通的：管控功能属于系统设计时必不可少的一部分，。Data Models and Query Languages。讲了Relational和Document两种数据模型的纷争历史，数据对应的查询语言，图数据模型。Storage and Retrieval。先是介绍了主索引的结构，着重提了B-Trees和LSM-Trees；然后是TP和AP；最后讲的是列式存储。Encoding and Evolution。讲了一些编码方式，然后提到了数据流，数据流会是作者后面非常强调的一个思路。
Reliable, Scalable, Maintainable
开宗明义，提出了很多软件系统中重要的三个关注点：
- 可依赖性。系统能够正确地工作，即使在有异常发生的时候。主要强调的是系统的健壮性、高可用性。
- 可扩展性。当系统的数据量、流量、复杂性变化时，能够以合理的方式扩展。分布式系统的基本要求，目前的软件版本需要满足可预见的时间内的扩展需求，需要对其中每一个组件的可扩展性有非常仔细的考量。
- 可维护性。系统可以让后面不断加入的人员能够在其中卓有成效地工作。可维护性强调的并不单纯是运维上的友好，更多地是系统需要结构清晰，让后面的工程的演进变得更容易，而不是遇到一些需求的时候必须把之前的推倒重来。
Reliability
fault和failure的区别。fault是指单个组件工作异常，比如说硬盘损坏，内存错误；failure是指整个系统对外服务能力的中断。所以系统需要做到fault-tolerance，从而避免failure。
故意地提高错误发生的机率可以持续地检测系统的fault-tolerance机制。
虽然通常情况下我们倾向于容忍错误而不是预防错误，但是在有些case下预防错误比处理错误要好（可能有些错误是没法处理的，造成的影响是不可逆的）。
Hardware Faults
对于硬件故障（硬盘坏、RAM坏等），我们的第一反应是给每个组件加上冗余，比如：使用RAID、双路电源、Hot-swappable CPUs（这种部件在互联网的部署中不多见）、在数据中心中准备柴油发电机。这种方法可以有效地降低故障率。
随着数据存储容量和业务计算量的增加，机器数目也开始增加，所以故障次数也会增加。现在越来越倾向于在软件上使用fault-tolerance的技术来替代或者辅助硬件冗余，这样系统就可以容忍整台机器的失效。这样的系统也会有运维上的好处：可以使用rolling update等方式来重启系统中所有的机器，如果只有单点时，需要向使用方告知planned downtime。
Software Faults
我们通常认为硬件错误相互之间是随机独立的，某些情况下可能会有弱相关性（比如一个机柜的温度升高），但通常不会大量的硬件部件在同一时刻发生错误（这里面也有tricky的地方，比如硬件的firmware按道理上来讲，也是软件。从应用开发者的角度，它们属于硬件的一部分，但是可能会同时发生错误）。
软件错误（bug）是很难被预测到的，而且会导致多个节点同时发生错误。这些bug通常会潜伏比较长的时间，直到在一个特定的场景下被触发。对于软件错误并没有快速的解决方式，只有靠一系列非常小的点来保证：仔细思考系统中的假设和交互；完善全面的测试；进程隔离；容忍进程崩溃和重启；在生产环境中度量、监控、分析系统行为。
Human Errors
这里人为错误指的是运维中人造成的错误。人是不可靠的，即使有最好的动力。据一些统计表明，服务中断的最主要原因就是运维人员的配置错误。
- 设计系统时让出错的概念降到最低。
- 把人们容易犯错误的地方和他们会导致故障的地方解耦开。
- 全面的测试。
- 建立完善清晰的监控。
- 实施良好的运维培训。
Reliability的重要性
Reliability不止是对核电站或者飞行控制系统比较重要，一些不那么致命的程序的Reliability也非常重要，比如说电商网站服务的中断会导致收入下降和名誉受损。
当然，有些情况下，我们会牺牲稳定性来降低开发或运维成本，但是我们需要清醒地意识到自己在走捷径。
Scalability
一个系统在当前的阶段正常运行，不意味着在以后也会。扩展的增长可能会导致系统降级。可扩展性是针对系统而言的，而不是针对某一个模块。
负载描述
我们需要简洁地描述系统当前的负载，只有这样，我们才能够讨论负载增长。负载可以使用一些数字来描述，这些数字我们可以称为“load parameters“，“load parameters“的选择取决于系统的架构。
性能描述
对于批处理系统，我们用throughput来描述性能；而对于一些在线系统，我们会用response time来描述性能。
这里作者试图说明latency和response time在概念上的区别，但是在我们的日常工作中还是会把这两者当成是同义词。作者说latency是请求的等待时间。
然后在描述response time时引入了P99相关的概念，这些概念在service level objectives (SLOs)和service level agreements (SLAs)中经常会被使用到。
排队延时是造成长尾延时的原因之一。取决于服务器的并发度，系统只能并行处理一部分请求，然后会阻塞后续的请求，这也被称为”head-of-line blocking”。在我们制造负载来测试系统的可扩展性时，需要异步地发送请求，因为如果同步地发送请求的话，会导致队列长度比实际情况要短。
应对负载的变化
应对负载的变化 ，最直观的方法就是扩容。扩容的路径，一般会二分为scale up和scale out。某些系统是具备弹性的，在负载增加时它们可以自动地增长计算资源，而其它的系统需要手动地进行调整，但它们被认为可以更直观地进行维护。
相对于单点系统，分布式系统在可扩展性上会更灵活，这一章剩下的内容会介绍分布式在可维护性上的好处。
对于某一个特定系统设计的可扩展架构 ，通常是基于假设：哪些操作是常见的，哪些操作是稀有的。如果这个假设错了，那么在扩展性上的工程努力有可能会适得其反。
虽然可扩展性架构对于特定的应用是不一样的，但是一些通用的“积木”，有着类似的模式。
Maintainability
软件的绝大部分成本不在于初始的开发，而在于后续的维护：修bug、让系统可运维、排查问题、适配新平台、为新的场景做修改、还技术债、增加新的功能。
不幸地是，软件开发者不喜欢维护继承下来的系统：legacy systems，因为这样感觉像在给别人擦屁股 。在设计软件时，我们需要降低维护的困难，这样我们就不会自己制造legacy systems。有以下三个设计准则可以让我们达到这个目的：
- Operability，方便维护
- Simplicity，易于理解
- Evolvability，便于演进
Operability: Making Life Easy for Operations
good operations can often work around the limitations of bad (or incomplete) software, but good software cannot run reliably with bad operations
一些方面的运维操作可以而且需要被自动化，但是需要人来把自动化流程建立起来，而且保证它能够正常工作。
高度的可运维性意味着让日常的工作变得容易，这样运维团队就可以专注在一些更高价值的工作上。要达到这个目的，数据系统能够做的事情很多：
- 提供运行时行为和内部状态的可视化
- 提供自动化和外部标准工具结合的良好支持
- 避免对单一机器的依赖
- 提供完善的文档和易于理解的运维模型
- 提供好的缺省配置
- 在合适的条件下能够自愈，并且提供手动控制系统状态的方式
- 展现可预期的行为
Simplicity: Managing Complexity
当工程变得越来越大时，就会变得复杂和难以理解。这种复杂性会增加系统维护者的难度，增加维护成本。复杂度陷入泥潭的软件有时候被称为“a big ball of mud”。
软件复杂性的症状很多：状态非常多、模块的紧耦合、没用的依赖、不一致的命名和术语、为了解决性能问题的一些hack、为了解决特定问题的if-else。
降低复杂性可以极大地提高软件的可维护性，所以简洁性是我们打造系统的一个重要的目标。把系统变得简单并不意味着会丧失功能，可以意味着移除“附加的复杂度”。如果复杂度不是软件解决的问题带来的，而是特定的实现引入的，那么这样的复杂度就可以被称为“附加的复杂度”。为了移除这种复杂度，我们可以在软件中做更好的“抽象”。
Evolvability: Making Change Easy
对系统的重构在软件开发的过程中是必不可少的，因为软件运行的环境总是在不断地变化的，所以系统必须具备很强的可演进的能力。这个能力和系统的简洁性是紧密相关的。
Data Models and Query Languages
The limits of my language mean the limits of my world.
数据模型在软件开发中是非常重要的，因为它不仅会影响我们如何编写软件，也会影响我们怎么看待要解决的问题。
这一章节讲了关系型模型和文档模型在历史上的一些演进，然后两者在今天的应用场景上的区别：
- 使用哪种模型可以让应用的代码更简洁
schema的灵活型。这里作者强调了文档数据库并不是schemaless，而是schema-on-read，那些强schema的，可以认为是schema-on-write，这个听起来很有道理- 查询的数据局部性。对于文档型数据库来说整个文档的数据是存在一起的，如果写入会改变整个文档的大小，就会发生
rewrite。但是对于关系型数据库来说，不也是如此么？ - 文档型数据库和关系型数据库的集合。关系数据库开始支持
JSON，文档型数据库开始支持join语法，数据模型在互相补充彼此。
接着作者讲了对应的查询语言，摆出了两类查询语言：声明式和过程式语言，简单来看，声明式只标明了API，没有给明实现；而过程式是直接把实现都写明了。所以声明式语言给实现者的空间会更大。
Mongodb中之前使用MapReduce的方式，更像是过程式语言，需要在函数里面把实现都定义好。后面开始引入aggregation pipeline，看起来就更像是声明式语言。作者听起来像是SQL的忠实粉丝，但奇怪的是他好像并不是太喜欢MySQL。
Note there is nothing in SQL that constrains it to running on a single machine, and MapReduce doesn’t have a monopoly on distributed query execution.
SQL是可以支持分布式查询的，嗯，至少API层面没有限制它是单机的。
Being able to use JavaScript code in the middle of a query is a great feature for advanced queries, but it’s not limited to MapReduce—some SQL databases can be extended with JavaScript functions too
在查询中使用JavaScript代码并不是Mongodb发明的，在Postgre中也是有这样的使用的。
对于实体之间关系特别多的场景，图模型就比较合适了。对于图模式，作者提出了两种不同的类型：
property graph，把图分为点和边来组织，比如Neo4j、Titan等triple-store，只存放关系，比如Datomic、AllegroGraph等
对于我们通常的理解而言，都是针对property graph的。这两种模型这有什么优缺点呢？
针对图数据库的查询语言，有声明式的：Cypher, SPARQL, Datalog，也有过程式的Gremlin。把Gremlin定义为过程式的查询语言感觉是很奇怪的，对于我而言，更像是声明式的语言。
在描述triple-store的过程中，作者引入了semantic web和Resource Description Framework (RDF)。
除了上面提到的关系型、文档和图模型，还有很多其它模型，比如：
- 基因研究中，通常会做
sequence-similarity searches，序列相似度查询。类似于GenBank的特殊基因数据库软件服务于这种场景 - 像
Large Hadron Collider (LHC)这样的工程会产生数百PB的数据，粒子物理学家需要对这些数据做分析 - 全文检索
Storage and Retrieval
If you keep things tidily ordered, you’re just too lazy to go searching.
这一章讲了存储的索引相关的内容，Hash、LSM和B-Tree，解析了各自的优缺点。
Hash
对于Hash，最有名的实现应该是Bitcask了。对于点查询是非常快的，因为hashmap是保存在内存中的。Hash的想法很简单，但是实现中通常需要考虑到如下因素：
- File format
- Deleting records
- Crash recovery
- Partially written records
- Concurrency control
使用append-only的日志，而不是in-place的写，出于以下几点考虑：
- 追加写对性能更好
- 原地写对并发和恢复都不友好
merge文件可以避免碎片
这种索引方式的限制是：hash table需要常驻内存中；对于范围查询不友好。
LSM
使用SSTable (Sorted String Table)来组织数据，这种方式被Leveldb/Rocksdb/Hbase/Cassandra使用。Log-Structured Merge-Tree (LSM-Tree)在1996年被提出，是基于1992 年的log-structured filesystem的。
SSTable压缩和合并的策略可以分为：size-tiered和leveled两种。leveled可以让compact过程中占用的空间更少，相当于把compact的输入文件做了分裂；size-tiered，可以让最终的空间放大变得更小，而且对于读放大可能是有好处的，这点不太能确认。
B-Trees
1970年被引入，然后在10年之后变得无处不在，B-trees明显经历过了更长时间的考验。
LSM将数据库支解为变长的段：SSTable。B-trees把数据库支解成定长的blocks和pages，这跟底层的硬件结合得更加紧密。B-tree也会借助WAL来保证写入的可靠。B-trees的优化可以有以下几个方面：
- 可以使用
copy-on-write的方法，而不是借助原地更新和WAL的方法组织B-tree。LMDB就是这样做的，而且这样做对并发也是有好处的。 - 对于内部页，可以容纳更多的
key，这样可以提高branching factor，从而减少层数。 - 很多
B-tree会让相邻的叶子节点在物理空间上更可能地连续，但这一点并不好保证，而LSM Trees就能很好地做到这一点。 - 叶子节点中增加额外的指针指向前后的其它叶子节点（
B+ Tree）。 B-tree的变种fractal trees也借用了一些LSM的想法。
其它的一些索引
这里作者先提到了二级索引，和主键索引不同的是，二级索引的同一个key可能对应着多个value。这种场景一般来说，有两种解决方案：
- 对某一个特定的
key，维护一个value列表，就像multimap - 对于每一个
key，追加一个特定的标志符构成一个组合key
在索引中存储value
对于二级索引而言，要么存放冗余的原始记录，要么存放原始记录的指针。第二种方法中数据存放的地方被称为heap file，二级索引中的value都是指向heap file 中的偏移的。
如果heap file中原始数据有更新，特别是更新的记录比原来大，不能原地更新时，要么所有的索引都需要更新相应的值，要么让原来的偏移指向新的偏移。
存储冗余的原始记录的索引又可以称为clustered index，在MySQL Innodb引擎中，表的主键索引就一定是clustered index。
有一种在clustered index和nonclustered index之间的折衷，我们称之为covering index或者index with included columns，这种索引只会存入原始记录的一部分在索引中。
多列索引
最常见的多列索引是联合索引，Multi-dimensional indexes可以用来同时查找多列的值，比如说在geospatial中会用到的查询。 HyperDex中使用的2D index也可以达到类似的效果。
全文搜索和模糊索引
前面讲的都是查询键能够精准匹配的，但是类似于Lucene这样的索引需要支持模糊的查询，Levenshtein automaton，可以搜索到和查询键的编辑距离在一定范围内的记录。
内存索引
Further changes to storage engine design will probably be needed if non-volatile memory (NVM) technologies become more widely adopted. At present, this is a new area of research, but it is worth keeping an eye on in the future.
数风流人物，还看NVM
Encoding and Evolution
对于编码方式，我们比较关注兼容性问题：
- 向后兼容：新的代码能读到旧代码写入的数据
- 向前兼容：旧的代码能读到新代码写入的数据
向后兼容是非常好保证的行为，但是向前兼容的能力需要编码方式从最终的设计上就开始保证。只有保证了这两种兼容性，系统的升级才可能平滑。
作者介绍了几种编码的格式：
- 语言自带的编码格式，被限制在同一个语言内，通常不具备向前向后的兼容性
JSON、XML、CSV这些文本格式的兼容性需要靠使用方自己来确保的，格式本身没有提供相应的机制- 二进制格式：
Thrif、Protocol Buffers、Avro这些编码格式占用的空间少，而且提供了完善的向前向后兼容的机制，唯一劣势就是可读性不强
对于编码方式的选择而言，弄清楚数据的流动模式也是很重要的。