关于kylin:Apache-Kylin-40精确去重的全局字典原理

全局字典解说

为什么须要全局字典

在 OLAP 数据分析畛域，去重计数 (Count distinct) 是十分常见的需要，而依据去重后果的要求又分为近似去重和准确去重。

在大规模数据集下，要想做到准确去重还要保障查问疾速响应还是很有挑战性的。咱们晓得准确去重常常用到的解决形式就是位图法(Bit map)。对于整型数据，咱们能够将统计信息保留在 Bit map 中，然而理论解决的数据中除了整型还会有 String 等其余类型，如果想做到准确去重首先就须要构建一个字典来为这些数据进行对立映射, 而后再通过 Bit map 法进行统计。

咱们都晓得 Kylin 通过预计算技术来减速大数据分析。在增量构建 Cube 的时候，为了防止不同的 segment 独自构建字典导致最终去重后果出错，一个 Cube 中所有的 Segment 会应用同一个字典，也就是全局字典(Global Dictionary)。

全局字典的演变

Kylin 从 1.5.3 版本就开始反对全局字典性能，然而这时的构建形式也具备显著的缺点：

全局字典在 Job Server 上进行单点构建，随着数据增多构建时长变得不可控
随着数据积攒，全局字典的构建对 Kylin 构建节点的内存的需要会一直增多
受限于整型最大数量的限度
其实在 Kylin3.1 中曾经退出了基于 Hive 的分布式全局字典构建，它曾经解决了以上问题，详情能够查看 Kylin 分布式全局字典。然而 Kylin 4.0 为了适应全新的构建查问引擎，基于 spark 实现了另外一种分布式构建全局字典的形式，明天咱们就来详细描述一下 Kylin 4.0 的全局字典是如何实现的。

基于 Spark 的全局字典

Kylin 4.0 构建全局字典的形式基于 Spark 进行分布式的编码解决，减小了单机节点的压力，构建字典数量可能冲破整型最大数量的限度。

设计与原理

全局字典的构造

• 每一次构建工作会生成一份新的全局字典
• 每次新的构建工作的字典按版本号进行保留, 旧的全局字典会被逐步删除
• 一份字典包含一份 meta 数据文件和多个字典文件, 每个字典文件称之为桶(Bucket)
• 每个桶分为两个映射(Map<Object, Long>), 两者合并为残缺的映射关系

Bucket 的概念与转化

Kylin 引入了桶这一概念，能够了解为在解决数据的时候，将数据分到若干个桶 (即多个分区) 中进行并行处理。第一次构建字典的时候会对每个桶内的值从 1 开始编码，在所有桶的编码实现之后再依据每个桶的 offset 值进行整体字典值的调配。在代码中两次编码是通过两个 HashMap 进行存储的，其中一个存储桶内绝对的字典值，另一个存储所有桶之间相对的字典值。

下图所示的是编号为 1 的桶屡次构建工作中，桶内字典的传递，每一次构建都会为桶创立一个新的版本 (即 v1, v2, v3 等)，退出版本控制的起因前面会有解释。Curr(current) 和 Prev(Previous)是一个桶内的两个 HashMap，别离存储着以后桶内字典的绝对 (Relative) 编码值和之前曾经构建的所有字典值的相对 (Absolute) 编码值。

构建步骤

• 通过 Spark 创立平表并获取需准确去重列的 distinct 值
• 依据确定去重后的字面值数量来确认分片数, 并且依据需要判断是否须要扩容
• 将数据调配 (repartition) 到多个分片 (Partition) 中，别离进行编码, 存储到各自的字典文件中
• 为以后构建任务分配版本号
• 保留字典文件和 metadata 数据(桶数量和桶的 offset 值)
• 依据条件判断须要删除旧版本

首次构建

• 计算桶的大小
  取须要构建字典的数量解决单个桶阈值和桶数量默认值的最大值。
• 创立桶并调配数据进行编码
• 生成 meta 文件记录桶的 offsets

以下是相干配置项及其默认值。

kylin.dictionary.globalV2-min-hash-partitions=10
kylin.dictionary.globalV2-threshold-bucket-size=500000

非首次构建

• 依据字典数量确定桶是否须要扩容
• 已编码的字典值对扩容后的桶进行重新分配
• 读取之前最新版本的字典数据，并调配到各个桶中
• 将新的值调配到桶中
• 前一次构建的字典值不会扭转

版本控制

全局字典会通过给单次构建调配基于工夫戳的版本号来进行隔离。退出版本控制的起因是构建工作可能会并发执行，而以后构建全局字典过程中的编码是不反对并发。通过版本控制，每一次编码都可能残缺的读取之前构建好的全局字典，这样就保障了最新版本的字典领有最残缺的全局字典编码，而且一个 Cube 的全局字典每次被读取的时候都会选取最新版本的字典。字典最终在文件存储系统 (此处为 HDFS) 上按版本存储如下图所示。

常见问题

1. 为什么在一个 BucketDIctionary 须要应用两个 Map?

构建过程开始须要对调配到各个桶内的字典从 1 开始做一个绝对 (Relative) 编码，这一部分字典绝对编码值会存储在一个 HashMap 中，在绝对字典值编码实现后，会失去每个桶的 offset 值，也就是桶内字典的数量，而后依据这个字典值计算出每个桶 (桶是有程序的) 内字典值绝对于所有桶的 offset 值的相对 (Absolute) 编码, 字典的相对编码也会用另一个 HashMap 进行存储。

1. 会不会存在数据歪斜问题?

当初测试下来因为热点构建不进去的概率很小，个别歪斜十亿级别才会过不去, 列很多确实可能会造成这个问题, 不过编码的桶数是能够有限放大的 除非单 key 热点，否则调整参数也是很轻松实现构建。

1. 为什么全局字典的数量可能超过整型最大基数 (21 亿) 的限度？

因为引入了全新的 BitMap 数据结构 Roaring64BitMap，在全局字典编码实现之后, 编码会被压缩成二进制存储在 Roaring64BitMap 对象中，BitMap 实际上是通过 Long 而不再是 Integer 进行存储的。