Dorisdb

<article class=“article fmt article-content”><p>作为OLAP数据库，StarRocks 诞生之初的外围应用场景就是统计报表，防止不了有统计去重的需要。</p><p>以如来的业务需要举例，在统计命中某个标签的人数时，显然是须要基于用户ID去重的。 </p><p>海量数据的去重，是不能应用传统的 count distinct 形式的，例如下图2个BE节点上的数据，就须要进行屡次运算。</p><p></p><p>StarRocks 提供两种高效的去重办法：</p><ul><li>BitMap：对应 BITMAP_UNION</li><li>HyperLogLog：对应 HLL_UNION</li></ul><p>还记得聚合表中：BITMAP_UNION、HLL_UNION 两个函数吗，对应的就是这里的去重形式。</p><h2>1. Bitmap 去重</h2><h3>1.1. 原理</h3><p>Bitmap 去重可能 精确计算 一个数据集中不反复元素的数量，相比传统的 Count Distinct，能够节俭存储空间、减速计算。</p><p>例如，给定一个数组 A，其取值范畴为 [0, n)，可采纳 (n+7)/8 的字节长度的 bitmap 对该数组去重。</p><p>行将所有 bit 初始化为 0，而后以数组 A 中元素的取值作为 bit 的下标，并将 bit 置为 1，那么 bitmap 中 1 的个数即为数组 A 中不同元素 (Count Distinct) 的数量。</p><p>劣势次要体现在以下两点 ：</p><blockquote><strong>（1）节俭存储空间</strong></blockquote><p>通过用 Bitmap 的一个 Bit 位示意对应下标是否存在，能节俭大量存储空间。例如，对 INT32 类型的数据去重，如应用一般的 bitmap，其所需的存储空间只占 COUNT(DISTINCT expr) 的 1/32。</p><p>StarRocks 采纳一种设计的非常精美的 bitmap，叫做 Roaring Bitmap，相较 Bitmap 会进一步缩小内存占用。</p><blockquote><strong>（2）减速计算</strong></blockquote><p>Bitmap 去重应用的是位运算，所以计算速度相较 COUNT(DISTINCT expr) 更快，而且 bitmap 去重在 StarRocks MPP 执行引擎中还能够并行减速解决，进步计算速度。</p><h3>1.2. 举例</h3><p>1、建表</p><p>创立一张聚合表 page_uv。其中 visit_users 列示意拜访用户的 ID，为聚合列，列类型为 BITMAP，应用聚合函数 BITMAP_UNION 来聚合数据。</p><pre><code class=“sql”>CREATE TABLE page_uv ( page_id INT NOT NULL COMMENT ‘页面id’, visit_date datetime NOT NULL COMMENT ‘拜访工夫’, visit_users BITMAP BITMAP_UNION NOT NULL COMMENT ‘拜访用户id’) ENGINE=OLAPAGGREGATE KEY(page_id, visit_date)DISTRIBUTED BY HASH(page_id)PROPERTIES ( “replication_num” = “3”, “storage_format” = “DEFAULT”);</code></pre><p>2、向表中导入数据。</p><p>采纳 INSERT INTO 语句导入：</p><pre><code class=“sql”>INSERT INTO page_uv VALUES(1, ‘2020-06-23 01:30:30’, to_bitmap(13)),(1, ‘2020-06-23 01:30:30’, to_bitmap(23)),(1, ‘2020-06-23 01:30:30’, to_bitmap(33)),(1, ‘2020-06-23 02:30:30’, to_bitmap(13)),(2, ‘2020-06-23 01:30:30’, to_bitmap(23));</code></pre><p>数据导入后:</p><ul><li>在 page_id = 1， visit_date = ‘2020-06-23 01:30:30’ 数据行，visit_users 字段蕴含 3 个 bitmap 元素（13，23，33）；</li><li>在 page_id = 1， visit_date = ‘2020-06-23 02:30:30’ 的数据行，visit_users 字段蕴含 1 个 bitmap 元素（13）；</li><li>在 page_id = 2， visit_date = ‘2020-06-23 01:30:30’ 的数据行，visit_users 字段蕴含 1 个 bitmap 元素（23）。</li></ul><p>统计去重的人数能够用 bitmap_union_count，也能够还用 count distinct，StarRocks 会将其主动转换为 bitmap_union_count 函数：</p><pre><code class=“sql”>select bitmap_union_count(visit_users) from page_uv group by page_id</code></pre><h3>1.3. 阐明</h3><p>Bitmap index 和 Bitmap 去重二者尽管都应用 Bitmap 技术，但引入起因和解决的问题齐全不同。前者用于低基数的枚举型列的等值条件过滤，后者则用于计算一组数据行的指标列的不反复元素的个数。</p><p>StarRocks 的 bitmap 去重是基于 Roaring Bitmap 实现的，roaring bitmap 只能对 TINYINT，SMALLINT，INT 和 BIGINT 类型的数据去重。如想要应用 Roaring Bitmap 对其余类型的数据去重，则须要构建全局字典，将其余类型数据（如字符串类型）通过全局字典映射成为整数类型。</p><p>Bitmap 是一种数据类型，尽管 BITMAP_UNION 函数是聚合表中的函数，但不是只有聚合表能力创立 Bitmap 类型指标列。甚至表中某列的数据类型是int，然而在查问时能够通过 to_bitmap 函数，将其转换为 Bitmap 类型再进行位运算。间接存储 Bitmap 类型列，是为了缩小存储空间、查问更快。</p><p>从 StarRocks 2.3 版本开始，所有类型的表均反对设置指标列为 BITMAP 类型，然而所有类型的表不反对设置排序键为 BITMAP 类型。</p><p>因为 Bitmap 是准确去重，存的是理论值，因而能够通过 bitmap_to_string 函数，将 Bitmap 类型数据转换为逗号分隔（当有多个元素时）的字符串，查看原始int值。</p><h2>2. HyperLogLog</h2><h3>2.1. 概念</h3><p>HLL（HyperLogLog）是一种 近似去重 算法，当数据量达到肯定水平，Bitmap 准确去重也会比较慢，在对去重精度要求不高的场景下，能够抉择应用 HLL 加重计算压力。HLL 算法的误差可管制在 1% 至 10% 左右，数据量越大，误差越小。</p><p>应用 HLL 去重，须要在建表语句中，将指标指标列的类型设置为 HLL，聚合函数设置为 HLL_UNION。<br/>这里要留神，只有 聚合表 反对 HLL 类型列。</p><h3>2.2. 举例</h3><p>1、建表</p><p>创立聚合表，存储 union_id、member_id HLL类型：</p><pre><code class=“sql”>CREATE TABLE xxx_hll ( ts DATETIME NOT NULL COMMENT “工夫”, scene VARCHAR(128) COMMENT “场景编码”, ab VARCHAR(40) COMMENT “ab分流内容”, union_id_hll HLL HLL_UNION COMMENT “unionId近似去重”, member_id_hll HLL HLL_UNION COMMENT “memberId近似去重”)AGGREGATE KEY(ts, scene,ab)PARTITION BY RANGE(ts)(PARTITION p20240114 VALUES LESS THAN (“2024-01-15”))DISTRIBUTED BY HASH(ts,scene,ab) BUCKETS 8PROPERTIES( … );</code></pre><p>2、StarRocks 通过 Stream Load 导入 columns 为：</p><pre><code>ts,scene,ab,union_id,member_id,union_id_hll=hll_hash(union_id),member_id_hll=hll_hash(member_id)</code></pre><p>3、查问去重的 union_id、member_id 数量SQL为：</p><pre><code class=“sql”>SELECT hll_union_agg(union_id_hll),hll_union_agg(member_id_hll) from buddha_user_hit_scene_ab_hll</code></pre><p>和 Bitmap 相似，此时应用 count distinct 成果一样，StarRocks 会将其主动转换为 hll_union_agg</p><h3>2.3. HLL 原理</h3><h4>2.3.1. 伯努利试验</h4><p>HLL算法的数学根底是伯努利试验，这里用最直白的形式带大家了解这个算法过程。</p><p>伯努利试验 是在同样的条件下反复地、各次之间互相独立地进行的一种试验，试验就两种后果。</p><p>最常见的伯努利试验就是抛硬币，只有正、反两面后果，而且每次抛硬币的后果可能性都是二分之一。</p><p>当初试验规定设定为：每轮试验抛硬币，如果呈现背面就持续抛，如果呈现侧面就完结本轮试验，咱们记录本轮试验一共抛了几次。</p><p>能够计算概率：</p><ul><li>试验抛了1次的概率是：1/2，第1次抛就是侧面，概率是1/2。</li><li>试验抛了2次的概率是：1/4，即第1次抛是背面，第2次是侧面，概率是 1/2 * 1/2。</li><li>试验抛了3次的概率是：1/8，即第1次抛是背面，第2次是背面，第3次是侧面，概率是 1/2 <em> 1/2 </em> 1/2。</li><li>… …</li><li>试验抛了n次的概率是：1/2^n。</li></ul><p>意味着要进行 2^n 轮试验，才可能呈现一轮抛了 n 次才呈现侧面的试验。</p><p>如果你通知我，你进行了有数轮试验，这些试验中单轮抛了最多的次数，是100次。我大略能够揣测出你进行了 2^100 轮试验。</p><p>极大似然预计中，试验的基数越大，后果误差越小。这里的基数就是进行多少轮试验，HLL 是一种基数估算算法。只须要记录目前所有试验中单论抛了最多的次数，就能够估算试验基数是多少。即理论数据库中能够只存储数值 n，能够预估统计数量 2^n 。</p><h4>2.3.2. HLL算法的实现</h4><p>后面解说如何通过伯努利试验的思维预估宏大的数量，那么 HyperLogLog 算法具体是如何实现这个思维的呢？</p><p>还记得在写入hll类型数据时，都通过 hll_hash 转换一下：<code>union_id_hll=hll_hash(union_id)</code></p><p>这也是一种 hash 算法，每写入一条数据，就将 union_id 通过 hash 转换成二进制，假如二进制如下：</p><p><em>hash(record) = 011… 00101101110</em></p><p>二进制中只有0和1，咱们能够定义1是抛硬币的侧面，0是背面。只有 hash 算法足够均匀，就能保障二进制中每一位呈现0、1的概率都是1/2。</p><p>上述二进制值，从低位开始，记录第一个呈现1的位数（抛了侧面），这里就是第2位。数据库中hll字段就存储值2就能够了。</p><p>因为是聚合表，当每次有排序键雷同的数据写入表中时，记录第一个呈现1的位数，如果比以后 hll 类型字段的值大就替换，否则就抛弃。</p><p>然而以前学概率时老师常说，小概率事件却常常产生！如果说运气好，第一轮试验就抛了十几次，那后续几百轮的误差都会很大，HyperLogLog 算法有什么优化形式吗？ 求和谐平均数</p><h4>2.3.3. 求和谐平均数</h4><p>和谐平均数公式为：</p><p></p><p>和谐平均数 和 平均数 有啥区别吗？举个例子就分明了：</p><p>比方我的工资1千块，我共事的工资10万元一个月，求咱们公司平均工资。</p><ul><li>平均数 = (1000+100000)/2 = 50500 (元)</li><li>和谐平均数 = 2/(1/1000 + 1/100000) ≈ 1980 (元)</li></ul><p>显著和谐平均数更正当。因为和谐平均数的后果会偏向于汇合中比拟小的数。</p><p>在 HyperLogLog 算法中，hll 数据结构会分成多个桶，二进制数据会将第一个呈现1的位数最大值存到随机一个桶内，而后基于各个桶内统计的值求和谐平均数。</p><p>Redis 中同样有 HyperLogLog 构造，它会将存储的数据 hash 成64位二进制，取其中14位决定数据落入哪个桶内（2^14，能够有16384个桶），剩下50位存储数据，即伯努利试验最多有50轮，单个 hll 数据结构能够预估的最大值是 2^50，有1千多万亿。</p><p>50的二进制是110010，最多须要6个bit寄存。16384个桶，每个桶存6个bit，则一共不到12kb，就能预估1千多万亿数据。</p></article> ...