万字长文,深入浅出讲解分布式数据库TiDB架构设计

2024年 5月 20日 55.5k 0

TiDB概述

TiDB 是一款开源 分布式关系型数据库,同时支持 在线事务处理(OLTP) 与 在线分析处理(OLAP) 的混合型(Hybrid Transactional and Analytical Processing, HTAP) 分布式数据库,具备水平扩容或缩容、金融级高可用、实时 HTAP、Kubernetes 云原生的分布式数据库、兼容 MySQL 5.7 协议和 MySQL 生态等重要特性,支持在本地和云上部署。

万字长文,深入浅出讲解分布式数据库TiDB架构设计-1

与传统的单机 MySQL 数据库相比,TiDB 具有以下优势:

  • 分布式架构: 纯分布式架构,拥有良好的扩展性,支持弹性的扩缩容
  • 兼容MySQL: 支持 SQL,对外暴露 MySQL 的网络协议,并兼容大多数 MySQL 的语法,在大多数场景下可以直接替换 MySQL
  • 高可用部署: 默认支持高可用,在少数副本失效的情况下,数据库本身能够自动进行数据修复和故障转移,对业务透明
  • 支持强一致性: 符合CAP理论的CP,支持 ACID 事务,对于一些有强一致需求的场景友好,例如:银行转账
  • 丰富的开源生态链: 具有丰富的工具链生态,覆盖数据迁移、同步、备份等多种场景

TiDB组件

在内核设计上,TiDB 分布式数据库将整体架构拆分成了多个模块,各模块之间互相通信,组成完整的 TiDB 系统。对应的架构图如下:

万字长文,深入浅出讲解分布式数据库TiDB架构设计-2

计算引擎层:TiDB/TiSpark

OLTP计算引擎TiDB

TiDB Server 主要用于 OLTP 业务,属于 SQL 层,对外暴露 MySQL 协议的连接 endpoint,负责接受客户端的连接,执行 SQL 解析和优化,最终生成分布式执行计划。

TiDB 层本身是 无状态的,实践中可以启动多个 TiDB 实例,通过 负载均衡组件(如 LVS、HAProxy 或 F5)对外提供统一的接入地址,客户端的连接可以均匀地分摊在多个 TiDB 实例上,以达到 负载均衡 的效果。

TiDB Server 本身并不存储数据,只是解析 SQL,将实际的数据读取请求转发给底层的存储节点 TiKV(或 TiFlash)。

OLAP计算引擎TiSpark

TiSpark 作为 TiDB 中解决用户复杂 OLAP 需求的主要组件,它将 Spark SQL 直接运行在 分布式键值对存储层 TiKV 上,同时融合 TiKV 分布式集群的优势,并融入 大数据社区生态。至此,TiDB 可以通过一套系统,同时支持 OLTP 与 OLAP,免除用户数据同步的烦恼。

万字长文,深入浅出讲解分布式数据库TiDB架构设计-3

TiFlash 和 TiSpark 都允许使用多个主机在 OLTP 数据上执行 OLAP 查询。TiFlash 是列式存储,它提供了更高效的分析查询。TiFlash 和 TiSpark 之间的关系,可类比于 Clickhouse 和 Spark。

分布式协调层:PD

PD (Placement Driver) 是整个 TiDB 集群的 元信息管理模块,负责存储每个 TiKV 节点实时的数据分布情况和集群的整体拓扑结构,提供 TiDB Dashboard 管控界面,并为分布式事务分配事务 ID。

PD 不仅存储集群元信息,同时还会根据 TiKV 节点实时上报的 数据分布状态,下发数据调度命令给具体的 TiKV 节点,可以说是 整个集群的“大脑” 。

此外,PD 本身也是由至少 3 个节点构成,拥有高可用的能力。建议部署奇数个 PD 节点。

存储引擎层:TiKV/TiFlash

行存储TiKV

用于存储 OLTP 数据,采用 行存储格式,支持 事务机制,TiKV 本身是一个 分布式的 Key-Value 存储引擎。

存储数据的基本单位是 Region,每个 Region 负责存储一个 Key Range(从 StartKey 到 EndKey 的左闭右开区间)的数据,每个 TiKV 节点会负责多个 Region。

万字长文,深入浅出讲解分布式数据库TiDB架构设计-4

  • TiKV 的 API 在 KV 键值对层面提供对分布式事务支持,默认提供了 SI (Snapshot Isolation) 的隔离级别。
  • TiDB 的 SQL 层做完 SQL 解析后,会将 SQL 的执行计划转换为对 TiKV API 的实际调用。
  • TiKV 支持高可用和自动故障转移,所有数据都会自动维护多副本(默认为三副本)。

列存储TiFlash

用于存储 OLAP 数据,和普通 TiKV 节点不一样的是,在 TiFlash 内部,数据是以 列存储格式,主要的功能是为分析型的场景加速。

万字长文,深入浅出讲解分布式数据库TiDB架构设计-5

上图为 TiDB HTAP 形态架构,其中包含 TiFlash 节点。TiFlash 提供列式存储,且拥有借助 ClickHouse 高效实现的协处理器层。

TiFlash 以 低消耗不阻塞 TiKV 写入的方式,实时复制 TiKV 集群中的数据,并同时提供与 TiKV 一样的 一致性读取,且可以保证读取到最新的数据。TiFlash 中的 Region 副本与 TiKV 中完全对应,且会跟随 TiKV 中的 Leader 副本同时进行分裂与合并。

TiFlash 可以兼容 TiDB 与 TiSpark 两种计算引擎,TiDB 适合用于中等规模的 OLAP 计算,而 TiSpark 适合大规模的 OLAP 计算。

TiDB计算引擎

SQL层架构

用户的 SQL 请求会直接或者通过 Load Balancer 发送到 TiDB Server,TiDB Server 会解析 MySQL Protocol Packet,获取请求内容,对 SQL 进行语法解析和语义分析,制定和优化查询计划,执行查询计划并获取和处理数据。整个流程如下图所示:

万字长文,深入浅出讲解分布式数据库TiDB架构设计-6

  • 用户发起请求: 数据库客户端向指定的 TiDB 集群发起请求。
  • 目标数据库响应: TiDB 集群指定 TiDB 节点响应用户的请求。
  • 两者建立会话: TiDB 集群其中一个 TiDB Server 节点与客户端建立会话。
  • 对象请求解析: TiDB Server 节点对接收到的请求进行语法检查、词法分析、对象解析,并将其转换为关系代数结构,然后完成执行计划优化。
  • 调度并且执行:  TiDB Server 根据 PD 寻找最合适的 TiKV 副本,根据优先级执行 SQL,按照内存、缓存、数据快照、磁盘存储的顺序查询。
  • 监测任务状态: TiDB Server 监测执行中任务的状态。
  • 返回数据结果: TiDB Server 将执行结果返回给数据库客户端。
  • 表数据映射到KV

    由于 TiDB 底层基于键值对存储数据,TiDB 表中的 行数据 需要按照一定格式映射转换为 键值对:

    • 为了保证同一张表的数据放在一起,方便查找,TiDB 会为每个表分配一个 表 ID,用 TableID 表示。表 ID 是一个整数,在整个 集群内唯一。
    • TiDB 会为表中每行数据分配一个 行 ID,用 RowID 表示。行 ID 也是一个整数,在表内唯一。对于行 ID,TiDB 做了一个小优化,如果某个表有整数型的主键,TiDB 会使用主键的值当做这一行数据的行 ID。

    每行数据按照如下规则编码成 (Key, Value) 键值对:

    Key: tablePrefix{TableID}_recordPrefixSep{RowID}Value: [col1, col2, col3, col4]

    表索引映射到KV

    TiDB 同时支持 主键索引 和 二级索引。与表数据映射方案类似,TiDB 为表中每个索引分配了一个 索引 ID,用 IndexID 表示。

    • 对于 主键索引 和 唯一索引,需要根据键值快速定位到对应的 RowID,因此,按照如下规则编码成 (Key, Value) 键值对:

    Key: tablePrefix{TableID}_indexPrefixSep{IndexID}_indexedColumnsValueValue: RowID

    • 对于非唯一性约束的 普通二级索引,一个键值可能 对应多行,需要根据 键值范围 查询对应的 RowID。因此,按照如下规则编码成 (Key, Value) 键值对:

    Key: tablePrefix{TableID}_indexPrefixSep{IndexID}indexedColumnsValue{RowID}Value: null

    KV映射示例

    数据与 KV 的映射关系,定义如下:

    tablePrefix     = []byte{'t'}
    recordPrefixSep = []byte{'r'}
    indexPrefixSep  = []byte{'i'}

    假设表结构如下:

    CREATE_TABLE User (
        ID int,
        Name varchar(20),
        Role varchar(20),
        Age int,
        UID int,
        PRIMARY KEY (ID),
        KEY idxAge (Age),
        UNIQUE KEY idxUID (UID)
    );

    假设表数据如下:

    1, "TiDB", "SQL Layer", 10, 10001
    2, "TiKV", "KV Engine", 20, 10002
    3, "PD", "Manager", 30, 10003
    • 表数据映射到KV如下:
    t10_r1 --> ["TiDB", "SQL Layer", 10, 10001]
    t10_r2 --> ["TiKV", "KV Engine", 20, 10002]
    t10_r3 --> ["PD",   "Manager",   30, 10003]
    • 唯一索引映射到KV如下:
    t10_i1_10001 --> 1
    t10_i2_10002 --> 2
    t10_i3_10003 --> 3
    • 非唯一索引映射到KV如下:
    # 假设 IndexID 为 1
    t10_i1_10_1 --> null
    t10_i1_20_2 --> null
    t10_i1_30_3 --> null

    TiKV存储引擎

    TiKV Region

    TiKV 可以看做是一个 巨大的、有序的 KV Map,为了实现存储的水平扩展,数据将被分散在多台机器上。对于一个 KV 系统,为了将数据 均衡分散 在多台机器上,通常有两种方案:

    • 一致性哈希(Hash): 按照 Key 做 Hash,根据 Hash 值选择对应的存储节点

    利用哈希函数将数据节点均匀打散到一个 0 ~ 2^32 - 1 的顺时针哈希环上面,对于数据的新增、查询和删除等操作者,首先通过同一个哈希函数计算数据的哈希值,然后再哈希环上顺时针寻址,找到第一个数据节点进行数据访问。如图所示:

    万字长文,深入浅出讲解分布式数据库TiDB架构设计-7

    • 连续分段哈希(Range): 按照 Key 分 Range,某一段连续的 Key 都保存在一个存储节点上

    TiKV 选择了 连续分段哈希(Range) ,将整个 Key-Value 空间分成很多段,每一段是一系列连续的 Key,将每一段叫做一个 Region,可以用 [StartKey,EndKey) 这样一个 左闭右开 区间来描述。每个 Region 中保存的数据量默认在 96 MiB 左右(可以通过配置修改)。

    万字长文,深入浅出讲解分布式数据库TiDB架构设计-8

    TiKV集群架构

    TiKV 参考 Google Spanner 论文设计了 multi-raft-group 的副本机制。它将数据 按照 key 的范围 划分成大致相等的分片 Region,每一个 Region 会有多个副本(默认是 3 个),其中一个副本是 Leader,提供读写服务。

    TiKV 通过 PD 对这些 Region 以及副本进行调度,以保证 数据负载 和 读写负载 都 均匀分散 在各个 TiKV 节点上,保证了整个集群资源的充分利用,并且可以随着 机器数量 的增加 水平扩展。

    万字长文,深入浅出讲解分布式数据库TiDB架构设计-9

    上图示意了一个典型的 TiKV 集群,中间有 4 个对等的 TiKV 节点,负责存放数据。其中一个 Region 存在3个副本,每个副本分布在不同的 TiKV 节点上。

    右边是PD 集群,负责提供集群的元数据服务,比如 TiKV 节点信息和数据的路由信息,即数据存放在哪个 TiKV 节点上。

    TiKV数据架构

    按 Range 分片存在的问题是,数据的写入、读取可能集中在某一个 Region 上,造成计算资源、存储空间的倾斜。因此,当一个 Region 的数据量 超过阈值 时,TiKV 自动将其 分裂 成多个更小的 Region;当一个 Region 的数据量 低于阈值 时,TiKV 自动将其与相邻的 Region 合并。

    万字长文,深入浅出讲解分布式数据库TiDB架构设计-10

    TiKV 采用了 分层架构设计,将功能划分为四个层级,每一层都只负责自己的事情。

    • TiKV API 负责 gRPC KV API 逻辑,Coprocessor API 负责 TiDB 的算子下推计算
    • Transaction 负责数据的读写冲突和事务的隔离性
    • Raft 负责节点间数据同步,保证数据的安全性
    • RocksDB 负责数据的存储

    网络层

    首先是网络层,TiKV 使用了高性能的 gRPC 作为网络通信框架。TiKV 对外暴露了多种形式的接口,包括支持事务的 KV 服务、高性能但不支持事务的纯 KV 服务,还有用于加速 SQL 查询的计算下推服务。

    事务层

    在网络层之下,是事务层。TiKV 实现了一个基于 Percolator 算法的事务处理机制,支持 乐观事务。此外,TiKV 还对 Percolator 做了改进,加入了对 悲观事务 的支持。

    用户可以根据业务负载特点,灵活选择 事务模式:

    • 如果业务依赖于 MySQL 事务 的行为,可以选择悲观事务模式
    • 如果业务冲突较少,则可以选择乐观事务,以获得更高的吞吐量和较低的延迟

    事务层提供了快照隔离的特性和事务 ACID 属性中的 ACI(原子性、一致性、隔离性)特性,而 D(持久性)特性由下一层实现。

    一致性层

    接下来是一致性层,该层提供了最基本的 键值操作接口,如 kv put/kv delete/kv get/snapshot。在一致性层内部,TiKV 实现了 Raft 一致性算法,保证 强一致性。

    TiKV 还扩展了 Raft 算法,并引入了 multi-raft 算法,使数据能够自动分片。通过 multi-raft 算法,每个 Region 的大小可以保持在大约 96MB,而 PD(Placement Driver)则可以通过调度实现水平扩展。

    存储层

    最底层是 RocksDB,作为高效的键值存储引擎,它是 TiKV 真正存储数据的地方。RocksDB 提供了 持久化存储的能力,并被 TiKV 内部的各个层级用来读写数据。

    万字长文,深入浅出讲解分布式数据库TiDB架构设计-11

    每个 TiKV 实例中有 两个 RocksDB 实例,一个用于存储 Raft 日志(通常被称为 raftdb),另一个用于存储 用户数据 以及 MVCC 信息(通常被称为 kvdb)。kvdb 中有四个 ColumnFamily:raft、lock、default 和 write:

    • raft 列: 存储各个 Region 的 元信息,仅占极少量空间。
    • lock 列: 存储悲观事务的 悲观锁,以及分布式事务的 一阶段 Prewrite 锁。当分布式事务提交之后,lock cf 中的数据会被快速删除。因此,大部分情况下 lock cf 中的数据也很少(少于 1GB)。
    • write 列: 存储 表数据 以及 MVCC 信息(该数据所属事务的开始时间以及提交时间)。当用户写入了一行数据时,如果该行数据长度小于 255 字节,那么会被存储 write 列中,否则该行数据会被存入到 default 列中。
    • default 列: 用于存储超过 255 字节长度的数据。

    把 TiKV 集群架构 和 数据架构 整合起来,TiKV 集群的数据存储结构大致如图所示:

    万字长文,深入浅出讲解分布式数据库TiDB架构设计-12

    RocksDB原理

    TiKV 使用 RocksDB 作为底层存储引擎,RocksDB 是一种 内嵌式 的 KV 存储引擎,因此可以将 RocksDB 理解为一个 单机持久化 Key-Value Map。

    由于 RocksDB 是 TiKV 底层存储的核心引擎,所以接下来会花大篇幅介绍 RocksDB 的 内部构造 和部分 优化原理。

    万字长文,深入浅出讲解分布式数据库TiDB架构设计-13

    RocksDB 是由 Facebook 基于 Google LevelDB 开发的一款提供键值存储和读写功能的 LSM-tree 架构引擎。

    可见,RocksDB 底层基于 LSM-tree 实现。LSM Tree(Log Structured Merge Tree,日志结构合并树) 是一种数据存储模型,而不是某一种具体的树型的数据结构。

    LSM 树的核心思想是顺序 IO 远快于随机 IO,因此适用于写多读少的业务场景。

    LSM Tree结构

    LSM树是一种用于 键值存储 的 数据结构。LSM 的基本思想是将所有的数据修改操作(如插入、更新、删除)都记录在一个 顺序日志文件 中,这个日志文件又称为 预写日志(Write-Ahead Log,WAL) 。顺序日志文件的好处是 顺序写入,相比 随机写入 的 性能更好。

    除了TiKV以外,Hbase、Cassandra和MongoDB等NoSQL底层的存储模型用的是LSM。

    万字长文,深入浅出讲解分布式数据库TiDB架构设计-14

    WAL(预写日志)

    为了防止 内存断电 而丢失,LSM 在写入 Memtable 之前,会先将 增删查改操作 备份到 WAL 磁盘日志,在系统故障时,WAL 可以用来恢复丢失的数据。

    WAL 是一个只允许追加的文件,包含一组更改记录序列。每个记录包含键值对、记录类型(Put / Merge / Delete)和校验和(checksum)。

    Memtable(内存表)

    Memtable 是 内存数据结构,可以使用 跳跃表 或 红黑树 来实现,以保持数据的 有序性。当 Memtable 达到一定的数据量后,Memtable 会转化成为 ****Immutable Memtable,同时会创建一个新的 Memtable 来存储新数据。

    跳表:跳表是一种非常简单的链状二分搜索结构,期望时间复杂度 O(log n) ,最坏 O(n)

    万字长文,深入浅出讲解分布式数据库TiDB架构设计-15

    Immutable Memtable(不可变内存表)

    Memtable 存储的数据达到一定数量后,就会把它拷贝一份出来成为 Immutable Memtable。

    Immutable Memtable 在内存中是 不可修改 的数据结构,它是处于 Memtable 和 SSTable 之间的一种 中间状态,目的是避免在转存过程中 不阻塞写操作。写操作可以由新的 Memtable 处理,避免由于 Memtable 直接写入磁盘造成的 IO 阻塞。

    SSTable

    内存中的 Immutable Memtable 是有大小限制的,需要 定期持久化 到磁盘上的 SSTable。

    SSTable 是 Sorted String Table 的简称,是一种 高性能 的 有序键值对 存储结构,由于键是有序的,查找键可以采用 二分搜索。

    为了优化读取性能,LSM 树使用了 多层级 的 SSTable 文件。具体来说,RocksDB 的 SSTable 从 Level 0 到 Level N 分为多层,每层包含多个 SSTable 文件。层级越高的 SSTable 数据越新,层级越低的 SSTable 数据越旧。

    SSTable 的基本组成部分包括:

    • 数据: 这是存储在 SSTable 中的实际数据。数据被组织成键值对,并且每个键值对都被写入到磁盘中。
    • 索引: 除了数据,SSTable 还包含一个索引,这个索引用于快速查找数据。索引包含了所有键的列表,以及每个键在数据中的位置。
    • 元数据: SSTable还包含一些元数据,如创建时间、最后修改时间等。

    SSTable 的优点包括:

    • 数据的有序性: SSTable 中的数据是有序的,这使得查找数据变得非常快速。
    • 数据的持久性: SSTable 中的数据被写入到磁盘中,因此即使在系统重启后,数据也不会丢失。
    • 数据的压缩: SSTable 中的数据被压缩,这使得存储的数据量更小,提高了存储效率。
    • 数据的恢复: SSTable 中的数据可以被恢复,这使得数据库的备份和恢复变得非常简单。

    RocksDB写操作

    RocksDB 中写入操作的原理见下图:

    万字长文,深入浅出讲解分布式数据库TiDB架构设计-16

  • 写入时首先写 WAL 日志文件,方便 进程闪崩 时可以根据日志快速恢复。
  • 将请求写入到内存中的跳表 SkipList 即 Memtable 中,立即 返回给客户端。当 Memtable 写满后,将其转换成 Immutable Memtable,并切换到新的 Memtable 提供写入。
  • RocksDB 在后台会通过一个 flush 进程 将这个 Memtable 刷新到磁盘,生成一个 Sorted String Table(SST) 文件,放在 Level 0 层,删除 对应的 WAL 日志。L0 层 的文件,是由内存中的 Memtable dump 到磁盘上生成的,单个 文件内部 按 key 有序,文件之间无序,而 L1 ~ L6 层 的文件都是按照 key 有序;
  • 当 Level 0 层 的 SST 文件个数超过 阈值 之后,就会通过 Compaction 策略 将其放到 Level 1 层,以此类推。每一层的数据是上一层的 10 倍(因此 90% 的数据存储在最后一层)。
  • RocksDB读操作

    RocksDB 中读取操作的原理见下图:

    万字长文,深入浅出讲解分布式数据库TiDB架构设计-17

  • 首先在 Memtable 中查找指定的 key,如果查到符合条件的数据,结束查找。
  • 然后在 Immutable Memtable 中查找指定的 key,如果查到符合条件的数据,结束查找。
  • 按 低层 至 高层 的顺序,从 level 0 层到 level 1 层的 SST文件 中查找指定的 key,如果查到符合条件的数据,结束查找,否则返回 Not Found 错误。
  • Compaction操作

    RocksDB 通过 追加写 的方式记录 数据修改操作:

    • Insert 操作: 直接写入新的 KV
    • Update 操作: 写入修改后的 KV
    • Delete 操作: 写入一条 tombstone 标记删除 的记录

    通过这种方式,将磁盘的 随机写入 转换为 顺序写入,提高了写入性能,但也带来了以下问题:

  • 大量的冗余和无效数据 占用磁盘空间,造成 空间放大。
  • 如果在内存中没有读取到数据,需要从 L0 层开始查找 SST 文件,造成 读放大。
  • 因此,RocksDB 引入了 compaction 操作,依次将 L(N) 层 的数据合并到下一层 L(N+1) 层,同时清理标记删除的数据,从而降低 空间放大、读放大 的影响。

    Compaction的机制

    RocksDB 在逻辑上把 SSTable 文件划分成 多个层级(7 层),并且满足以下性质:

  • 层级越高 说明其数据写入越早,即先往 上层进行 “放”(minor compaction) ,上层 “满”(达到容量限制) 之后 “溢”(major compaction)到下层 进行 合并。
  • 每层文件 总大小 都有限制,层级大小 成指数级增长。比如 L0 层 文件总大小上限为 10MB,L1 层 为  100MB,L21 层 为 1000MB。依次类推,最下层(L6 层)没有限制。
  • 由于 L0 层 每个 SSTable 文件 都是直接由 Memtable 落盘而来,因此 L0 层 多个 SSTable 文件的 key 范围可能会有 重合。而其他层(L1 ~ L6)的多个 SSTable 文件,则通过一些规则保证 没有重合。
  • Compaction的作用

  • 数据持久化: 将内存中的数据持久化到磁盘中的 SSTable 文件
  • 提高读写效率: 将 L0 层的 SSTable 文件合并为若干个 没有数据重合 的 L1 ~L6 层文件,避免多层无效遍历
  • 平衡读写差异: 当 L0 层SSTable 文件数量过多时,暂停 写入操作,直到 compaction 完成为止
  • 节约磁盘空间: 同一个 key 可能存在着多条数据,对不同版本进行 合并 可以节省磁盘空间。
  • Compaction的类型

    RocksDB 的 Compaction 操作分为两类,分别是 Minor Compaction 和 Major Compaction。

    • Minor Compaction

    Minor Compaction 是指将 Immutable MemTable 转存为 SSTable 文件写入 L0 层

    万字长文,深入浅出讲解分布式数据库TiDB架构设计-18

    • Major Compaction

    Major Compaction 是指 合并压缩 第 L(N) 层 的多个 SSTable 文件到第 L(N+1) 层

    万字长文,深入浅出讲解分布式数据库TiDB架构设计-19

    Major Compaction 的触发条件:

    当 L0 层 SSTable 文件数 超过预定的上限(默认为4个)

    当 L(N) 层文件的 总大小 超过(10 ^ i) MB

    当某个 SSTable 文件 无效读取 的次数过多

    布隆过滤器(Bloom Filter)

    为了减小 读放大 导致性能下降,RocksDB 采取了以下两种策略:

    • 通过 major compaction 尽量减少 SSTable 文件数
    • 使用 布隆过滤器,快速判断 key 是否在某个 SSTable 文件中

    布隆过滤器底层使用一个 位数组(bit array) ,初始集合为空时,所有位都为 0:

    当往集合中插入一个 数据 x 时,利用 k 个 独立的 哈希函数 分别对 x 进行散列,然后将 k 个散列值 按数组长度取余后,分别将位数组位置置为 1:

    万字长文,深入浅出讲解分布式数据库TiDB架构设计-20

    查找过程和插入过程类似,也是利用同样的 k 个哈希函数 对待 查找数据 按顺序进行哈希,得到 k 个位置。

    • 如果位数组中 k 个位置上的 位均为 1,则该元素 有可能 存在
    • 如果任意一位置上值为 位为0,则该值 一定不存在。

    布隆过滤器用于快速判断一条数据是否在集合中。其本质上是通过容忍一定的错误率,来换取时空的高效性。

    RocksDB 并未使用 k 个哈希函数,而是用了 double-hashing 方法,利用一个哈希函数达到近似 k 个哈希函数的效果。

    结语

    本文详细介绍了 TiDB 的核心组件,尤其是用于 OLTP 的分布式 计算引擎 TiDB 和分布式 存储引擎 TiKV。一方面阐述了 TiDB 是如何将 关系型表数据 、索引数据 转换为 键值对 数据;另一方面,深度剖析了 TiKV 内部的架构设计和原理,尾篇大幅介绍了 TiKV 底层引入的 单机键值对 数据库 RocksDB 的原理,一定程度让大家知其然也知其所以然。本文抛砖引玉,关于 TiDB 内部的分布式通信、一致性原理、MVCC、GC清理算法、一些巧妙数据结构,仍需大家深入研究方可融会贯通,活学活用。

    作者介绍

    陈林,51CTO社区编辑,某零售银行龙头DevOps持续集成平台技术负责人,主导核心业务方案设计落地,推动产品架构持续演进。

    相关文章

    Oracle如何使用授予和撤销权限的语法和示例
    Awesome Project: 探索 MatrixOrigin 云原生分布式数据库
    下载丨66页PDF,云和恩墨技术通讯(2024年7月刊)
    社区版oceanbase安装
    Oracle 导出CSV工具-sqluldr2
    ETL数据集成丨快速将MySQL数据迁移至Doris数据库

    发布评论