最近读完了 Designing Data-Intensive Applications，这本书从实际工程的角度出发，全方位地剖析了现代系统与数据的关系和各种技术背后的设计思想，为我们分析了每种设计天生所带来的优势劣势以及为了适用不同使用场景上所作出的权衡。此系列文章是对该书内容的一些总结和精炼。
前言
近些年服务端或者后端系统都被存储与处理数据这两个目标带来的问题围绕。我们可以将这样的一个应用称作数据密集型应用(Data-intensive applications)，这个应用的首要挑战是数据，包括数据量，数据复杂性以及数据变化的速度。
以下一些条件推动了构建数据库、分布式系统或者基于前二者的应用上的发展。
- 互联网公司有着海量数据与流量需要处理，使得他们必须找出一种能高效处理如此大规模数据的新工具
- 业务需要更加敏捷，为了快速响应市场必须缩短开发周期并且保持数据模型的灵活
- 开源软件行业更加成功，并且被大量使用在商业环境中
- CPU的速度增长减缓，“The free lunch is over”, 而多核处理器与网络却在高速发展，并行处理成为了唯一增加性能的方式
- IaaS使得构建在多台甚至跨地理区域的多台机器的系统更加容易
- 服务对高可用性要求更高
过去的十年间，为了帮助数据密集型应用响应存储与处理数据的需要，NoSQL, Big Data等等新兴技术出现了爆炸式增长，消息队列、缓存、搜索索引、批处理与流处理框架等等工具被使用在实战中。
在如此多技术中选出适合自身需求的工具成为新的烦恼，但是只需要记住“There are no silver bullets.” 这一条经典法则即可。这些不同的工具不过是不同目标导致设计理念上差异化带来的结果，因此它们有自己独特的优势，也一定会因为一些局限性做出了trade-offs。
数据系统的基石
可靠的，可伸缩的，可维护的应用
一个数据密集型应用都会代表性地包括一些基本的标准模块，这样标准的模块都会提供一些必要的功能。举例来说，许多应用都需要
- 存储数据，过后该应用或者其它应用能够再次读取数据(数据库)
- 记录一些需要较高开销操作的结果，加速读取速度(缓存)
- 让用户可以通过关键词搜索数据或者过滤数据(搜索索引)
- 向另外的进程发送可以被异步处理的消息(流处理)
- 周期性地处理大量累积数据(批处理)
当我们使用这些工具构建自己的服务时，API为我们隐藏了这些工具实现的细节。而我们的目标是实现一个好的服务，那么什么可以算上一个好的服务呢？
在大多数软件系统中，我们应该集中关注以下3点
Reliability 可靠性
可靠性是指系统可以在异常情况下按照期望(一定的等级)继续正确地工作。Scalability 可伸缩性
随着系统不断增长(数据容量，流量，复杂性)，系统能够处理这些增长的需求并且依然保持较高性能。Maintainability 可维护性
不同人员或者团队在该系统上进行工作时，系统能使得协同工作更加容易。
Reliability
对一个系统可靠性典型的期望应该是
应用可以按用户期望的目标完成功能
系统可以容忍用户犯错或者用一种意外的方式去使用软件
在预想的负载与数据容量下，系统性能足以满足用户用例
系统阻止任何无权限的访问或者恶意操作
错误(fault)是指一些事情弄错了(go wrong)，而我们的容错机制(fault-tolerant)是指在一定程度上容忍错误的发生，这不意味着我们能完全解决所有错误，假如整个地球都被黑洞吞噬，那么显然在这种条件下错误是不可能可以解决的。因此我们只能容忍一定程度上的错误。
错误(fault)和失败(failure)不同，错误是指系统的一些部件偏离了它们的正常使用，而失败是指整个系统都完全无法向用户提供需要的服务。
Reliability需要解决硬件错误(Hardware Faults)、软件错误(Software Errors)、人为错误(Human Errors)。
硬件错误可以通过冗余(redundancy)等手段来解决。
软件错误没有较快的解决方法，但是可以通过设计时仔细的思考、测试、进程隔离、允许进程崩溃并重启、测量(measuring)、监控(monitoring)或者分析系统等等方式来处理。
人为错误一般可以通过抽象(abstractions)、将最容易出错的地方解耦(decouple)、各个级别的测试(test)、快速恢复机制(quick and easy recovery)、监控(monitoring)、良好的管理(management)帮助解决。
Scalability
我们首先能给出系统当前的负载状态，比如100k requests/sec，然后我们能根据新的需求去决定负载指数(load parameter)。
一些术语：
吞吐量(throughput)：我们每秒能处理的请求的数量
延迟(latency): 请求等待被处理这个过程的时间
响应时间(response time): 处理整个请求的时间(包括网络延时以及处理队列延时)
百分位(percentile): 给出一定性能条件，满足这个条件所占的百分比
通常有两种解决方案
- 垂直扩展(scale up): 使用更加强大性能的机器
- 水平扩展(scale out): 将负载均摊到多个更小的机器上
scale up在一定条件下有用，但是它不是无限增加的，单个机器的性能是有限的，CPU也不可能无限提高自身的性能，而且高性能的机器会带来昂贵的成本，因此scale out成为了另一种更可行的解决方法。
Maintainability
以下三点都是系统设计在可维护性上需要考虑的
可操作性(Operability): 团队操作更加容易
简易性(Simplicity): 对于新手更加友好
可进化性(Evolvability): 即可扩展性(extensibility)，未来系统修改时更加容易
数据模型与查询语言
数据模型
关系型数据模型(Relational Model)已经经历住了时间的考验，并且成为了最为熟知的数据模型，SQL也获得了巨大的成功，关系型模型在1970年就已经提出：数据由关系(SQL中的表)来组织，每个关系就是一系列元组(tuple,SQL中的行row)的无序集合。
NoSQL = Not Only SQL
NoSQL由以下需求驱动
- 比关系型数据库更好的伸缩性
- 拥抱开源软件而不是商业数据库产品
- 提供关系模型不支持的查询操作
- 针对关系型数据模式(schema)的局限性，需要更加灵活和具有表达力的数据模型
阻抗失配(Impedance mismatch): 应用代码中的对象与数据库模型中的表、行、列之间需要一个映射层，而不是直接对应的关系。
文档型数据模型(Document Model)将数据形成自独立(self-contained)的文档，文档之间的关联比较少。
图数据模型(Graph Model)将所有事物都看做是有关系的，它们(顶点vertice)之间通过边(edge)来关联。
关联
通常有三种关联需要处理
一对一关联(One-To-One)
一对多关联(One-To-Many)
关系型模型或者层次文档模型多对多关联(Many-To-Many)
查询语言
- SQL
- MapReduce Query
- Aggregation pipeline
- Graph Query
关系(relational)、文档型(document)、图(graph)三种模型都有自己的使用场景。
存储与检索
在最基本的角度来看，一个数据库需要做两件事：你给它一些数据，它将数据存下来；你过一段时间找它要这些数据，它会将数据返回给你。
索引
为了在数据库中高效率地找出一个指定的关键字，我们需要一种数据结构：索引。索引背后基本的思想就是为存储的数据再多余保存一些元数据(metadata)，这个元数据就好像指示牌一样能帮你过后找到存储的数据。索引只是原始数据衍生出的额外结构，它并不会影响原始数据本身，它只会影响查询原始数据时的速度。任何索引都会降低写数据的速度，因为每次写数据时都会更新索引，而这些索引是额外的内容。在存储系统中有一个重要的trade-off，适当的索引会加速查询读的速度，但是每个索引都会降低写的速度，因此，数据库通常不会为每一个存储的数据建立索引。
Hash index
最简单的一种Hash索引就是在内存中保存一个Hash表，里面存着每个key以及对应数据的字节偏移量，当需要查询值时，就用这个哈希表通过偏移量找出该key所对应的数据文件中对应值得位置，然后读出。写入值时就采用append-only顺序写入(sequential write)的方式。
因为我们在不断顺序写入，为了避免用光所有空间，一种可行的解决办法是，将这个顺序写入的记录(log)拆分成若干固定大小的段(segment)，当一个段写满时，就停止写入并且开启下一个段。接着我们就能对这些段进行压缩合并操作(compaction)，compaction就是将记录中重复的key丢弃只保留最新更新的那个key。
append-only只追加数据这种方式看起来比较浪费，为什么不直接去将对应旧值替换成新值呢？
- 由于追加(append)与段合并(segment merging)都是顺序写操作，这种方式比随机写速度要快很多，在磁盘上表现尤其明显
- 并发写与崩溃恢复(crash recovery)更加简单，因为段文件是只可以追加的，你不用担心部分旧值与部分覆盖的新值混合在一起的情况
- 合并旧的段避免了数据文件随着时间带来的碎片化(fragment)
然而，这种hash table index也有一些限制
hash table必须能适合内存大小，如果keys非常大的话，那么就有问题了。而将hash map存在磁盘上性能会大大降低
范围查询低效
SSTable
前面讲的index模型就是一个顺序的key-value集合，这些kv对的顺序就是它们被写入时的顺序，因此在这种结构中并没有考虑顺序。
现在做出一些改变，我们要求kv对的顺序是按照key来进行排序。这种形式叫作Sorted String Table(SSTable)
先来看看这种方式有什么优势
- 合并段(segment)更加高效了，因为我们的segment都是有序的，所以只需要对每个segment逐个复制合并即可。
- 我们现在不需要在内存中保存所有的key了，因为kv是有序的，只需要保存一部分key，这样我们就可以通过两个索引的key确定要查找的kv的范围，然后再查找，这样速度就非常快了，而且还节省了索引占用空间。
- 还可以将两两key间隔的范围对应的数据进行压缩成块进行存储，这样也节省了磁盘空间和io带宽。
在内存中保持一个顺序结构十分容易，可以使用平衡树这种数据结构来实现。我们现在的存储引擎工作方式是这样的：
- 写请求来时，将它加入到一个内存中的平衡树的数据结构，这个数通常叫作memtable
- 当memtable大小超过一定限额时，把这个memtable写入到磁盘中，并且提供一个新的memtable实例去继续提供写功能
- 读请求来时，首先查询memtable中的key，然后到最近更新的磁盘上的segment，接着按时间顺序一直找下去
- 同时在后台开启一项进程对segments进行合并与压缩操作
这种模式还有一个问题，如果数据库崩溃了，那么memtable中还没有写入磁盘的数据就丢失了。为了避免这个问题，可以在磁盘上保持一个分离的日志，这个日志会记录每次写的信息，在崩溃后恢复时可以找回memtable，而每次memtable被写到SSTable中时，这个日志就可以丢弃掉并重新用一份新的。
LSM-Tree
上面这种索引结构被叫做Log-Structured Merge-Tree(LSM-Tree)，而基于合并与压缩分类文件这种思想的存储引擎通常被叫做LSM存储引擎。
这种引擎在实战中还有很多可以优化的细节，比如增加一个Bloom filters来检测要查询的key是否存在，这样如果该key不存在就不需要查询整个segments了。
LSM-Trees的基本思想就是保持一个级联的SSTables，并且让它们在后台合并。这种方式能处理数据集比可用内存更大的情形，而且由于数据是有序的，因此可以使用范围查询，而且写操作也是顺序的，因此可以满足高吞吐的要求。
B-Tree
B-Tree是使用最广泛的索引结构。和SSTables相似，B-tree的KV对也是按key来排序的，这样查询值和范围查询时会更高效。但是B-Tree和SSTables在设计思想上还是有很大不同的地方，SSTables的段(segments)是变长的，并且是顺序写(sequential write)，而B-Tree是将数据划分为块(block)或者页(page)，块是定长的，并且一次只会读写一个块，每个块都会用固定的标识符标识，这样就能通过标识符找到对应的块。B-Tree的块会指向更深层次的块，类似指针，这样能缩小查询时的范围，并且B-Tree会保证树的平衡。B-Tree更新某个key的值就可以直接查询该key并更新对应的值，如果增加新的值而空间不够时，就会将该块再往下层迁移成新的两个块。为了保证B-Tree崩溃时有足够的可靠性，B-tree实现通常会在磁盘上增加一个额外的数据结构，一个预写式日志(write-ahead log WAL)，这个日志是只追加方式写的(append-only)，它在做出修改前先将修改的操作写入这个日志，这样能在数据库崩溃后进行恢复操作。一般来说，LSM-trees通常写更快，而B-trees读更快，但是这得根据实际场景进行测试，并不是绝对的。
上面的索引结构都是Key-Value索引，类似关系模型(relational model)中的主键(primary key)索引，下面有一些其它类型的索引。
- secondary index
二级索引(secondary index)可以从key-value索引中很容易地创建，比如在关系型数据库中CREATE INDEX语句。
storing values within the index
Multi-column index
fuzzy index
比如全文搜索引擎一般就支持模糊匹配，它允许搜索关键词有一些语法上的错误。
OLTP&OLAP
OLTP(Online transaction processing) 联机事务处理，通常是面向用户的，每一次查询请求只会使用到少量的数据，因此磁盘查找时间(seek time)一般是系统瓶颈。
OLAP(Online analytic processing) 联机分析处理，通常面向商业分析，而不是终端用户，每一次查询请求会使用大量的数据，因此磁盘带宽(disk bandwidth)是系统瓶颈。OLAP一次会顺序扫描大量数据，而查询的索引并不是它的核心关注点，更加精简地压缩数据才是关注点，这样可以减小从磁盘中读取的数据量，提高效率，面向列的存储(column-oriented storage)可以使用在这种场景。
Column-Oriented Storage
与按行存储数据的方式不同，行式存储是将一行所有的数据存储在一起，而列式存储是将一列所有的数据存储在一起。由于一列中数据的值的区别较小，因此将它们压缩存储更加容易。存储的时候会按照一定的顺序存储，这样我们就能知道哪个值对应哪一条数据(item)。排序不仅可以加快查询速度，而且可以使得压缩列的时候更加高效。
编码与演变
应用不可避免地在变化，随着新产品的发布，功能会被增加或者修改，而对应的数据也在不断变化。而这种变化在大型应用中不可能立即全部完成，旧的与新的代码、数据格式可能共存
- 在服务端(server-side)应用中，可以执行滚动升级(rolling-upgrade)，即把新版本先部署到一部分节点上，然后将旧版本节点慢慢进行迁移到新版本。
- 在客户端(client-side)应用中，用户不一定会立即升级到最新版本。
因此我们需要在两个方向保持兼容性(compatibility)。
Backward compatibility向后兼容：新的代码可以读取旧代码写入的数据
Forward compatibility 向前兼容： 旧的代码可以读取新代码写入的数据
程序通常会有(至少)两种形式处理数据
- 在内存中，数据可以以对象(object)、结构(struct)、列表(list)、数组(array)、哈希表(hash table)、树(tree)等等形式存在，都是为了CPU可以进行更高效处理。
- 当需要将数据写入文件或者在网络上传输时，这时必须将数据编码(encode)为一组独立的字节序列(比如JSON)。
有以下一些方式对数据进行编码
- 语言特定格式
比如java.io.Serializable，具有较多限制，在性能和兼容性上不足 - JSON,XML, CSV
这些都是文本格式，易于阅读，如果有良好的设计可以保持较好的兼容性，但是在处理数字(number)和二进制串(binary string)时都不易处理 - Binary Encoding
二进制编码格式有很多成熟的解决方案，比如Thrift、Protocol Buffers、Avro等等。特点是高效率，并且能保持良好的兼容性，缺点是必须解码(decode)后才可读(human-readable)。
常见的数据编码场景
- 数据库Database
- RPC与REST API
- 异步消息传递
RPC(Remote Procedure Call)
RPC是通过网络服务进行调用，使得client好像在调用本地函数一样。但是两者有着很大不同
- 本地函数调用是可以预知的，即要么失败要么成功只取决于调用时传入的参数，而RPC调用会被网络所影响，因此它无法预知(unpredicable)
- 本地函数调用会返回一个结果或者抛出一个异常，或者不返回(无限循环或者进程崩溃)。而网络请求有可能没有任何回应，比如超时(timeout)，这种情况无法知道发生了什么。
- 如果重试一次失败的网络请求，有可能之前的请求已经完成了，只不过是响应丢失了，这种情况请求有可能会发生两次，所以需要幂等机制(idempotence)。
- 每次本地函数调用时时间基本是在一定范围内的，而网络调用就不一定了，有可能时间差异非常大。
- 网络调用必须先转换成字节序列，如果是很大的对象(big objects)那么就会是比较麻烦的问题
- 客户端与服务有可能用不同语言实现，因此有一个数据类型和语言层面的转换。
上述的一些问题新出现的RPC框架都在解决，比如将可能失败的异步操作封装起来，让它与普通的函数调用看上去不同。
RESTful API一个吸引人的地方在于，它并没有隐藏它是基于网络(一般是HTTP+JSON)的事实。而且RESTful API在试验与调试时更加方便，可以使用任何浏览器或者curl这种工具，不需要额外安装工具，并且支持所有编程语言与平台。
所以基于上述原因，REST主要适合公有API(public API)的场景，而RPC框架更适合一个组织内的使用。
Message-Passing Dataflow
异步消息传递(Asynchronous message-passing)和RPC不同，往往发送者(sender)不关心他发出消息的响应，而仅仅是将消息投递过去。这种异步的通信模式即：发送者发出消息后不等待消息的传递，而是发出过后然后忘记掉这个消息一样。
异步消息传递通常有两种模型
Message brokers
一个进程将消息发送到一个指定的queue或者topic，broker确保该消息会被传递到一个或者多个与该topic关联的消费者(consumer)或者订阅者(subscriber)Distributed actor framework
每个actor内维护自己内部本地的状态，actor之间传递immutable的消息，消息传递不是100%保证的，有可能会丢失。由于每个actor一次只会处理一条消息，这样就避免了并发模型中使用线程经常会出现的race condition。
