10年前,big data火遍全球,进而带动了数据存储的大发展!互联网大厂动辄数亿的DAU,每天带来了PB级别的新增数据;这么多数据,正确、快速的存储和精准、高效的查询/检索成了当务之急,由此带来了各种数据库的发展:有OLTP事务型的,有OLAP分析型的,也有专门做倒排检索(Elastic search)的,还有专门做传输的MQ(其实本质也是存储),每一种类型的数据库细分又有很多产品,这么多的数据库,底层数据都是怎么存储和检索的了??又是怎么达到正确快速存储、精准高效检索的了?总的来说,按照存储引擎来划分,数据的存储和检索有这么两类:
- 基于page页的存储引擎:比如B+树,代表作mysql
- 基于log日志的存储引擎:比如 LSM-tree了,代表作hbase、leveldb等!
1、因为mysql很出名,B+树大家都很熟悉了吧!为什么mysql会那么流行了?我个人认为原因如下:
- 早期开源,被很多技术大佬协同支持
- 早期互联网很多都是读多写少的场景,比如各种bbs论坛、新闻等,非常适合B+树这种数据结构
- 数据按行组织,是典型的结构化数据,理解起来很方便
- 能够存储千万级别的数据:这里以innoDB为例:第一层和第二层都是索引【如果第一、二层有data,会极大减少索引的数量,进而减少树的覆盖范围】,第三层是data了!mysql每次读取16KB的数据,每个索引按照10byte计算,3层树形可以支持千万级别的数据检索【2层索引能覆盖(16*1024/10)*(16*1024/10) =256w个数据块;假设每条数据1KB,那么每个数据块有16KB/1KB=16条数据,所有数据块能存储256*16=4096w条数据】;
- B+树把索引和数据都放磁盘,价格比内存便宜很多,两种存储介质对比如下:
价格问题是解决了,磁盘读写速度比内存低的问题怎么解决了?那就只能让磁盘顺序读写了【所以mysql以16KB为颗粒度读写数据,避免频繁寻址浪费时间】,速度比随机寻址读写快很多倍,虽说还是比不上内存,但耐不住磁盘价格便宜啊!
- 上面解决了数据的快速写入和查询问题,但新问题又来了:如果对每条记录都建一个索引,索引本身的数量是巨大的,维护索引自生的开销都很大,这样做值得么?为每条数据都建索引的原因很简单:每条数据的长度是不固定的,所以被迫记录每条数据的起始位置offset+len,导致整个索引非常庞大;既然以数据行为最小颗粒度建索引会导致开销庞大,为啥不以数据块为颗粒度建索引了?(这就是稀疏索引,clickhouse是每8192条数据凑成一个数据块);比如mysql就是以16KB为颗粒度切分data block的!每个datablock又编号,记录了保存数据的范围;然后每个block也会维护一个index:每行数据的offset和size,检索的时候先定位block,再根据offset+size定位具体的数据!注意:block之间的数据是有序的,block内部的数据也是有序的,才能支持快速地支持单行检索和范围查找!如果数据只是简单存储不排序,就会“退化”成MessageQueue(kafka就是这样的)!
最后总结一下为什么要选择B+树:
基于B+树引擎的优缺点:
2、B+树是树形结构,每次有数据增加或删除的时候需要重新调整和维护这个结构,所以数据写入的效率就打折扣了,所以B+树适合写少读多的场景,其本质上是用写入的“低效”换取读取的“高效”!既然有适用于读多写少的数据结构,那有没有适合于写多读少(日志系统、推荐系统、数据的挖掘/统计分析等)场景的数据结构和算法了?这就是LSM tree了!
- 之前介绍过Big Table的原理,这里的LSM是基于Big Table改进而来的!用户的所有操作会先被写到日志,这就是传说中的write ahead log,简称WAL!
- 利用磁盘顺序IO效率高的特点,所有的操作都append到log文件,写入确实爽歪歪了,查询了?要从log文件头开始挨个遍历,找到数据后需要根据日志的记录做增删改等操作,效率极低,怎么提升读的效率了?
- 增加一个bloomFilter,遍历文件前先看看key是不是有,如果没有就没必要遍历log文件了。
- 定时整理和合并log文件,只保留最终结果,增删改的过程都去掉(合并log文件会消耗大量的cpu和IO,所以hbase是可以配置合并log文件时间的,一般情况可以设置为凌晨使用低谷期时合并)
- log文件必须有序,便于后续通过二分法查找key;
- 为了进一步提速,可以先把部分操作缓存在内存,达到一定阈值后再写入磁盘的文件(所以同样的数据会有两份:内存和WAL各一份)。详细如下:
数据的整个流转流程如下:先顺序写入WAL日志,再写入内存的table。达到一定阈值后写入磁盘的SSTable文件保存!
为了确保快速查找,数据不论是在内存、还是磁盘中都是有序的,所以合并后的结果还是有序的,比如内存的数据和磁盘数据合并后还是树形结构,示意如下:
SSTable的格式如下:前部分是KV结构,后面是index索引结构;查询的时候先从index开始找到key的offset,再根据offset在前部分找value!
- 数据增删改的问题解决了,接下来就是查询了,流程如下:
由于lastest数据会先放内存,所以最现在memTable找。找不到了再往后去磁盘的SSTable找,这就是LSM查找效率不如B+树的根本原因!
- 由于这种算法自身的特性,存在读放大read amplification、空间方法space amplification和写放大write amplification等缺陷,建议的解决办法如下:
最后老规矩做个总结:
参考:
1、https://www.bilibili.com/video/BV16X4y1A7TV/?vd_source=241a5bcb1c13e6828e519dd1f78f35b2
2、https://cs.umb.edu/~poneil/lsmtree.pdf
3、https://juejin.cn/post/6844903863758094343
4、https://www.cnblogs.com/zxporz/p/16021373.html 5、https://www.bilibili.com/video/BV1Zz4y1r7BJ/?spm_id_from=333.337.search-card.all.click&vd_source=241a5bcb1c13e6828e519dd1f78f35b2 标签:存储,log,数据,storage,system,索引,内存,磁盘,data From: https://www.cnblogs.com/theseventhson/p/16757775.html