分析型数据库、数据仓库
内部初名 Garuda，又名 ADS
整体架构
读写分离架构
计算存储分离
冷热数据分离
视角 1
前端节点（FN)
写入节点（BN）
计算节点（CN）
视角 2
第一层是接入层，由Mulit-Master可线性扩展的协调节点构成，主要负责协议层接入、SQL解析和优化、实时写入Sharding、数据调度和查询调度。
第二层是计算引擎，具备分布式MPP+DAG融合执行能力，结合智能优化器，可支持高并发和复杂SQL混合负载，同时借助于云原生基础设施，计算节点实现了弹性调度，可根据业务需求做到分钟级甚至秒级扩展，达到了资源的有效利用。
第三层是存储引擎，基于Raft协议实现的分布式实时强一致高可用存储引擎，通过数据分片和Multi-Raft实现并行，利用分层存储实现冷热分离降低成本，通过行列存储和智能索引达到极致性能。
关键技术
1、智能 sql 优化器
2、曦和计算引擎
3、玄武存储引擎
4、读写节点分离
5、硬件加速
静态分层模块
存储层（玄武引擎）
整体存储架构
- FrontNode（FN）
包括 W-FN（负责写入）、R-FN（负责查询）
FRONTNODE 主要负责SQL解析、查询结果汇聚，实时数据写入、DDL等功能。所有FN完全对等，节点之间完全无耦合，无单点故障。
- BufferNode（BN）
分布式的队列系统
支持多副本
master-slave 架构，可快速 failover
failover 期间，会有短暂的不可写，但是 CN 在此期间可以直接读取 pangu 的数据（写入宕机不影响查询）
- ComputeNode（CN）
计算节点，承担计算 + 存储的功能
不在写入链路上，不影响写入（流量反压的时候可能会）
每个节点上都包含历史的 cache 数据和实时数据两部分：加速分区列计算，避免数据 shuffle 和跨机计算
会定期去同步本地存储引擎中和 BN 有差异的数据
发展历程
第一代：普通的 OLTP 引擎
借鉴 H2 数据库的存储引擎：行存 + B+索引、支持事务
第二代：列存
列存的原理示意图
优点 ：压缩比高、自由选择压缩算法 -> 更低的 io 延迟
列存的天然优势：io 剪裁，只读取感兴趣的数据列
ADB 的列存，增加了三部分内容：分区、列和块三层meta
1、 分分区meta主要包括表的行数和列数，主要解决count(*)的性能问题。
2、 列meta主要包括：
- max、min：可以有效解决二级分区快速筛选
- sum，count，count distinct， null count： 可以加速sum/count/distinct 计算，同时该metrics可以提供给优化器选择最优执行计划。
- Dict： 针对cardinality较少的列（例如性别，星座），保存字典在该meta中，数据文件中保存字典序号（int 类型），既大大压缩了存储空间，又可以加速groupby、distinct 等算子的计算性能。
3、 块meta主要包括：
- max、min： 解决无索引条件下的，快速过滤功能。如果某条件与max、min无交集，则可以快速跳过该块。同时可以提高max，min算子的计算性能。
- sum： 提高sum算子计算性能。
- null count：支持快速filter 空值列。
其他：
1、 增加了二级分区。支持数据的生命周期管理，也即能够设置数据的保存期限，自动根据规则淘汰过期数据；
2、 实时化。这是另一个很大的话题，我们单独开了文章来介绍。请参见《超大规模的立即可见实时写入》。
第三代：行列混存
解决了的问题：
1、OLTP 的点查性能问题
解决办法： select *等由列存的完全随机读转化为了顺序读。
2、OLAP 的多维分析问题
解决办法：进行单列IO时将列存的顺序读转化为了顺序跳读；进行多列IO时则将随机读转化为了顺序读。
3、写入大吞吐的问题：每天千亿级别实时数据写入
解决办法：列存时的随机写被转化为了顺序写。
AnalyticDB也支持了另外两项重要功能：
1）clustered by预排序功能。该功能将某一列或某几列的数据进行排序后，存放到磁盘上。从而保证了相同数据在磁盘上连续存储。对于等值查询、范围查询都能够大幅减少需要IO的block数，实现查询加速。
2）分层存储。将SSD盘作为本地cache，确保热点数据查询性能，同时降低了总体存储成本。
第四代：定长存储
即以byte为单位将block真正变为定长。
解决结构化、非结构化数据存储问题
下一代：HTAP
展望
索引
全索引
多列、多条件同时走索引，快速多路合并，可以在毫秒级内找出结果集
根据成本估计，智能选择走索引还是扫描
支持的索引类型
1、 倒排索引
基于 lucene
目前Lucene采用Prefix+Sufix字典压缩term，倒排链中保存的是递增行号集合，采用Delta+Vint压缩算法，压缩比可以达到1：4。同时所有查询过程为顺序读，解压速度达到900MB/s。
2、Bitmap 索引
对于散列度较低的列，自动构建 bitmap 索引，降低存储空间
3、 范围索引
解决 lucene 的范围索引问题
先生成直方图数据分布，将所有数据切分为多个互不相交的区间，并将每个区间作为一个Bitmap索引
查询时，范围条件被拆成多个or 条件的组合。例如数据被切成[0,10),[10,20), [30,40),[40,50)等区间，
如：条件 x > 5 and x < 45，会被转换为 (5, 10)，[10, 20), [20, 30),[30, 40), [40, 45)多个or条件。
4、全文索引
5、向量索引
6、json 索引
。。。
索引优化
1、 索引结果缓存
2、CBO（基于代价优化）
根据 index 中的统计信息
根据 meta 中的统计信息
3、无索引查询优化
多没有构建索引的列，也能根据统计，做一些加速，减少 io
4、流式归并
传统的数据处理系统在所有查询条件计算完毕后，将结果集一次性合并完毕。
而AnalyticDB采用了流式归并方法，按需将结果集进行合并。该方法的一大优点是：一旦满足了计算需求，就会触发早停逻辑，避免了不必要的结果合所带来的CPU、内存消耗 。
例子：
where ( (姓名=‘张三’ AND 性别!= ‘女’ ) AND (籍贯 = ‘山西’ OR 籍贯 = ‘安徽’)) OR (工作 like ‘建筑%’ OR 工作like ‘%酒吧%’)
5、结构化、非结构化的融合检索
能够在进行等值、范围、多值列检索的同时，进行文本的匹配和计算，为大数据分析带来了新的可能性
SQL 解析层
主要的优化手段
1、执行下推
执行下推是将SQL中可以依赖存储能力的关系代数计算进行提取，将查询计划等价转换为两部分，一部分在计算层执行，一部分下推给存储层执行
2、基于代价的查询优化器
3、查询计划缓存及调整
执行计划
传统的火山执行引擎
生成一系列的算子（operator)
存在的问题：
1、代价很高的解释开销
2、较低的 cpu cache 命中率
next()是虚函数，导致 cpu 预测错误，耗费大量无用的 cpu 时间
基于字节码生成技术的算子优化
使用 asm 技术，对 sql 算子进行特定的优化，如 for 循环、switch 等
计算层（Lambda 结构）
每个 CN 节点都无状态
每个 CN 内部，数据分为两部分：
- 全量
- 全索引
- 列存储
全量数据走全索引查询
- 增量
分两步查询：
1）利用block 级别索引剪裁无用block；
2）对有用数据块扫描；
两部分的结果汇总作为该分区的查询结果。
会定期合并增量数据 -> 全量数据（重新排序 + 重建索引）
离线完成，不影响 CN 的查询（解耦）
硬件加速
使用 GPU 对一些可并行的逻辑进行加速
1、 使用 gpu 进行聚合、join、hash 等计算
2、cpu、gpu 混合计算
执行计划层面、算子执行层面
3、gpu 代码动态生成技术
基于 llvm，根据逻辑执行计划，动态生成 gpu 物理执行计划
4、显存管理技术
5、GPU 解压技术
用 gpu 来进行数据解压缩，大幅提升性能
动态流程
实时写入流程
可横向扩展 FN、BN
写入不受制于某节点，完全松耦合、易扩展
注意：
1、BN 会定时将数据推送给 CN
2、CN 也会在需要的时候去 BN 里查数据
性能
写入速度上，单DB（20个FN）写入速度达到280W条每秒，每天入库数据量1600亿条，同时写入数据大小达到600MB每秒。
查询过程
解析层生成执行计划（一个 DAG），然后生成物理执行计划（一系列的 task、operator 等）
FN 接收到请求，向 BN 收集涉及表的分区和最新写入的版本号
将查询的请求和版本号一起发给 CN
CN 对比本地的版本号和请求中的版本
若 CN 本地的版本号小于请求的版本，则去 BN 中拉取最新的数据（可以保证写入实时可见）
若 CN 本地的版本号大于等于请求的版本，则直接用 CN 本地的最新版本
然后进行数据查询操作
参考文档
2、ADB 的论文
https://www.vldb.org/pvldb/vol12/p2059-zhan.pdf
