首页 > 其他分享 >system desing 系统设计(十五):数据存储data storage和检索retrieval原理概述

system desing 系统设计(十五):数据存储data storage和检索retrieval原理概述

时间:2022-10-06 23:36:17浏览次数:80  
标签:存储 log 数据 storage system 索引 内存 磁盘 data

    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

相关文章