文章目录
- <1%的“异常”查询影响OLAP引擎的稳定性
- 基于规则判断的方式比较粗糙，只能解决部分问题
- 借鉴数据库Query Optimizer思想建立查询成本指标
-
- 扫描数据量预估
- 返回结果集预估
- 返回结果集基数预估的修正
- 确定成本阈值
- 基于SparkSQL的实现方案
-
- 统计每个时间片中数据总行数
- 统计每列数据的直方图信息
- 后记
-
- 多OLAP引擎联合支撑
- 基于HyperLogLog算法预估结果集基数
随着用户分析数据量的急剧增长与用户多维实时交互分析数据的需求，OLAP引擎成了交互式数据分析的标配。
<1%的“异常”查询影响OLAP引擎的稳定性
如何保证让OLAP引擎能稳定高效地提供数据服务，是普遍面临的一个问题。而影响OLAP引擎稳定性的一大原因是来自用户的“异常”查询：用户由于错误操作或确实基于合理需求而触发的大查询可能会挤占整个集群的资源甚至会让集群崩溃，从而影响到其他用户的正常使用，甚至造成数据的丢失。
通常的做法是拦截或者采用其他计算引擎如SparkSQL来处理这些“异常”查询，这都首先要求能很好的识别这些“异常”查询。
基于规则判断的方式比较粗糙，只能解决部分问题
首先想到的是基于预定规则判断的方式来识别并拦截用户的大查询，这也是目前大多数系统的解决方案。一般是通过限制用户查询数据的时间跨度与同时查询展开的维度两个视角来进行识别拦截，如：
- 用户的查询跨度不能超过3个月；
- 用户查询的展开维度不能同时超过5个；
由于规则依据比较简单固定，不能根据数据的特性进行调整，因此识别“异常”查询的准确度比较差。这种方案存在以下不足：
- OLAP引擎多采用列存储，那在限制查询时间跨度时是不是需要根据用户查询的字段数量进行动态调整？
- 不同字段数据类型及其数据内容差异很大，是不是也应该差异对待？
- 不同维度的基数差异很大，且会随着时间变化，在限制维度展开时是不是应该根据维度的基数进行动态调整？
基于规则判断的方式比较粗糙，只能解决部分问题。那有更加智能的方式识别“异常”查询吗？
借鉴数据库Query Optimizer思想建立查询成本指标
总结分析发现“异常”查询主要有两大特点：
- 一是因为扫描处理的数据量太大从而占用过多的集群资源，影响对其他用户查询的响应；
- 二是由于返回的结果集太大对节点造成很大的内存压力，甚至导致集群节点OOM崩溃。
因此识别“异常”查询问题的本质就是计算评估查询的成本，这自然联想到关系数据库的Query Optimizer。数据库的优化器有两大类：基于规则的RBO优化器和基于成本的CBO优化器。RBO规则优化器只能承载一些明确的、简单的预定义规则，应用范围比较有限。而基于成本的CBO优化器被所有数据库广泛使用，不一样的只是不同数据库会定义不同的成本指标与优化函数。因此可以建立评估“异常”查询的成本指标：
COST1 = 扫描数据量
COST2 = 返回结果集
“异常”查询 = COST1 > Threshold1 or COST2 > Threshold1
这样识别“异常”查询的问题就转化为对扫描数据量和返回结果集大小的预估，并根据其对集群稳定性影响的大小来评估确定两个阈值。
扫描数据量预估
目前几乎所有的OLAP引擎都采用列存储来存储数据，相比行存储来说需要扫描的数据量小并且数据压缩率更高。由于列存储中不同列是分开独立存储的，则可以根据用户查询需要扫描的列以及各列占用存储的大小来评估查询要扫描的数据量。
// row_number表示查询时间范围内的总行数
// col1_bytes、col2_bytes分别表示各列数据占用的平均字节大小
扫描数据量 = row_number * (col1_bytes + col2_bytes + ...)
OLAP引擎为了加速查询都会对各列数据建立稀疏索引，同时在BI系统中用户的查询往往会带有一些筛选项（通常是对维度的某几个枚举进行筛选，而且各维度间的筛选条件是与的方式联结），那是不是可以对上述的评估方法进行修正？如果能根据维度列的筛选项对满足筛选条件的数据量进行预估（可依据下一小节的直方图统计信息预估），则可以将扫描数据量预估方法进行修正：
// col1_row_number、col2_row_number分别表示各列满足筛选条件的行数，如该列没有筛选条件，则其等于总行数row_number
// col1_bytes、col2_bytes分别表示各列数据占用的平均字节大小
扫描数据量 = (col1_row_number * col1_bytes + col2_row_number * col2_bytes + ...)
维度类型可分为可枚举的维度和不可枚举的维度。对于可枚举维度来说，用户往往是给定几个筛选项来进行选择，如选择某个商品。对于不可枚举维度来说，用户往往是给定一个筛选区间来进行选择。这两种情况都可以使用列数据直方图的统计信息预估满足条件的数据量。
返回结果集预估
在数据库中预估返回结果集基数大小cardinality-estimation多采用列直方图预估的方式实现，假设在一个直方图区间中值的分布是均匀的。其通过扫描各列数据，预先统计各列数据分布的直方图信息，以年龄列统计的等高直方图为例：
由于列数据中值的分布往往是不均匀的，因此直方图统计多采用等高直方图（即各区间的宽度是动态不固定的，而落入每个区间中的值的个数是相同的即等高）的方式。上图中ndv表示每块中不同值的个数即基数。
示例一：对于给定枚举值的基数预估，如预估age = 27的基数。
// 此类情况的基数预估比较简单，直接等于筛选值的个数
// 由于筛选值在数据中不一定存在，是不是可以建立每个区间的Bloom filter来进一步判断值是否存在？
返回基数ndv = 1
// 由于是等高直方图，因此每个区间的值个数为5，而第二个区间中不同值的个数为3，因此可预估age=27的数据量
扫描数据量 = 5 * 1 / 3 = 1.67
示例二：对于给定范围的基数预估，如age > 38的基数。
// 范围命中了最后两个区间，根据每个区间的划分范围和其基数大小进行预估
返回基数ndv = (40-38)/(40-28)*4 + (80-40)/(80-40)*5 = 5.67
// 范围命中了最后两个区间，每个区间中值的个数为5
扫描数据量 = (40-38)/(40-28)*5 + (80-40)/(80-40)*5 = 5.83
因此返回结果集预估的成本指标函数如下：
// 返回结果集基数等于各返回维度基数预估的乘积
result_cardinality = col1_cardinality * col2_cardinality * ...
// 返回结果集数据量大小等于结果集的总行数乘以每行的字节数，每行的字节数等于返回各列字节数的加和
result_bytes = result_cardinality * (col1_bytes + col2_bytes + ...)
返回结果集基数预估的修正
直方图预估基数的方式是假定各维度之间是相互独立的，各列之间的数据是笛卡尔积组合的，因此其总的基数等于各列基数的乘积。但实际情况中各维度项之间往往是相关联的，特别是当维度间具有层次关系时基数预估的误差会被放大。
KYLIN引擎建立CUBE时通过用户预定义聚合组、联合维度和层级维度的方式裁剪维度组合的数量。那我们是不是可以将维度按其相关性进行分组，将相互关联的维度划分到一组中，假定各组维度之间是相互独立的。在结果集基数预估时首先在每组维度中选出结果基数最高的维度作为这一组维度总的基数值，然后将各组的基数相乘来估算最终结果集的基数。
// 首先计算各组中维度基数的最大值作为该组的基数
group1_cardinality = max(col1_cardinality, col2_cardinality)
group2_cardinality = max(col3_cardinality, col4_cardinality)
// 然后将各组的基数相乘得到最终的基数估计值
result_cardinality = group1_cardinality * group2_cardinality
确定成本阈值
在得到扫描数据量和返回结果集大小的预估值后，就需要确定判断“异常”查询的阈值大小。“异常”查询是影响OLAP引擎的稳定性，因此需要根据实际集群的资源性能情况和对服务稳定性的要求来确定具体的阈值。可以通过实验模拟实际查询的方式来确定合适的阈值。
基于SparkSQL的实现方案
由于我们每天的数据都是通过Spark计算得到，因此可以通过在生成数据后新增一个Spark任务来统计每日生成数据的统计信息。
统计每个时间片中数据总行数
AnalyzeTableCommand通过触发生成一个job任务来统计表中数据的总行数和总字节大小等信息。
val tableName = "table_name"
val sqlText = "ANALYZE TABLE $tableName COMPUTE STATISTICS"
spark.sql(sqlText)
val tableId = TableIdentifier(tableName)
println(spark.sessionState.catalog.getTableMetadata(tableId).stats.get.simpleString)
// 总行数为7922238，数据总字节大小为142276791 bytes
142276791 bytes, 7922238 rows
在每天的例行任务完成后增加一个Spark任务将每个时间片的数据临时存入到一个临时表中，然后通过表分析命令统计总行数信息。
统计每列数据的直方图信息
AnalyzeColumnCommand命令可以统计表中列的统计信息（默认直方图信息是不统计的，需要设置参数spark.sql.statistics.histogram.enabled=true来打开直方图信息的统计）。
// AnalyzeColumnCommand represents ANALYZE TABLE...FOR COLUMNS SQL command
val tableName = "table_name"
val allCols = df.columns.mkString(",")
val analyzeTableSQL = s"ANALYZE TABLE $tableName COMPUTE STATISTICS FOR COLUMNS $allCols"
spark.sql(s"DESC EXTENDED $tableName adgroup_id").show(truncate = false)
spark.sql(s"DESC EXTENDED $tableName scene").show(truncate = false)
+--------------+-----------------------------------------------------------------------------+
|info_name |info_value |
+--------------+-----------------------------------------------------------------------------+
|col_name |adgroup_id |
|data_type |bigint |
|comment |广告id |
|min |-1 |
|max |324051755 |
|num_nulls |0 |
|distinct_count|7020464 |
|avg_col_len |8 |
|max_col_len |8 |
|histogram |height: 4.71102879E7, num_of_bins: 10 |
|bin_0 |lower_bound: -1.0, upper_bound: 0.0, distinct_count: 2 |
|bin_1 |lower_bound: 0.0, upper_bound: 2.79059772E8, distinct_count: 924598 |
|bin_2 |lower_bound: 2.79059772E8, upper_bound: 2.86615295E8, distinct_count: 785414 |
|bin_3 |lower_bound: 2.86615295E8, upper_bound: 2.91429173E8, distinct_count: 649131 |
|bin_4 |lower_bound: 2.91429173E8, upper_bound: 2.95652736E8, distinct_count: 574800 |
|bin_5 |lower_bound: 2.95652736E8, upper_bound: 3.00972268E8, distinct_count: 709904 |
|bin_6 |lower_bound: 3.00972268E8, upper_bound: 3.04869169E8, distinct_count: 534671 |
|bin_7 |lower_bound: 3.04869169E8, upper_bound: 3.08332988E8, distinct_count: 473591 |
|bin_8 |lower_bound: 3.08332988E8, upper_bound: 3.14375206E8, distinct_count: 1031744|
|bin_9 |lower_bound: 3.14375206E8, upper_bound: 3.24051755E8, distinct_count: 1301775|
+--------------+-----------------------------------------------------------------------------+
+--------------+--------------------------------------------------------+
|info_name |info_value |
+--------------+--------------------------------------------------------+
|col_name |scene |
|data_type |int |
|comment |场景 |
|min |0 |
|max |95 |
|num_nulls |0 |
|distinct_count|64 |
|avg_col_len |4 |
|max_col_len |4 |
|histogram |height: 4.71102879E7, num_of_bins: 10 |
|bin_0 |lower_bound: 0.0, upper_bound: 1.0, distinct_count: 2 |
|bin_1 |lower_bound: 1.0, upper_bound: 3.0, distinct_count: 2 |
|bin_2 |lower_bound: 3.0, upper_bound: 6.0, distinct_count: 2 |
|bin_3 |lower_bound: 6.0, upper_bound: 12.0, distinct_count: 5 |
|bin_4 |lower_bound: 12.0, upper_bound: 12.0, distinct_count: 1 |
|bin_5 |lower_bound: 12.0, upper_bound: 12.0, distinct_count: 1 |
|bin_6 |lower_bound: 12.0, upper_bound: 13.0, distinct_count: 1 |
|bin_7 |lower_bound: 13.0, upper_bound: 28.0, distinct_count: 5 |
|bin_8 |lower_bound: 28.0, upper_bound: 45.0, distinct_count: 16|
|bin_9 |lower_bound: 45.0, upper_bound: 95.0, distinct_count: 33|
+--------------+--------------------------------------------------------+
可以看到，列统计信息中包括：
min：最小值
max：最大值
num_nulls：null值个数
distinct_count：基数大小
avg_col_len：平均字节长度
max_col_len：最大字节长度
histogram：直方图信息，包括height - 每个区间的值个数，num_of_bins - 区间个数
lower_bound/upper_bound - 直方图中每个区间的上下限值，distinct_count - 每个区间中值的基数大小
基于列统计信息可以计算得到查询扫描数据量和返回结果集的大小，以下面的查询为例：
维度展开：adgroup_id, scene
过滤条件：adgroup_id > 2.86615295E8 and adgroup_id < 3.04869169E8 and scene = 5
扫描的数据量为：
// adgroup_id > 2.86615295E8 and adgroup_id < 3.04869169E8命中了bin_3~bin_6，刚好是四个区间
adgroup_id列命中的记录数 = 4.71102879E7 * 4 = 1.884411516E8
// scene = 5命中了bin_2，该区间只有两个不同的值
scene列命中的记录数 = 1 / 2 * 4.71102879E7 = 2.355514395E7
// adgroup_id列的平均列长度为8字节，scene列的平均字节长度为4字节
扫描的数据量 = 1.884411516E8 * 8 + 2.355514395E7 * 4 = 1.6017497886E9 bytes
返回结果集数据量为：
// adgroup_id > 2.86615295E8 and adgroup_id < 3.04869169E8命中了bin_3~bin_6
adgroup_id列的返回基数 = 649131 + 574800 + 709904 + 534671 = 2468506
// scene = 5是属于枚举值筛选
scene列的返回基数 = 1
// 总基数等于各组维度基数的乘积
返回结果集总基数 = 2468506 * 1 = 2468506
// adgroup_id列的平均列长度为8字节，scene列的平均字节长度为4字节
返回结果集数据量 = 2468506 * (8 + 4) = 29622072 bytes
SparkSQL的AnalyzeColumnCommand只支持数值列类型的统计，无法对字符型维度进行统计分析。可以参考Oracle在收集直方图统计信息时的处理方式，取文本值的头32字节（可根据情况减少到如8字节）后将其转换成数值类型进行统计分析。
后记
多OLAP引擎联合支撑
这些对于像ClickHouse、Hermes等OLAP引擎来说是“异常”查询的请求，也可能确实是用户的正常需求。对于这类大查询请求，可以结合使用如SparkSQL、presto和impala等OLAP引擎进行支撑。不同的OLAP引擎有不同的特性与支持场景，应该对用户查询进行智能分析，首先分析数据在哪里，然后根据查询的特性选择合适的引擎执行。多OLAP引擎联合支撑才能很好地满足用户的需求。
基于HyperLogLog算法预估结果集基数
对于预估结果集基数的问题，第一反应肯定是使用count(distinct)的方式直接进行统计。但这种精确去重的方式需要消耗大量的内存资源，甚至可能导致集群崩溃。如果在扫描数据量不是特别大的情况下，这种方式不可行的最大原因是需要精确去重，而基数预估本身是允许精度损失的。
结果集预估本质上就是一个UV量统计问题，那可以将其转化成普通的可加性指标吗？很容易可以想到采用HyperLogLog算法来进行实现，HyperLogLog算法将UV量转变成普通的可加性指标，这样只需要在每个服务器本地就行统计后将结果汇总即可得到总的结果。
我们目前采用ClickHouse引擎来提供底层OLAP数据服务，查询其文档资料后发现其可以支持近似数量统计函数uniqCombined，而且其进行了实现优化，查询性能非常好。
select uniqExact(product_name, site_set, scene, adgroup_id) from t_daily_omad_insight_traffic_analysis_view where partition_time > 20201029;
select uniqCombined(product_name, site_set, scene, adgroup_id) from t_daily_omad_insight_traffic_analysis_view where partition_time > 20201029;
