最新要闻
- 【天天快播报】促消费,振内需,康佳加速业务高质量发展
- 世界第一名宇航员!尤里·加加林坠机遇难地点照片首次公开
- 每日看点!真的可以免费坐高铁了!用12306积分兑换:官方教程收好
- 焦点速递!杭州地铁现打工人专线 网友:通勤都不让闲着
- 环球观察:《指环王:力量之戒》片场马匹死亡 动保组织谴责:剥削动物
- 魅族20系列大杯曝光:120Hz E6直屏、12GB+512GB组合
- 核磁共振增强剂的危害_核磁共振增强剂的危害
- 环球热文:高德、阿里云发布全新车路协同方案 夜间开车像开了上帝视角
- 世界热文:瑞幸咖啡被吐槽喝完3口剩下全是冰 客服:门店按配方比例制作
- 世界快消息!育碧正式宣布“单飞”:E3展会再失重要参展商
- 独此一家!真我GT Neo5 SE梦幻续航组合:100W快充+5500mAh电池
- 每日速递:迪士尼《小美人鱼》真人电影确认引进内地:或5月上映
- 世界热点!各部队加强即将退役人员保密教育的一组见闻
- 焦点速递!男子2天喝4顿后死亡 起诉店家获赔:医生称如此喝酒很伤身
- 全球实时:价格相差数倍!智能手表比智能手环强在哪里?
- 昔日明星掌机落幕:任天堂正式关闭3DS游戏商店
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
数据密集型应用存储与检索设计
本文内容来自《数据密集型应用系统设计》(大名鼎鼎的 DDIA)。
高分好书
什么是「数据密集型应用系统」?
当数据(数据量、数据复杂度、数据变化速度)是一个应用的主要挑战,那么可以把这个应用称为数据密集型的。与之相对的是计算密集型——处理器速度是主要瓶颈。
其实我们平时遇到的大部分系统都是数据密集型的——应用代码访问内存、硬盘、数据库、消息队列中的数据,经过业务逻辑处理,再返回给用户。
(相关资料图)
查询类型
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 是查询 Key
- Value 是 KV 条目的起始位置和
看来很简单,但这正是Bitcask的基本设计,但关键是,他 Work(在小数据量时,即所有 key 都能存到内存中时):能提供很高的读写性能:
- 写:文件追加写。
- 读:一次内存查询,一次磁盘 seek;如果数据已经被缓存,则 seek 也可以省掉。
如果你的 key 集合很小(意味着能全放内存),但是每个 key 更新很频繁,那么 Bitcask 便是你的菜。举个栗子:频繁更新的视频播放量,key 是视频 url,value 是视频播放量。
但有个很重要问题,单个文件越来越大,磁盘空间不够怎么办?
在文件到达一定尺寸后,就新建一个文件,将原文件变为只读。同时为了回收多个 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 有序。我们称这种格式为:SSTable(Sorted 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 进行控制。 |
关键词:
数据密集型应用存储与检索设计
当前头条:范畴论:迷人的数学花园
环球观天下!智能存储重磅上线:低成本闲时转码
【天天快播报】促消费,振内需,康佳加速业务高质量发展
世界第一名宇航员!尤里·加加林坠机遇难地点照片首次公开
每日看点!真的可以免费坐高铁了!用12306积分兑换:官方教程收好
焦点速递!杭州地铁现打工人专线 网友:通勤都不让闲着
环球观察:《指环王:力量之戒》片场马匹死亡 动保组织谴责:剥削动物
魅族20系列大杯曝光:120Hz E6直屏、12GB+512GB组合
焦点快报!实验一 密码引擎-2-电子钥匙功能测试
CNStack 虚拟化服务:实现虚拟机和容器资源的共池管理
每日视讯:ChatGPT软件技术栈解密
天天微速讯:具有FTP、FTPS和sftp功能的文本编辑器——EditPlus功能介绍
今日热搜:【解答】MySQL MTR的实现原理与优势
核磁共振增强剂的危害_核磁共振增强剂的危害
环球热文:高德、阿里云发布全新车路协同方案 夜间开车像开了上帝视角
世界热文:瑞幸咖啡被吐槽喝完3口剩下全是冰 客服:门店按配方比例制作
世界快消息!育碧正式宣布“单飞”:E3展会再失重要参展商
独此一家!真我GT Neo5 SE梦幻续航组合:100W快充+5500mAh电池
每日速递:迪士尼《小美人鱼》真人电影确认引进内地:或5月上映
世界短讯!关于ChatGPT的一些信息,我画了一张思维导图
当前头条:前端设计模式——解释器模式
世界热点!各部队加强即将退役人员保密教育的一组见闻
焦点速递!男子2天喝4顿后死亡 起诉店家获赔:医生称如此喝酒很伤身
全球实时:价格相差数倍!智能手表比智能手环强在哪里?
昔日明星掌机落幕:任天堂正式关闭3DS游戏商店
最新消息:李想:攻破燃油车 需3步
当前简讯:任天堂爆款续作!《塞尔达传说:王国之泪》新实机今晚公布:5月12日发售
全球今热点:头铁面试官:一个小小的 System.out.println 硬是考了我半个小时,被问懵了。。
【天天播资讯】《Flask Web 开发指南 pt.1》
环球信息:日本北海道一养鸡场发生禽流感疫情
库克喊话:苹果和中国市场30年来密切关联 我们相互成长
今日热讯:告别物理卡槽!iPhone 15将进一步普及eSIM:水货机今后更难了
老人推倒摩托继承人被判赔1.6万元:车主直言被网曝 老人违法不该被宽恕
全球简讯:【国际大宗商品早报】隔夜外盘商品大面积反弹 美油涨超5%芝加哥农产品全线上涨
全球快报:最“丑”绿色车牌或在2年内取消 网友热议电车优待早该结束!国人将车牌代表面子
全球信息:2022年中国市场最畅销10款手机:国人狂买iPhone 13 高端安卓泪奔
天天视讯!昔日超市霸主 家乐福中国内地首店关闭:在北京开了28年
焦点快播:禁售时间已明确 油车还能开多久?中石油回应:新能源拐点还有很长路
天天微头条丨读Java性能权威指南(第2版)笔记30_Java服务器
世界热点评!Linux -mv命令的10个实用例子
全球看热讯:日本动漫演唱会_日本动漫
环球信息:【Visual Leak Detector】配置项 MaxDataDump
C++ 整理
OpenYurt v1.2 新版本深度解读(三):五步搭建一个OpenYurt集群
焦点速读:海外工具站 2022 复盘:商业认知篇
环球关注:泪目!孩子给离世父亲发短信被回复:爸爸也想你
1只花豹偷袭2只大猩猩:居然 全死了?
环球今日讯!别等魔兽国服了 暴雪今日开放全新服务器:自己单干
当蒂法换上《生化4》艾达王的装束:淡妆浓抹总相宜
全球观速讯丨软件、电影、游戏都“免费” 俄罗斯称盗版不再违法:要让奈飞破产
环球看点!樊小纯
前沿热点:美团面试:熟悉哪些JVM调优参数?
全球快看:基于.NET Core + Jquery实现文件断点分片上传
北京白领通勤天花板,单手拎起10秒折叠,网友:老板我需要
今日讯!针刺成小儿科?埃安官宣弹匣电池2.0枪击试验发布会
世界微资讯!手撕HashMap
每日资讯:一些面试高频题目
Synchronized详解
第134篇:解决浏览器的CORS跨域问题(CORS policy: Cross origin requests are only supported for p
环球观速讯丨《生化危机4:重制版》DLC正在开发中 艾达王是你的了
每日快播:深圳暴雨致航班取消 旅客情绪崩溃 跪求起飞 机场回应
环球通讯!全明星的三大遗憾,成就了这场本土篮球盛宴的缺憾之美
【Visual Leak Detector】配置项 AggregateDuplicates
Python毕业设计推荐
实时焦点:RTX 4070定了!还是你们讨厌的192位显存
每日看点!彻底没救了!《Forspoken》发售2个月后:RTX 4090依旧无法60帧
【播资讯】100亿捐款建大学 曹德旺:对标美国斯坦福 每个学生补贴5万
每日信息:做出莫斯利安的光明乳业:掉队了
女员工请假做试管婴儿被拒遭辞退 法院判了:恢复合同
环球观察:Vue 核心(二)
观焦点:HDFS Short-Circuit Local Reads
货币市场日报:3月27日
热消息:4月10日上市 福特F-150猛禽烈焰风暴特别版官图发布 为中国市场而
能抄底了?一汽奥迪补贴经销商清库存 明星车型降价近10万
每日看点!马云回国首谈ChatGPT:机器只有“芯”而人有“心”
国产车赢麻了!报告:中国品牌占俄罗斯新车销量近40%
焦点信息:“高端家用车”?比亚迪汉DM-i试驾 极致的油耗和空间
天天视讯!国产两轮电动车龙头!雅迪2022年营收310亿创纪录:电动自行车销量大增
焦点!通胀压力缓解避险情绪收敛 日债收益率周一全线回升
世界速读:商品日报(3月27日):沪锡领涨纯碱09合约增仓上行 苹果大幅下挫跌超4%
速读:前备箱门锁失灵?特斯拉扩大召回进口Model S
京东方iPhone 15灵动岛屏被曝漏光 苹果搬来三星救火:提前生产
天天热点评!女子赏花站梨树枝头甩衣狂摇 拍摄者:花瓣掉落一地
观热点:女子吃自助餐将店内甲鱼煮食 网友:是个狠人
乌鲁木齐周生生黄金价格多少钱一克(2023年3月27日)
新动态:CodeIgnitor 3.0.x 之 db 类实现机制
第一次博客
环球热点评!小皮Windows web面板漏洞详解
世界观速讯丨【原型设计工具】上海道宁为您提供Justinmind,助力您在几分钟内形成原型,并现场测试,无需编写任何代码
女生从俄罗斯花2分钟回国吃麻辣烫 挑战全网最短留学距离:网友感慨真近
环球观点:文心一言升级版!百度发布企业级大模型服务平台“文心千帆”
当前速讯:太危险!女子驾驶保时捷玩具车上机动车道吓坏路人:自称为了好玩
承认造假丑闻!百年日企川崎重工形象崩塌:鞠躬道歉
资讯推荐:男子跑滴滴1单挣了3148元:光等待费就两千多元
环球要闻:从GPT-4、文心一言再到Copilot,AIGC卷出新赛道?
即时:【必须收藏】别再乱找TiDB 集群部署教程了,这篇保姆级教程来帮你!!| 博学谷狂野架构师
当前关注:C#多态性学习,虚方法、抽象方法、接口等用法举例
python中index()、find()方法
每日视点!便宜香港主机推荐