BaikalDB技术实现内幕(二)

Stella981
• 阅读 634

本系列文章主要介绍HTAP数据库BaikalDB的技术实现细节。

作者介绍:黄文亮,百度商业平台研发部资深研发工程师,主要负责BaikalDB索引能力,性能优化等方向的研发工作。

欢迎关注 Star github.com/baidu/BaikalDB 国内加速镜像库gitee

BaikalDB系统简介

BaikalDB是一个分布式可扩展的存储系统,兼容MySQL协议,整个系统的架构如下图所示:

BaikalDB技术实现内幕(二)

  • BaikalStore 负责数据存储,数据分区按region组织,三个Store的三个region形成一个 Raft-group 实现三副本,多实例部署,Store实例宕机可以自动迁移 Region数据;
  • BaikalMeta 负责元信息管理,包括分区,容量,权限,均衡等, Raft 保障的3副本部署,Meta 宕机只影响数据无法扩容迁移,不影响数据读写;
  • BaikaDB 负责前端SQL解析,查询计划生成执行,无状态全同构多实例部署,宕机实例数不超过 qps 承载极限即可;

Baikal 命名由来

贝加尔湖(Baikal)是世界上最大的淡水湖,相当于北美洲五大湖水量的总和,超过整个波罗的海水量,淡水储量占全球20%以上。西伯利亚总共有336条河流注入贝加尔湖。冬天的贝加尔湖畔,淡蓝色的冰柱犹如分布式数据库一列列的数据密密麻麻但是有井然有序,令人惊艳。

BaikalDB技术实现内幕(二)

BaikalDB索引介绍

BaikalStore 对数据按照主键进行 range 划分形成多个 region,region 按行存的形式将数据组织为主键索引及二级索引,这些主键索引、二级索引编码为key、value 值写入本地 Rocksdb 中。

BaikalDB 索引主要包含以下五种,其中主键索引存储主表数据的所有字段,二级索引存储主键字段。

  • 主键索引(PRIMARY KEY)
    • 主键索引是 BaikalDB 针对主键创建的索引,主键 key 值必须唯一。BaikalDB 使用主键值将整个表进行 range 划分为多个 region 分区。
  • 局部二级索引
    • 普通索引(KEY)
    • 唯一索引(UNIQUE KEY)
  • 全局二级索引(GLOBAL KEY)
  • 倒排索引(FULLTEXT KEY)

本文以如下 schema 为例,对各索引类型的编码进行一一介绍。

CREATE TABLE example (
    field0 bigint(20) NOT NULL ,
    field1 bigint(20) NOT NULL DEFAULT '0' ,
    field2 bigint(20) NOT NULL DEFAULT '0' ,
    field3 bigint(20) NOT NULL DEFAULT '0' ,
    field4 bigint(20) NOT NULL DEFAULT '0' ,
    field5 varchar(20) NOT NULL DEFAULT '',
    PRIMARY KEY (field0),
    KEY index2 (field2),
    UNIQUE KEY index3(field3),
    KEY GLOBAL index4(field4),
    FULLTEXT KEY index5(field5)
)

主键索引

  • 主键:PRIMARY KEY (field0)

  • 主键索引将主键字段与一行数据做映射,并最终形成一个按主键 key 排序内存/磁盘结构,方便用户快速通过主键 key 进行定位或扫描。

  • 主键 key 值包含64 Bit region_id、64 Bit index_id、primary key 值组成。其中 region_id 为 region 的标识 id,在 region 生成时指定。index_id 为的索引标识 id, 在表创建时生成。在该示例中,primary key 值为字段 field0 的值,为64 Bit。

  • 主键 value 值为表 schema 对应动态 protobuf 反序列化之后的值。 上述 schema 对应的动态 protobuf 结构为:

    message example { optional int64_t field0 = 0; optional int64_t field1 = 1; optional int64_t field2 = 2; optional int64_t field3 = 3; optional int64_t field4 = 4; optional string field5 = 5; };

BaikalDB技术实现内幕(二)

局部二级索引

  • 所谓局部二级索引,就是主表数据和索引数据在同一分片上,每个分片就包含了该分片上信息的全部索引。局部二级索引又分为普通二级索引、唯一二级索引。
  • 二级索引将二级索引字段与主键 key 做映射,可以加速二级索引字段的查找或扫描。

局部索引

  • 索引:KEY index2 (field2)
  • key 值 包含64 Bit region_id、 64 Bit index_id、8 Bit 空字节、 index key值、primary key 值组成。其中 index key 值为 字段 field2 的值,为 64 Bit。(注:其中8 Bit 空字节已废弃,不体现在索引使用示例小节中。)
  • value 值 为空串 ""

BaikalDB技术实现内幕(二)

局部唯一索引

  • 唯一索引:UNIQUE KEY index3(field3)
  • key 值 包含64 Bit region_id、64 Bit index_id、8 Bit 空字节、 index key 值。(注:其中8 Bit 空字节已废弃,不体现在索引使用示例小节中。)
  • value 值为 64 Bit primary key 的值。

BaikalDB技术实现内幕(二)

全局二级索引: GLOBAL KEY index4(field4)

  • 所谓全局二级索引,就是主表数据和索引数据不在同一个分片上,所有分片的二级索引数据集中存储。
  • 相对于局部二级索引,全局二级索引的优势是:在没有具体分片信息,利用二级索引反查主键时,局部二级索引需要扫描所有分片,而全局二级索引只需要扫描单分片。
  • 全局二级索引也分为普通索引、唯一索引,编码规则与局部索引一致。

倒排索引: FULLTEXT KEY index5(field5)

  • BaikalDB 支持倒排索引,主要用来进行快速的全文检索。BaikalDB 倒排索引主要涉及索引构建及检索:
    • 构建:将正排字段切词为一或多个 term。构建 term 的有序倒排拉链,并按照格式进行存储。
    • 检索:根据检索词,对多个倒排拉链进行布尔查询。 下面对上述两个步骤,进行示例说明。
  • 切词:下图为以field5作为倒排索引字段的切词示例:

BaikalDB技术实现内幕(二)

  • 倒排存储:将所有正排按照词(term)粒度进行合并,建立倒排索引,并使用 Rocksdb 进行存储。其中 key 值为 64 Bit region_id、64 Bit index_id、分词后的 term ,value 值为排序之后的主键键值。(下图为简化模型,BaikalDB中实际使用分层存储)

BaikalDB技术实现内幕(二)

上述示例中 term 的倒排拉链的存储格式如下:

BaikalDB技术实现内幕(二)

  • 倒排检索:根据检索词对多个倒排拉链进行布尔逻辑检索。上例中检索词为 “倒排|索引”、“测试&倒排” 检索词的多排序表的合并结果如下图所示。其中“倒排|索引”检索词,将“倒排”及"索引"的倒排拉链进行并运算;“测试&倒排” 检索词,将“测试”及“倒排”的倒排拉链进行与运算。

BaikalDB技术实现内幕(二)

索引使用示例

为了更好的说明 BaikalDB 中的索引使用方式,下面给出4个示例,分别展示在数据的写入及读取过程中,主键索引、二级索引、全局二级索引所起的作用。

示例一:insert

  • sql : insert into example values (0,1,2,3,4,"测试倒排")
  • 整体流程
    • 根据表 example 的 schema 信息,生成动态 message,并设置各 field 值:{"field0" : 0, "field1" : 1, "field2":2, "field3" : 3, "field4":4, "field5":"测试倒排"}
    • 根据主键值(field0=0),定位到目标 region 分片。
    • 将动态 message 序列化之后,传给目标 region 分片。
    • 目标 region 分片分别对各索引生成对应格式的 kv 值,写入底层rocksdb。
    • 将全局索引写入全局索引分片。
    • 完成写入
  • 流程图

BaikalDB技术实现内幕(二)

示例二:select(不使用二级索引)

  • 不使用索引 sql:select * from example where field4 = 4;
  • 整体流程:
    • 根据sql,生成执行计划:因 field4 字段不在二级索引中,只能遍历主索引,并进行过滤。
    • 因没有主键条件,向所有 region 分片广播执行计划。
    • scan node 执行过程:在所有 region 分片中,编码主键前缀 key 值:(region_id、index_id),对 Rocksdb 中所有主键进行顺序扫描。
    • filter node 执行过程:对扫描出的所有主键 kv 中, 使用动态生成 protobuf 对 value 值进行反序列化,并提取出 field4 值。对解析出的 field4 值进行过滤,获取满足条件(field4 = 4)的结果。
    • 组装各 region 分片中的返回值,打包返回给用户。
  • 流程图

BaikalDB技术实现内幕(二)

示例三:select(使用二级索引)

  • 使用索引 sql:select * from example where field2 = 2;
  • 整体流程
    • 根据sql,生成执行计划:使用索引 index2 进行扫描。
    • 因没有主键条件,向所有 region 分片广播执行计划
    • scan node 执行过程:在 region 分片中,编码 index2 的 key 值(region_id、index_id、field2、primay_key),在 Rocksdb 中前缀扫描。
    • 在 Rocksdb 中 key 中,提取出 field0 值,构造主键 key,反查主键,解析所有字段。
    • 组装各 region 分片中的返回值,打包返回给用户。
  • 流程图

BaikalDB技术实现内幕(二)

示例四:select(使用全局二级索引)

  • 使用索引 sql:select * from example where field4 = 4;
  • 整体流程
    • 根据sql,生成执行计划:首先使用全局索引 index4 进行扫描,查出主键值之后,扫描主键值对应的分片。
    • 全局索引 scan node 执行过程:根据全局索引字段 feild4 ,定位全局索引分片,发送请求获取主键键值。
    • 根据主键键值,定位 region 分片信息。
    • 主键索引 scan node 执行过程:在 region 分片中,编码主键 index0 的 key 值(region_id、index_id、field0),在 Rocksdb 中前缀扫描。
    • 组装各 region 分片中的返回值,打包返回给用户。

BaikalDB技术实现内幕(二)

示例分析

  • 写入(insert)场景
    • 可以很好的利用 region 分片特性,只对部分 region 进行写入操作。
  • 查询(select)场景
    • 局部二级索引:使用恰当的索引对整体性能的提升有很大帮助。如示例2中,在没有二级索引的情况下,需要扫描所有主键 kv;然后进行 protobuf 反序列化;最后进行字段过滤。而在示例3中,只需要扫描部分二级索引。
    • 全局二级索引:在示例3中,虽然在单分片中,性能较好,但因为没有主键信息,所以需要广播所有分片,进行查询。考虑到较大的表可能有多达万级的分片数量,所以整个开销还是较大的。这种场景下可以使用全局二级索引,根据索引字段查出主键值,然后只需要查询已知主键值对应的分片即可,而不需要广播所有分片。

总结

本文对 BaikalDB 中的各种索引类型的编码方式、使用方法进行了简要的说明。如果你有兴趣继续深入了解,欢迎加入https://github.com/baidu/BaikalDB。

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
3个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
Android So动态加载 优雅实现与原理分析
背景:漫品Android客户端集成适配转换功能(基于目标识别(So库35M)和人脸识别库(5M)),导致apk体积50M左右,为优化客户端体验,决定实现So文件动态加载.!(https://oscimg.oschina.net/oscnet/00d1ff90e4b34869664fef59e3ec3fdd20b.png)点击上方“蓝字”关注我
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Stella981 Stella981
3年前
BaikalDB技术实现内幕(一)
本系列文章主要介绍HTAP数据库BaikalDB的技术实现细节。作者介绍:罗小兵(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fgithub.com%2Fluobuda),百度商业平台研发部高级研发工程师,主要负责BaikalDB事务能力,全局二级索引等方向的研发工作。
Stella981 Stella981
3年前
BaikalDB技术实现内幕(三)
本系列文章主要介绍HTAP数据库BaikalDB的技术实现细节作者简介:于正泉,百度商业平台研发部高级研发工程师。主要从事分布式存储、分布式数据库等领域的工作,现主要负责BaikalDBSQL性能优化,稳定性相关方向的研发工作。欢迎关注Stargithub.com/baidu/BaikalDB(https://www.
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
9个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这