《Designing Data-intensive Application》读书笔记 – 存储与检索

存储的数据结构


哈希索引

对于Key-Value的数据来说,hashTable是非常常见的索引方式,很适合更新频繁的场景。Value映射到一个数据文件中的字节偏移量,以能在数据存储中找到对应位置。

如果哈希索引存储在日志中,为了避免占用太多的磁盘空间,当日志增长到指定大小后,则关闭当前日志文件并开启新的日志文件,旧的日志文件成为只读。日志文件中,相同键的记录只需要保留最新的值即可,因此可以做压缩(Compaction)。同时,多个日志文件之间也可以做合并(Merging),生成新的日志文件。压缩和合并的工作可以在后台线程中完成,在工作完成之前,这些旧文件仍然可以提供查询,直到新文件生成并删除旧文件。

但是哈希索引也存在着某些局限性:

  1. 哈希表必须能放进内存,且会产生hash冲突
  2. 无法进行范围查询

SSTable / LSM Tree

如果要求键的顺序完全有序,则变成了SSTable(Sorted String Table),并要求每个键在SSTable中只出现一次。相比于HashTable,有如下几点优势:

  1. 由于键是有序的,因此Merge的过程更加简单和高效。利用归并排序(这样就不受内存大小的限制了),就可以保证多个SSTable的合并结果仍然是一个SSTable。当多个SSTable中出现相同的键时,只需要保留最新的值。
  2. 索引会变得更加稀疏,在一个SSTable中,只需要在索引中保存Block的第一个Key,这样在查找的时候,只需要先定位到Block,然后在block中顺序寻找即可。
  3. 在写入磁盘之前,就可以对Block中的记录进行压缩,从而减少IO。

SSTable的生成与维护

  1. 在内存中维护一个有序的数据结构,比如红黑树。这个内存树也被称为memtable
  2. 当memtable的大小超过阈值(几MB)时,写入到磁盘成为SSTable。写入成功后,继续在内存中产生新的memtable
  3. 当提供查询时,优先查询memtable,再查找最新的SSTable
  4. 后台线程会定期执行Compaction和Merge

LevelDb / RocksDb / HBase

LevelDb的生成过程

  1. memtable会生成Log File,默认超过4MB就会生成Sorted Table
  2. Sorted Table中存储的值,要么是key-value,要么是deletion marker,以便后续在compaction的时候删除记录
  3. 刚生成的Sorted Table又称为level-0,当level-0个数超过一定阈值后,会和level-1的文件进行合并,从而生成新的level-1文件
  4. level-0的文件之间可能存在重叠,其他层的文件不会重叠。当L层的总大小超过10^LMB,则需要进行合并生成新的L+1层
  5. 当进行合并时,一个L层的文件和L+1层有重叠的文件作为输入,生成新的L+1层。如果是0层,则会用多个文件作为输入,因为level-0文件之间会有重叠

RocksDb基于LevelDb的改进

HBase的compaction过程和LevelDB有所不同,更新和更小的SSTables先后被合并到更老的和更大的SSTable中。

B-Tree

B-Tree和LSM-Tree同样是键保证有序,但是B-Tree是将按照固定大小的Page进行存储,每次读取和写入都是以页面作为单位。这样设计更接近底层硬件。

一个页面作为根,页面之间存在引用关系,从而形成一棵树。每个子页面负责一段连续范围的键,叶子页面会存储键实际的值。

如果更新键的值,则需要定位到包含该键的叶子页面,更新该页的值,并重新写回磁盘。如果新增一个键,页面空间不足则会发生页面分裂,需要更新父页面的引用。

LSM-Tree VS B-Tree

LSM-TreeB-Tree
优势场景写入性能较好读取性能较好
写入吞吐写入的SSTable比较紧凑,因此有更高的写入吞吐量每次都要读取并更新写入整个页面,导致写放大
存储空间LSM-Tree支持压缩,且定期的Compaction以去除碎片由于页面分割,导致一些空间未被使用
读取性能Compaction的过程会干扰正在进行的读写。且如果写入量过大,导致文件没有来得及合并,导致读取的路径较长读取性能非常稳定
事务支持每个键会有多个副本每个键只存在于索引的一个位置中,在键上加锁可以实现事务隔离

其他索引

  1. 聚簇索引(Clustered Index)
  2. 覆盖索引(Covering Index)
  3. 多列索引(Concatenated Index)
  4. 多维索引(Multi-dimensional Index)
  5. 全文搜索和模糊索引

事务处理 vs 分析


OLTP or OLAP

属性OLTPOLAP
主要读取模式少量查询,按索引查询大数据量上的聚合
主要写入模式随机写入,要求低延迟批量导入(ETL)或事件流
主要用户终端用户或消费者,web访问内部分析师用于决策支持
处理的数据数据的当前状态随时间变化的历史数据
数据集大小GB ~ TBTB ~ PB

数据仓库

一个公司会有很多独立的业务系统,为了分析人员能够方便访问其中的数据,且不影响线上业务,需要有一个中心化的数据仓库,来存储各个业务系统的只读副本。将数据导入数据仓库的过程被称为抽取-转换-加载(Extract – Transform – Load,有时也会是ELT)。上文中讨论的存储数据结构,只适用于OLTP系统,对于分析查询来说,需要有特殊的存储结构。

星型模式和雪花模式

星型模式也被称为维度建模,在模式的中心是一张事实表,其中每一行代表着特定时间发生的具体事件。事实表会和一些维度表发生关联,这些维度代表了事实发生的时间、地点、方式等。这个模式的变体,又被称为雪花模式,关联维度被分解为了更多的维度。它被星型模式更加规范,但是使用起来可能更加困难。

列存储


数据仓库查询,一般只会用到其中的几列。如果是以行存储的话,读取过程将带来较大的浪费。面向列存储,是将每一列存储在一个单独文件中,从而节省读取成本。比如Parquet格式

列压缩

使用Bitmap可以有效地节省空间。如果一个列的基数比较少,总共有N个值,则可以转换为N个bitmap,每个bitmap记录该列哪些bit位上是有这个值的,有值记为1,无值记为0。再通过Run Length Encoding,则可以使列变得更加紧凑。

对于a = 1 and b = 30这样的查询,可以分别找到a=1、b=30这两个bitmap,然后计算bitand,可以快速筛选出符合的记录。

注:Cassandra和HBase中的Cluster,是将key和一行所有的列一起存储,并不使用列压缩。所以这两个仍然是面向行的。

列存储中的排序

在列存储中,如果不指定排序,则会按照行的插入顺序排序。但是也可以指定排序,需要注意的是,针对单独一个列排序是没有意义的,这样多列之间就没法找到同一行的数据了。

可以根据历史查询的经验,判断出列的排序顺序。比如订单表,将create_time作为第一排序字段,则相同创建时间的订单会放在一起,从而方便时间范围的查询。

另一个好处的话,就是排序列相同的值放在一起,那么Run Length Encoding压缩的效果会更好。

列存储的写入

如果底层是LSM-Tree的结构,那么列存储的写入就会比较方便。写操作先写入内存中的一个已排序的结构中,当积累了足够数据后,和磁盘上的列文件进行合并,然后写入新文件。

留下评论

5 × 4 =