> For the complete documentation index, see [llms.txt](https://shniu.gitbook.io/cs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://shniu.gitbook.io/cs/other/reading/ddia.md).

# 设计数据密集型应用

[书籍在线地址](https://github.com/Vonng/ddia/blob/master/ch1.md)

## 数据系统的基石

怎么理解数据密集型？

数据密集型应用的特点是数据量大，数据复杂度高，以及数据变更速度快；而非计算密集型，所以 CPU 一般不会成为数据密集型应用的瓶颈；比如数据库、搜索引擎、缓存、消息队列、流处理、批处理等。

不同的存储工具和数据处理工具，根据应用场景做了特定的优化，使得他们之间的界限越来越模糊，如数据存储可以被当成消息队列用（Redis），消息队列则带有类似数据库的持久保证（Apache Kafka）；此外，越来越多的应用程序有着各种严格而广泛的要求，单个工具不足以满足所有的数据处理和存储需求。取而代之的是，总体工作被拆分成一系列能被单个工具高效完成的任务，并通过应用代码将它们缝合起来，比如：

![一种可能的数据系统的结构](https://1617012602-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M5PFXCiDtVclypn0iMK%2F-M7NYywWCj-FJRLAPrl3%2F-M7NhTFPnfm7I6NscBeR%2Fddia-1-1.png?alt=media\&token=4c1910b1-019b-4066-9629-6a6cf82912d4)

数据系统面临的主要问题：

* 可靠性

可靠性是指系统在困境（硬件故障、软件故障、人为错误）下也能正常的工作（正确完成功能，并能达到期望的性能水准）

需要正确理解故障(fault)和失效(failure), 故障是不可能降为零的，同样我们在讨论故障时也要基于特定的场景；而系统应对故障的方式称为容错或具有弹性；系统需要具备容错性，而通过触发有意故障是有意义的，比如 Netflix 公司的 Chaos Monkey 就是这样一种实践。通常故障可分为几类：

**硬件故障**

比如硬盘崩溃、内存出错、机房断电、网线被拔，因为一旦有很多机器，一切皆有可能；有统计显示，硬盘的 平均无故障时间（MTTF mean time to failure） 约为10到50年，那么在拥有 10000 个磁盘的存储集群上，平均每天会有1个磁盘出故障。

解决硬件故障的思路就是使用`硬件冗余`，在单台失效的情况下，可以使用其他硬件。只需要做好在大量机器之间的灵活调度，即使单机失效也不会影响整体系统的使用。硬件故障是存在一定概率的，所以我们可以使用多台机器组成集群来降低故障带来的影响，也就是冗余的思想。

**软件故障**

软件故障最常见的是系统性错误，难以预料，并且跨节点；虽然软件中的系统性故障没有速效药，但还是有很多小办法，例如：仔细考虑系统中的假设和交互；彻底的测试；进程隔离；允许进程崩溃并重启；测量、监控并分析生产环境中的系统行为。如果系统能够提供一些保证（例如在一个消息队列中，进入与发出的消息数量相等），那么系统就可以在运行时不断自检，并在出现**差异(discrepancy)**时报警

**人为错误**

人为错误也是一种不可避免的故障因素，只能尽可能的降低它发生的概率，比如：

1. 精心设计API、设计抽象、设计管理后台等，用最小化犯错机会来设计系统
2. 将容易犯错的地方与可能导致失效的地方解耦合 
3. 更加充分的测试，单测、集成测试、手工测试、自动化测试，特别注意一些边界场景 
4. 允许从人为错误中快速恢复，如快速回滚、分批发布等

可靠性很重要，要权衡不同曾层面、不同场景的选择，明白自己处在哪个阶段，需要什么样的可靠性保障。

* 可扩展性

可扩展性（Scalability） 是用来描述系统应对负载增长能力的术语。讨论可扩展性意味着考虑诸如“如果系统以特定方式增长，有什么选项可以应对增长？”和“如何增加计算资源来处理额外的负载？”等问题。

如何描述负载？

增长为系统带来了可扩展性的需求，负载可以用来描述当前系统的状态，具体使用什么样的负载参数来描述系统架构是不确定的，因为不同的业务场景对于负载参数的要求是不同的：可能是 QPS、数据库的读写比率、活跃用户数、缓存命中率等

试想一下推特的业务场景（更多的内容见 DDIA 第一章）：发布推文和主页时间线，发推时粉丝数量是一个值得关注的关键负载参数，如果一个用户的用户粉丝数量是3000万，和用户的粉丝数量是100，其实需要不同的处理方式；

确定了系统的关键负载参数后，就可以来描述性能了，比如： 1. Hadoop这样的批处理系统，通常关心的是吞吐量（throughput），即每秒可以处理的记录数量 2. 在线系统，通常更重要的是服务的响应时间（response time）

如何应对负载？

水平扩展和垂直扩展，是通常使用的方法。水平扩展，需要尽量设计无共享架构（也可以理解为无状态），跨多台机器部署**无状态服务（stateless services）**非常简单，但将带状态的数据系统从单节点变为分布式配置则可能引入许多额外复杂度。出于这个原因，常识告诉我们应该将数据库放在单个节点上（垂直扩展），直到扩展成本或可用性需求迫使其改为分布式。但是随着分布式系统的工具和抽象越来越好，分布式系统会是未来的趋势。

* 可维护性

软件的大部分开销并不在最初的开发阶段，而是在持续的维护阶段，包括修复漏洞、保持系统正常运行、调查失效、适配新的平台、为新的场景进行修改、偿还技术债、添加新的功能等

原则：可操作性（运维）、简单性（应对复杂度）、可演化性（拥抱变化）

复杂度（complexity） 有各种可能的症状，例如：状态空间激增、模块间紧密耦合、纠结的依赖关系、不一致的命名和术语、解决性能问题的Hack、需要绕开的特例等。用于消除额外复杂度的最好工具之一是抽象（abstraction）。一个好的抽象可以将大量实现细节隐藏在一个干净，简单易懂的外观下面。一个好的抽象也可以广泛用于各类不同应用。比起重复造很多轮子，重用抽象不仅更有效率，而且有助于开发高质量的软件。抽象组件的质量改进将使所有使用它的应用受益。抽象可以帮助我们将系统的复杂度控制在可管理的水平，不过，找到好的抽象是非常困难的。在分布式系统领域虽然有许多好的算法，但我们并不清楚它们应该打包成什么样抽象。如高级编程语言是一种抽象，隐藏了机器码、CPU寄存器和系统调用。

修改数据系统并使其适应不断变化需求的容易程度，是与简单性和抽象性密切相关的：简单易懂的系统通常比复杂系统更容易修改。

总结一下：可靠性意味着发生故障时，系统也能正常工作，容错技术可以应对故障，隐藏故障细节；可扩展性意味着在负载增加的情况下也有保持性能的策略，需要引入负载参数来描述系统的关键负载，然后使用性能参数来衡量系统的状态，在随着负载增加时可以通过增加处理容量来应对，一般的方法有水平扩展和垂直扩展；可维护性，主要是关于工程师和运维团队的质量，良好的抽象可以应对复杂度，让系统易于维护和适应新的变化，敏捷的工作模式可以带来很多好处，运用持续优化持续重构的思想来提升可演化性。

## 存储与检索

大部分情况下，数据库需要完成两件事情：可以存储给它的数据；当你想获取这些数据的时候，可以再返还给你。作为应用开发人员为什么需要关注底层的存储引擎呢？因为当我们需要调优应用时，必须了解存储引擎的内部工作原理，而且事务型的场景和分析的场景调优的思路是不同的。目前有两大类主流的存储引擎：**日志结构**（log-structured）的存储引擎，以及**面向页面**（page-oriented）的存储引擎（例如B树）。

世界上最简单的数据库

```
#!/bin/bash

db_set() {
  echo "$1,$2" >> database
}

db_get() {
  grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}
```

麻雀虽小，五脏俱全。有如下有缺点：

* db\_set 足够简单，直接追加记录到文件末尾，是一个仅追加的日志型结构，这是他的优点；但是这只能应对一些简单的场景，但真正在生产中，我们还需要解决很多问题，如并发控制，回收磁盘空间以避免日志无限增长，处理错误与部分写入的记录
* db\_get 也足够简单，从所有记录里搜索指定的 key，然后取最新的数据，这是他的优点；但是随着数据的增加，查询速度会变慢，算法的时间复杂度为 O(n)，当数据量很大时，是无法忍受的

为了解决 db\_get 查询速度退化的问题，可以引入一个叫索引的数据结构，它是一个附加的数据结构，建立在原始数据之上，引入索引会带来好处，也会带来一些坏处：

1. 在查询时，会提高查询速度
2. 在写入时，需要付出额外的维护成本，所以会造成写入性能的降低

所有这些都需要在实际使用时根据业务去做权衡，不是一成不变的。

### Hash Index

Hash 算法是一类数学函数算法，也叫散列算法，是一种映射关系；当输入任意的数据，经过hash运算后，都会返回一个hash后的数据，不同的输入会产生不同的输出。将这种技术应用于字典、哈希表或者哈希map中，就可以很快速的查找到需要的数据，这是一种基于内存的kv映射数据结构，查找和插入的性能都非常好。

当我们存储数据是一个追加写入的文件时，我们可以考虑在内存中维护一个映射表，将每个key对应的真实内容在文件中的位置维护在这个映射表里，在查询时，只需要几步就可以找到数据，当写入时，更新映射表并追加数据。利用这种思想实现的数据库有：Bitcask，GoBeansdb。

#### Bitcask

```
1. 键存储在内存中以便快速查找，所有键必须都放在内存中
2. 只能追加写，这意味着写入是严格顺序的，不需要搜索，每次更新值的时候，都会在磁盘文件上追加值，并使用文件指针来更新内存索引
3. 读查询满足 O(1) 的随机磁盘搜索，如果所有键都在内存中，延迟是可以预测的，因为没有随机搜索文件
4. 对于读取，使用内核中的文件系统缓存
5. Bitcask对所有非活动文件执行定期合并，以压缩旧版本存储数据占用的空间。 在某些情况下，这可能会导致合并发生的Riak节点出现一些内存和CPU峰值。 为此，我们添加了指定Bitcask何时执行合并的功能
6. 值索引的键存在于内存和文件系统的合并文件中，合并数据文件时会生成提示文件，在重启时，只需要为非合并文件创建索引，这些数据应该是数据的一小部分

* Bitcask 模型将数据追加到文件中，顺序写入（日志追加），不允许修改，写入性能高
* 将日志文件分段存储，易用管理,一个活动文件用于写入，多个旧文件用来读取
* Hash 内存索引快速定位值的位置，读性能很高
* 文件合并和压缩，对旧文件进行这些操作
* 线索文件hint file，方便崩溃后恢复内存索引
* 方便部分写入的记录可以删除掉，因为只有很少记录会部分写入
* 并发控制容易，一个写，多个读
```

Bitcask 索引表的缺点：

1. 映射表必须放在内存中，当键非常多的时候，就放不下了；如果将映射放入磁盘，不幸的是磁盘哈希映射很难表现优秀。它需要大量的随机访问I/O，当它变满时增长是很昂贵的，并且散列冲突需要很多的逻辑
2. 范围查询效率不高

#### SSTable 和 LSM-Trees

#### B-Tree 和 B+Tree

### 参考资料

* [Bitcask: A Log-Structured Hash Table For Fast Key/Value Data](http://highscalability.com/blog/2011/1/10/riaks-bitcask-a-log-structured-hash-table-for-fast-keyvalue.html)   介绍了 Bitcask 的特性
* Bitcask 的论文：[Bitcask intro](https://github.com/basho/bitcask/blob/develop/doc/bitcask-intro.pdf)
* [优雅的Bitcask](https://my.oschina.net/doctor2014/blog/411029)
* [Gobeansdb](https://github.com/douban/gobeansdb)
* [GoBeansdb wiki](http://sunisdown.me/gobeansdb-jia-gou-she-ji.html)
* [Amazon dynamo](https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf)
* 常见的 kv 数据库
  * Bitcask
  * [go-cache](https://github.com/patrickmn/go-cache)
  * GoBeansDB
  * Dynamo
  * [dgraph-io/badger](https://github.com/dgraph-io/badger)
  * leveldb
  * RocksDB
  * Couchdb
  * [boltdb](https://github.com/boltdb/bolt)
  * Riak
  * [etcd](https://github.com/etcd-io/etcd)
  * [consul](https://github.com/hashicorp/consul)
  * [memcached](https://memcached.org/)
  * [awesome-go-storage](https://github.com/gostor/awesome-go-storage)
  * [kvstore](https://github.com/igorsobreira/kvstore)
  * [kv](https://godoc.org/modernc.org/kv)