北京专业网站建设网站,网店如何引流与推广,wordpress 分类 字段,怎么做网站解析本文内容翻译自《数据密集型应用系统设计》#xff0c;豆瓣评分高达 9.7 分。 什么是「数据密集型应用系统」#xff1f; 当数据#xff08;数据量、数据复杂度、数据变化速度#xff09;是一个应用的主要挑战#xff0c;那么可以把这个应用称为数据密集型的。与之相对的是…本文内容翻译自《数据密集型应用系统设计》豆瓣评分高达 9.7 分。 什么是「数据密集型应用系统」 当数据数据量、数据复杂度、数据变化速度是一个应用的主要挑战那么可以把这个应用称为数据密集型的。与之相对的是计算密集型——处理器速度是主要瓶颈。 其实我们平时遇到的大部分系统都是数据密集型的——应用代码访问内存、硬盘、数据库、消息队列中的数据经过业务逻辑处理再返回给用户。
这本书并不是针对某个具体的数据库而是自顶向下展开各项技术的共性和区别把所有跟「数据」有关的知识点做了剖析、整理、总结。 查询类型
Online analytical processing和Online analytical processing。
查询类型主要分为两大类 引擎类型 请求数量 数据量 瓶颈 存储格式 用户 场景举例 产品举例 OLTP 相对频繁侧重在线交易 总体和单次查询都相对较小 Disk Seek 多用行存 比较普遍一般应用用的比较多 银行交易 MySQL OLAP 相对较少侧重离线分析 总体和单次查询都相对巨大 Disk Bandwidth 列存逐渐流行 多为商业用户 商业分析 ClickHouse
其中OLTP 侧常用的存储引擎又有两种流派 流派 主要特点 基本思想 代表 log-structured 流 只允许追加所有修改都表现为文件的追加和文件整体增删 变随机写为顺序写 Bitcask、LevelDB、RocksDB、Cassandra、Lucene update-in-place 流 以页page为粒度对磁盘数据进行修改 面向页、查找树 B 族树所有主流关系型数据库和一些非关系型数据库
此外针对 OLTP 还探索了常见的建索引的方法以及一种特殊的数据库 —— 全内存数据库。
对于数据仓库本章分析了它与 OLTP 的主要不同之处。数据仓库主要侧重于聚合查询需要扫描很大量的数据此时索引就相对不太有用。需要考虑的是存储成本、带宽优化等由此引出列式存储。 驱动数据库的底层数据结构
本节由一个 shell 脚本出发到一个相当简单但可用的存储引擎 Bitcask然后引出 LSM-tree他们都属于日志流范畴。之后转向存储引擎另一流派 ——B 族树之后对其做了简单对比。最后探讨了存储中离不开的结构 —— 索引。
首先来看世界上 “最简单” 的数据库由两个 Bash 函数构成 1 2 3 4 5 6 7 8 #!/bin/bash db_set () { echo $1,$2 database } db_get () { grep ^$1, database | sed -e s/^$1,// | tail -n 1 } 这两个函数实现了一个基于字符串的 KV 存储只支持 get/set不支持 delete 1 2 3 4 $ db_set 123456 {name:London,attractions:[Big Ben,London Eye]} $ db_set 42 {name:San Francisco,attractions:[Golden Gate Bridge]} $ db_get 42 {name:San Francisco,attractions:[Golden Gate Bridge]} 来分析下它为什么 work也反映了日志结构存储的最基本原理
set在文件末尾追加一个 KV 对。get匹配所有 Key返回最后也即最新一条 KV 对中的 Value。
可以看出写很快但是读需要全文逐行扫描会慢很多。典型的以读换写。为了加快读我们需要构建索引一种允许基于某些字段查找的额外数据结构。
索引从原数据中构建只为加快查找。因此索引会耗费一定额外空间和插入时间每次插入要更新索引即重新以空间和写换读取。
这便是数据库存储引擎设计和选择时最常见的权衡trade off
恰当的存储格式能加快写日志结构但是会让读取很慢也可以加快读查找树、B 族树但会让写入较慢。为了弥补读性能可以构建索引。但是会牺牲写入性能和耗费额外空间。
存储格式一般不好动但是索引构建与否一般交予用户选择。 哈希索引
本节主要基于最基础的 KV 索引。
依上小节的例子所有数据顺序追加到磁盘上。为了加快查询我们在内存中构建一个哈希索引
Key 是查询 KeyValue 是 KV 条目的起始位置和看来很简单但这正是 Bitcask 的基本设计但关键是他 Work在小数据量时即所有 key 都能存到内存中时能提供很高的读写性能
写文件追加写。读一次内存查询一次磁盘 seek如果数据已经被缓存则 seek 也可以省掉。如果你的 key 集合很小意味着能全放内存但是每个 key 更新很频繁那么 Bitcask 便是你的菜。举个栗子频繁更新的视频播放量key 是视频 urlvalue 是视频播放量。 但有个很重要问题单个文件越来越大磁盘空间不够怎么办 在文件到达一定尺寸后就新建一个文件将原文件变为只读。同时为了回收多个 key 多次写入的造成的空间浪费可以将只读文件进行紧缩 compact 将旧文件进行重写挤出 “水分”被覆写的数据以进行垃圾回收。 当然如果我们想让其工业可用还有很多问题需要解决
文件格式。对于日志来说CSV 不是一种紧凑的数据格式有很多空间浪费。比如可以用 length record bytes 。记录删除。之前只支持 put\get但实际还需要支持 delete。但日志结构又不支持更新怎么办呢一般是写一个特殊标记比如墓碑记录tombstone以表示该记录已删除。之后 compact 时真正删除即可。宕机恢复。在机器重启时内存中的哈希索引将会丢失。当然可以全盘扫描以重建但通常一个小优化是对于每个 segment file 将其索引条目和数据文件一块持久化重启时只需加载索引条目即可。记录写坏、少写。系统任何时候都有可能宕机由此会造成记录写坏、少写。为了识别错误记录我们需要增加一些校验字段以识别并跳过这种数据。为了跳过写了部分的数据还要用一些特殊字符来标识记录间的边界。并发控制。由于只有一个活动追加文件因此写只有一个天然并发度。但其他的文件都是不可变的compact 时会读取然后生成新的因此读取和紧缩可以并发执行。
乍一看基于日志的存储结构存在折不少浪费需要以追加进行更新和删除。但日志结构有几个原地更新结构无法做的优点
以顺序写代替随机写。对于磁盘和 SSD顺序写都要比随机写快几个数量级。简易的并发控制。由于大部分的文件都是不可变immutable的因此更容易做并发读取和紧缩。也不用担心原地更新会造成新老数据交替。更少的内部碎片。每次紧缩会将垃圾完全挤出。但是原地更新就会在 page 中留下一些不可用空间。
当然基于内存的哈希索引也有其局限
所有 Key 必须放内存。一旦 Key 的数据量超过内存大小这种方案便不再 work。当然你可以设计基于磁盘的哈希表但那又会带来大量的随机写。不支持范围查询。由于 key 是无序的要进行范围查询必须全表扫描。
后面讲的 LSM-Tree 和 B 树都能部分规避上述问题。
想想会如何进行规避SSTables 和 LSM-Trees
这一节层层递进步步做引从 SSTables 格式出发牵出 LSM-Trees 全貌。
对于 KV 数据前面的 BitCask 存储结构是
外存上日志片段内存中的哈希表
其中外存上的数据是简单追加写而形成的并没有按照某个字段有序。
假设加一个限制让这些文件按 key 有序。我们称这种格式为SSTableSorted String Table。
这种文件格式有什么优点呢
高效的数据文件合并。即有序文件的归并外排顺序读顺序写。不同文件出现相同 Key 怎么办 不需要在内存中保存所有数据的索引。仅需要记录下每个文件界限以区间表示[startKey, endKey]当然实际会记录的更细即可。查找某个 Key 时去所有包含该 Key 的区间对应的文件二分查找即可。 分块压缩节省空间减少 IO。相邻 Key 共享前缀既然每次都要批量取那正好一组 key batch 到一块称为 block且只记录 block 的索引。
构建和维护 SSTables
SSTables 格式听起来很美好但须知数据是乱序的来的我们如何得到有序的数据文件呢
这可以拆解为两个小问题
如何构建。如何维护。
构建 SSTable 文件。将乱序数据在外存磁盘 or SSD中上整理为有序文件是比较难的。但是在内存就方便的多。于是一个大胆的想法就形成了
在内存中维护一个有序结构称为 MemTable。红黑树、AVL 树、条表。到达一定阈值之后全量 dump 到外存。
维护 SSTable 文件。为什么需要维护呢首先要问对于上述复合结构我们怎么进行查询
先去 MemTable 中查找如果命中则返回。再去 SSTable 按时间顺序由新到旧逐一查找。
如果 SSTable 文件越来越多则查找代价会越来越大。因此需要将多个 SSTable 文件合并以减少文件数量同时进行 GC我们称之为紧缩 Compaction。
该方案的问题如果出现宕机内存中的数据结构将会消失。 解决方法也很经典WAL。
从 SSTables 到 LSM-Tree
将前面几节的一些碎片有机的组织起来便是时下流行的存储引擎 LevelDB 和 RocksDB 后面的存储结构LSM-Tree 这种数据结构是 Patrick O’Neil 等人在 1996 年提出的The Log-Structured Merge-Tree。
Elasticsearch 和 Solr 的索引引擎 Lucene也使用类似 LSM-Tree 存储结构。但其数据模型不是 KV但类似word → document list。
性能优化
如果想让一个引擎工程上可用还会做大量的性能优化。对于 LSM-Tree 来说包括
优化 SSTable 的查找。常用 Bloom Filter。该数据结构可以使用较少的内存为每个 SSTable 做一些指纹起到一些初筛的作用。
层级化组织 SSTable。以控制 Compaction 的顺序和时间。常见的有 size-tiered 和 leveled compaction。LevelDB 便是支持后者而得名。前者比较简单粗暴后者性能更好也因此更为常见。 对于 RocksDB 来说工程上的优化和使用上的优化就更多了。在其 Wiki 上随便摘录几点
Column Family前缀压缩和过滤键值分离BlobDB
但无论有多少变种和优化LSM-Tree 的核心思想 —— 保存一组合理组织、后台合并的 SSTables —— 简约而强大。可以方便的进行范围遍历可以变大量随机为少量顺序。
B 族树
虽然先讲的 LSM-Tree但是它要比 B 树新的多。
B 树于 1970 年被 R. Bayer and E. McCreight 提出后便迅速流行了起来。现在几乎所有的关系型数据中它都是数据索引标准一般的实现。
与 LSM-Tree 一样它也支持高效的点查和范围查。但却使用了完全不同的组织方式。
其特点有
以页在磁盘上叫 page在内存中叫 block通常为 4k为单位进行组织。页之间以页 ID 来进行逻辑引用从而组织成一颗磁盘上的树。查找。从根节点出发进行二分查找然后加载新的页到内存中继续二分直到命中或者到叶子节点。 查找复杂度树的高度 —— O (lgn)影响树高度的因素分支因子分叉数通常是几百个。 插入 or 更新。和查找过程一样定位到原 Key 所在页插入或者更新后将页完整写回。如果页剩余空间不够则分裂后写入。
分裂 or 合并。级联分裂和合并。
一个记录大于一个 page 怎么办
树的节点是逻辑概念page or block 是物理概念。一个逻辑节点可以对应多个物理 page。
让 B 树更可靠
B 树不像 LSM-Tree 会在原地修改数据文件。
在树结构调整时可能会级联修改很多 Page。比如叶子节点分裂后就需要写入两个新的叶子节点和一个父节点更新叶子指针。
增加预写日志WAL将所有修改操作记录下来预防宕机时中断树结构调整而产生的混乱现场。使用 latch 对树结构进行并发控制。
B 树的优化
B 树出来了这么久因此有很多优化
不使用 WAL而在写入时利用 Copy On Write 技术。同时也方便了并发控制。如 LMDB、BoltDB。对中间节点的 Key 做压缩保留足够的路由信息即可。以此可以节省空间增大分支因子。为了优化范围查询有的 B 族树将叶子节点存储时物理连续。但当数据不断插入时维护此有序性的代价非常大。为叶子节点增加兄弟指针以避免顺序遍历时的回溯。即 B 树的做法但远不局限于 B 树。B 树的变种分形树从 LSM-tree 借鉴了一些思想以优化 seek。
B-Trees 和 LSM-Trees 对比 存储引擎 B-Tree LSM-Tree 备注 优势 读取更快 写入更快 写放大 1. 数据和 WAL 2. 更改数据时多次覆盖整个 Page 1. 数据和 WAL 2. Compaction SSD 不能过多擦除。因此 SSD 内部的固件中也多用日志结构来减少随机小写。 写吞吐 相对较低 1. 大量随机写。 相对较高 1. 较低的写放大取决于数据和配置 2. 顺序写入。 3. 更为紧凑。 压缩率 1. 存在较多内部碎片。 1. 更加紧凑没有内部碎片。 2. 压缩潜力更大共享前缀。 但紧缩不及时会造成 LSM-Tree 存在很多垃圾 后台流量 1. 更稳定可预测不会受后台 compaction 突发流量影响。 1. 写吞吐过高compaction 跟不上会进一步加重读放大。 2. 由于外存总带宽有限compaction 会影响读写吞吐。 3. 随着数据越来越多compaction 对正常写影响越来越大。 RocksDB 写入太过快会引起 write stall即限制写入以期尽快 compaction 将数据下沉。 存储放大 1. 有些 Page 没有用满 1. 同一个 Key 存多遍 并发控制 1. 同一个 Key 只存在一个地方 2. 树结构容易加范围锁。 同一个 Key 会存多遍一般使用 MVCC 进行控制。
