《Designing Data-Intensive Applic

一、存储和检索

1、底层数据结构

1.1 log是保存文件数据最常见的方式，关于log的细节，比较通用的有：

1、append-only log，即不可修改，只能追加。
相比于可以修改value的结构，优点有3个。顺序追加更快，并发和恢复更简单，合并操作可以有效避免数据所片花
2、log的记录，随着时间变长，数据的增多，log拆分为多个segement，或者压缩，删减是所有都需要的操作
3、log的压缩，当key少，值经常变化时，日志的压缩，像redis压缩AOF持久化一样，是非常简便高效的方式

可以考虑的方面还有许多，
log的格式：是否用特定的格式，如二进制等
删除records：日志是否要进行优化
crash recovery：数据库重启，是从log从头到尾执行恢复还是 通过快照进行恢复
paritially written records：未确认的部分恢复
并发控制：单线程写入保证顺序，多线程读取

1.2 Hash Index

由HashMap 实现 Index，像字典一样，是最简单的index实现方式，可行性也很高。
所有的key在内存中，value为真正的数据文件地址或者offset偏移量，通过 append-only log实现

缺点：key只有在内存中才能查询快，在大数据的时候只能把key放在磁盘上，这样，通过磁盘查key的性能损耗太大；range query 是低效的，采用hashmap，无法很快得到 key从1-999的value

1.3 SSTable and LSM-Trees

SSTable（Sorted String Table），是对Hash Index的一个改进，原来的hash Index是杂乱的key-value pair，我们相同的key最近的value是什么，其他的我们什么都不关心，而SSTable，会将key进行排序

• 这个排序是指在merge后的segment中必须只能出现一次，且只能出现一次，而现在使用的segment不受影响

相比Hash Index的优点：
1.合并segment更快更简单

image.png

因为key是sorted的状态，所以合并算法会很简单，而且能保证合并后的还是sorted的状态

2.找一个特定的key，不在需要保存所有的key在内存中

image.png

因为key是sorted，所以你可以找某些key在内存中，就可以锁定你找的key是在2者之间，从而丁二到准确的key。 kafka采用的稀疏索引就是用了这个道理

3.range query更为方便了
因为key是有序的，你现在可以将某部分有序的record 压缩后 放在一个block写在磁盘中，这样range query可以直接一个block拿出来，现在计算机磁盘顺序IO是很快的，kafka仍然使用了这个原理

SSTable的工作流程

• 构造SSTable
  有很多数据结构可以构造有序，如红黑树，自平衡树等，当使用这些数据结构时，任何顺序插入数据，读取是都是有序的
• 通常我们使用一个memtable即内存中的红黑树维护顺序，当memtable过大，我们进行一次持久
  化，作为SSTable写到磁盘上
• 读取时现在memTable查找，再去磁盘查找
• 定时使用后台任务，对已落入磁盘的segment进行merge

那么缺点有什么呢?

当数据库crash，memTable的数据会丢失。所以我们得维护另一个append-only log，就像最开始那样，不用管是否有序，只是在写入时，立刻持久化，目的就是为了恢复数据，每次memTable持久化后，这个log就可以丢弃

• Log-Structured Merge-Tree (or LSM-Tree)，基于合并和压缩有序文件的存储系统，我们称之为LSM storage engines

可以优化的细节

• 查找一个不存在的key
  当你找一个不存在的key时会发生什么，你必须先在memTable中找，再去segment中找，你可以通过一个在内存中的布隆过滤器来进行拦截，布隆过滤器可以用很小的空间就完成很高比例的拦截

• 压缩合并的策略和时间点
  目前有2种方式 size-tiered compaction和 leveled compaction
  size-tiered compaction：小的segment，新的segment被合并到 旧的，大的segment中
  leveled compaction：文件是分层，每一个level都是有序的，memTable为L0，L1开始在内存，当L0内存中达到阈值，出发合并后，L0与L1进行合并，然后L1到达积累达到阈值后，L1与L2合并

  
  image.png
  image.png
  

  使用这种模式时，查一个key需要一层层查找，每一层用二分法查找

1.4 B-Trees

最为常见的索引结构 B-Trees。
之前的log结构，常常将log分为一个个segement，通常为MB级别或更大，但B-Tree将数据库分为一个个固定大小的block，通常为4kb，这是每次读写的一个page，这是由底层硬件设备所决定的，因为硬盘也是这么设计的。

B-Tree

B-Tree Index.png

• 1.它和SST唯一相同的，可能就是它的key也是sroted的，我们将一个4kb或更大的block作为整个index 的root，即图中的 ref-100······500-ref，这就是读写的一个page
• 2.每一个page都用address或者location作为标识，这使得每一个page都可以关联到其他的page，就像一个指针一样，只不过是存贮在硬盘中的指针。每一个page包含了很多的key和指向child page的ref，ref两边的key就是 child page中key的边界范围，每一个child page包含了这段范围的key
• 3.最后没有其他child page的节点就称为 leaf page即 叶节点，只有在叶节点上包含了真正的value
• 4.ref to child page的数量就是所谓的branching factor，如上图汇总就是6，但通过会是数百，这应该是通过分析，减少层级做出的设计

如何查找或更新一个key

假设数据为图 B-tree index，我们想查找key=251的值，先在根节点找到200-300之前的ref，在找child page中的250-270间的ref，最后再 叶节点找到key=251的真正数据。同理，你想更新它也是一样的操作

如何插入一个key

如果你插入key时，那个page仍然有充足的空间，则直接插入即可，但若是没有空间，则会将split page 形成2个page，parent page 原来是leaf page，就更新为 包含child page的ref，通过这个split操作，使得B-Tree grow up

image.png

效率

通过B-Tree算法，保证了Tree是平衡的，一个 n个key的数据量，深度为O（logN），一般为3-4层，估算一下，一个4层的 ，每个page4kb的，branching factor 为500的，能存储256TB
4500500500500/1000/1000/1000=250TB

making B-Tree reliable

比较B-Tree和LSM，由于一个是append-only log实现，一个的数据是可以overwrite的，导致B-Tree在以下方面会相对而言更为复杂

• OverWritte
  overwrite操作在普通的时候是没问题，但当你要同时写多个page的时候，你可能在某些page写入后，数据库崩溃了，另一些没有写入。如插入数据导致split，你要重写2个page，并重写parent page。
  此时我们又要去借助之前的append-only log
  我们需要在磁盘中维护一个 write-ahead log（WAL），即 redo log。主要就是用来数据库崩溃后恢复数据。B-Tree的任何一个修改都要写入其中，才能真正执行

• 并发
  多线程并发控制，因为修改的同一份数据，所以必须借助latches（light locks）进行控制，而LSM完全不用考虑这个问题

B-Tree 优化

1.WAL的替代方案，修改的并不会在原来的地方执行，而是在另一个地方创建，同时一个new version的parent page也被创建，这也同样可以用于并发控制
2.使用简短的key或者缩写的key，节省空间，从而使得branch factor可以更大
3.在range query时，LSM效率很高，但是B-Tree很难，因为只有leaf-pages 依次在一起才能达到顺序读取的效果，维护所有的leaf-pages是困难的
4.因此我们可以通过多一个指针来完成这个目的，每一个leaf-page都包含一个ref，这个ref指向它的兄妹leaf-page，这个样子查找就可以不跳回parent page，直接在leaf-page上依次找下去

1.5 B-Trees 和LSM 的对比

• 一个直观的概念，B-tree应用会相对更广一些，它在读的性能上更好一些，而LSM在写的性能上更好一些

SLM的优点

• B-tree写入为了可靠性，至少得写2次，第一次写入WAL，第二次写入page，更多的如split操作。
  而LSM也有write amplification（写入放大）的问题，在某一个时刻，某一个写入可能会导致多次合并写入，这在SSDs上会很明显，SSD在有限次数的写入后会磨损
  在write-heavy的应用中，瓶颈可能会在磁盘写入上，此时write amplification会有明显的影响，降低写入的效率。尽管如此，我们通常还是认为LSM写入比B-Tree更快，部分是因为写入放大会和实际负载和配置有关系，部分是因为顺序写入明显会比随机写入快很多
• LSM得益于merge操作，使得存储效率更高，因为B-Tree无法避免碎片问题，每一个leaf-page不可能都刚好填充满，除非经常进行特殊的整理操作
• 在很多SSD上，会将随机写入通过LSM改为顺序写入，这使得某些引擎看上去性能没有那么显著，但更少的写入放大和更少的碎片率是SSD的优点，体现了更高的读写带宽

SLM的缺点

• 合并的时候，会影响到读写，这是的后台合并任务发生的时候，读写可能必须要等待合并完成才可以执行。由于采用了增量合并，通常影响很小，但也很难避免某个时刻需等待很久的情况
• 第二点是关于database的size，当databse过大，即key越来越多，segment的合并会不断变大，此时的后台合并操作可能会占用更多的磁盘写入读取带宽，所以要合理评估数据的容量
• 关于事务性，大部分情况下，事务是通过对一个范围的index加锁来实现的，由于B-tree的key是一个固定的位置，使得加锁很自然，但LSM，由于一个key可能会存在多个segment，这是的加锁变得困难，事务性也就不自然。

1.6 其他索引结构

之前我们讲的索引都是唯一索引，即key是唯一的，但很多时候，我们会需要第二索引，第二索引和唯一索引不同的是，第二索引的key可能会有重复。大致上有2种思路解决这个问题

• 将重复处理为唯一，添加一个唯一的row来完成
• 通过将相同的key当做一个list来进行处理

Storing values within the index

索引我们常常是将key作为索引，那我们到底是怎么存放value的，value一般可以有2种形式，一是真正的value，二是真正value的引用，最终的value在heap上。
为了节省空间，我们只会存储一份真实的数据，因此第二索引的value只能为 真实value的引用

• 更新value
  当新value比老value小的时候，很简单，直接overwrite即可，但如果新value比较大，我们就需要heap移动位置，并将所有value的引用进行更新

• 聚簇索引和非聚簇索引
  首先得知道区分的依据是什么：在mysql 的InnoDB中，我们分析了B-Tree的存储方式，我们知道在叶子节点，所有的value都是真实的value，相邻的value是紧紧聚集的，所以我们叫聚簇索引。因为真实value我们只会存在一份，所以一个数据库，聚簇索引我们也只会有一个。这个导致了你的第二索引，很可能需要查找2次，第一次找到数据的真实主键，然后根据真实主键在聚簇索引中找到真正的value

• Multi-column indexes
  这其实就是多列索引，在某些情况下，如地理位置，单一的经度或者维度对于我们是没有意义的，我们需要的是合起来的经纬度，这时候我们可以将经纬度合起来作为多列索引进行使用

• 全文搜索和fuzzy indexes
  距离了lucene，这个可以学习ElasticSeaerch

• 内存存储
  由于内存技术的成熟，价格的降低，内存存储像redis也成了成熟的技术，通常我们用硬盘作持久化，而用内存存储作为缓存，但我们可以接受一定的数据丢失的时候。

2、事务和分析

2.1 数据仓库

传统数据库，我们一般是交互式的插入或更新数据，但后来随着数据分析的兴起，2者出现了一些区别，从而专门用于数据处理的数据仓库兴起了

image.png

OLTP通常和OLAP要进行区分，如果用同一个数据存储，analyse通常占用了太多资源，会影响正常的业务。正常，我们会将一个read_only的copy数据放入数据仓库用于分析，有时候放入前要清晰数据，以方便后续的分析业务
这一个过程，我们一般称之为ETL(extract-transform-load)
常见的开源数据仓库：Apache Hive，Spark Sql等

2.2 星型模型和雪花模型

在数据仓库中，常使用2种数据模型，星型模型和雪花模型

• 星型模型：顾名思义，就是一张核心表，其他的表都是核心表的发散和具体内容，如一张核心表有个字段是单号，可能这个单号是另一张表的主键，有很多完整的其他信息。实际中，核心表可能有数百个字段，在实际使用中由于更为简单的结构而常常被采用
• 雪花模型：在星型模型的基础上，继续演变，每一个关联的表可以继续发散。优点是设计比较顺滑，缺点是大量的join操作

2.2 面向列的存储

实际使用中，一个核心表常常有上百列的规模，在OLTP中，一般都是面向row存储的，即每个row的数据是放在一起的。但实际分析中，我们常常只需要其中的几行，怎么办？
传统的面向row的数据存储，虽然可以select某几行，但实现上其实是先加载所有的数据到内存，再选出其中的几个字段。

解决方法就是 面向列的存储：每一列的数据进行存储，举例

列存储

可以看到，每一个列都成了一个单独的文件，顺序都是按原来的row模式的顺序。此时假设你需要找23行的 product_sk，quantity字段，你就可以分别到2个文件中，去找第23rd的列数据，再组合在一起

列的压缩

列存储，如age等，相似的概率很大，因此压缩效率会很高。常用的有bitmap等方式
此外还有cpu的SIMD技术

列的排序

当使用列存储时，单独对某个列文件进行排序是没意思，因为你会对应不上row。
这里的列排序，一般只是用于搜索时，如只要上个月数据，就去日期的列，先找到所有的row，排序，然后去其他的列中查找，最后整合

列存储的写入

列存储的目的是为了方便大数据的读取，包括存储的压缩。但它的写入也变得复杂，你可能需要去同时去更新很多文件。那么有什么办法去优化呢？
答案是：批量处理
我们会使用一个在内存中的LSM结构去存储插入的数据，在内存时，你不需要去关心最终到硬盘是row oriented还是column oriented，当内存累计到一个值，再批量写入磁盘
通过这个写入方式时，读取数据也需要结合disk的数据和内存的数据，再返回。但数据库帮你屏蔽了这些复杂的实现细节，对于用户来说，就是写入和读取是实时的

聚合

常见的聚合操作： COUNT, SUM, AVG, MIN, MAX

有一种解决方式为 materialized view（物化视图），和一般的view相比，一般的view其实只是一种抽象，最终还是会执行为sql，但物化视图是一个真正的，需要存储空间的表，他主要用于分析，因为需要同时维护一些聚合信息，所以，写入操作是很昂贵的，一般的OLTP系统不会用
本质上，通过物化视图提升查询速度，只是因为进行了预处理运算