电话咨询

0571-89852485

工作日 9:30-18:00

在线咨询

架构师咨询

kudu 存储引擎简析

2017-12-25     作者:宋洋
本篇文章仅限本站分享,如需转载,请联系网易获取授权。
欢迎技术交流和讨论:bigdata@service.netease.com

1 概述

  本文主要介绍kudu底层存储引擎的数据组织方式,先看整体结构如下:

  一张表会分成若干个tablet,每个tablet包括MetaData元信息及若干个RowSet,RowSet包含一个MemRowSet及若干个DiskRowSet,DiskRowSet中包含一个BloomFile、Ad_hoc Index、BaseData、DeltaMem及若干个RedoFile和UndoFile(UndoFile一般情况下只有一个)。

  MemRowSet用于新数据insert及已在MemRowSet中的数据的更新,一个MemRowSet写满后会将数据刷到磁盘形成若干个DiskRowSet。

  DiskRowSet用于老数据的mutation,后台定期对DiskRowSet做compaction,以删除没用的数据及合并历史数据,减少查询过程中的IO开销。

  BloomFile根据一个DiskRowSet中的key生成一个bloom filter,用于快速模糊定位某个key是否在DiskRowSet中存在。

  Ad_hoc Index是主键的索引,用于定位key在DiskRowSet中的具体哪个偏移位置。

  BaseData是MemRowSet flush下来的数据,按列存储,按主键有序。

  UndoFile是基于BaseData之前时间的历史数据,通过在BaseData上apply UndoFile中的记录,可以获得历史数据。

  RedoFile是基于BaseData之后时间的mutation记录,通过在BaseData上apply RedoFile中的记录,可获得较新的数据。

  DeltaMem用于DiskRowSet中数据的mutation,先写到内存中,写满后flush到磁盘形成RedoFile。


2 MemRowSet

  MemRowSet的数据组织形式是一颗B+Tree,结构如下:

  这颗B+树实现的比较简单,因为它没有update跟delete操作,kudu在MemRowSet中中数据的mutation采用类似append log方式,在base数据上有个mutation指针,所有的后续mutation操作都挂在这个指针上了。

  虽然只有插入,但是也会出现节点满时需要做split,同时可能有读操作也在同步进行,kudu使用AtomicVersion(原子变量+位移)实现了一个锁。树的度跟cpu的CACHELINE_SIZE有关,是为了让一个节点仅读取一次cpu cache。

  树的检索是先找到key所在的LeafNode,然后在LeafNode内部进行二分查找,LeafNode间有指针进行串联,为了方便scan,扫整个MemRowSet一般通过一个空串的key找到第一个LeafNode,然后依次读数据。


3 DiskRowSet

  这部分是kudu存储部分最复杂的东西,分为两个部分来讲,DiskRowSet间的组织,DiskRowSet内数据组织,先看DiskRowSet间怎么组织的。

3.1 DiskRowSet间组织

  一个tablet随这数据的不断写入会包含很多个DiskRowSet,每个DiskRowSet上有min_key、max_key标明key的范围,如果要查找一个key在哪个DiskRowSet上依次遍历每个DiskRowSet效率是很低的,这种情况线段树这种数据结构是很适合做range索引的,将所有的DiskRowSet形成一颗线段树,结构如下:

  其实就是一个二叉平衡树,每次从所有range(最小的min_key跟最大的max_key)的中间key做split,将range跨域左右子树的DiskRowSet(即split point落在DiskRowSet的min_key与max_key之间)放到overlap rowsets中去。这颗树实现的也很简单,因为它只做查询用,生成后就不会变动,若遇到MemRowSet flush或DiskRowSet Merge Compaction就直接重新生成一颗新树。

  这个树主要用于在读或写的时候定位某个或若干个key在哪些DiskRowSet的range范围内,只能通过DiskRowSet的min_key/max_key做一层模糊过滤,是否正在存在需要做进一步检查。

3.2 DiskRowSet内数据组织

  一个DiskRowSet大体数据组织上面概述中已介绍过,其中DeltaMem跟MemRowSet在内存中的组织方式是一样的,都是B+Tree,而在磁盘上的存储都是放在CFile中的,下面我们看看CFile的文件格式:

  CFile包含Header、Data、Index、Footer几块,其中Data部分起始部分是为空值的条目建立的bitmap,仅针对可为null的column,对于主键是没有这个的,bitmap就是以那些值为null的RowId建立起来的位图,这样Data中就不用存这些空值。data部分不同的column类型文件会有不同的编码方式:

  对于ad_hoc文件使用的是prefix,delta file使用的是plain,bloomfile使用的是plain。每种BlockBuilder在处理一定量数据后就会append到Data中。

  Index有两种,posidx_index是根据RowId找到在Data中的偏移,validx index是根据key的值找到在Data中的偏移,validx只针对只有一个column为key的情况,这个时候DiskRowSet没有Ad_hoc索引,使用validex来代替。这两个index内部实现是一个B-Tree,index不一定是连续的,在达到一定长度后就会刷盘,而内部可以区分是中间节点还是叶子节点及其孩子节点的位置。

  Footer是记录了CFile的元信息,包括posidx_index、validx_index两棵树根节点所在位置,数据条目、编码、压缩方式等。

  下面看看DiskRowSet数据在磁盘上的分布:

  在磁盘上每个DiskRowSet有若干个***.metadata及***.data文件,metadata文件记录的是DiskRowSet的元信息,主要包括哪些block及block在data中的位置,上图为block与DiskRowSet中各部分的映射关系,在写磁盘是通过container来写,每个container可以写很大一块连续的磁盘空间,用于给某个CFile写数据,当一个CFile写完后会将container归还给BlockManager,这时container就可以用于下个CFile写数据了,当BlockManager中没有container可用时会新建一个container给新来的CFile使用。

  对于新建block先看看有无container可用,若没有目前默认是在所有配置中的data_dir中随机选取一个dir中建一个新的metadata及data文件。先写data,block落盘后再写metadata。


  对于kudu底层数据存储就介绍到这里,希望对大家有所帮助。

立即下载

格式不正确
格式不正确
格式不正确
请输入正确的验证码
请选择职位