In the field of OLAP data analysis, "count distinct" (or "deduplication") is a common requirement, and it has the "approximate count distinct" and "precise count distinct" according to the requirements for the deduplication results.
In large-scale data sets, it is still very challenging to achieve accurate deduplication and ensure quick query response. We know that the most frequently used processing method for precise deduplication is the bitmap method. For integer data, we can save these integer numbers into Bitmap directly, but except for integers, there are other data types, such as String. If we want to achieve accurate deduplication, we first need to build a dictionary for these data to do a unified mapping to integers, and then use the bitmap method for calculation.
We all know that Kylin uses pre-computation technology to accelerate big data analysis. In the incremental construction of the Cube, in order to avoid errors in the final deduplication results caused by the separate construction of dictionaries for different segments, all segments in a Cube will use the same dictionary (for one column), which is called the global dictionary.
Kylin has supported the global dictionary function since version 1.5.3, but the construction method at that time has obvious limitations:
In fact, the Hive-based distributed global dictionary construction has been added to Kylin 3.1. It has solved the above problems. However, in order to adapt to the new Spark engine, Kylin 4.0 implements another distributed method of building a global dictionary based on Spark. Today we will describe in detail how Kylin 4.0's global dictionary works.
Kylin 4.0 builds a global dictionary based on Spark for distributed encoding processing, which reduces the pressure on a single machine node, and the number of built dictionaries can break the limit of the maximum number of integers.
Kylin introduced the concept of buckets, which can be understood as dividing the data into several buckets (ie, multiple partitions) for parallel processing when processing data. When the dictionary is built for the first time, the value in each bucket will be encoded starting from 1, and after the encoding of all buckets is completed, the overall dictionary value will be allocated according to the offset value of each bucket. In the code, the two encodings are stored through two HashMaps, one of which stores the relative dictionary value in the bucket, and the other stores the absolute dictionary value among all buckets.
The following figure shows the transfer of the dictionary in the bucket in multiple tasks for bucket 1, and each build creates a new version for the bucket (v1, v2, v3, etc.). Curr (current) and Prev (Previous) are two HashMaps in a bucket, which store the relative code value of the dictionary in the current bucket and the absolute code value of all the dictionary values that have been constructed before.
The following are related configuration items and their default values.
kylin.dictionary.globalV2-min-hash-partitions=10 kylin.dictionary.globalV2-threshold-bucket-size=500000 |
The global dictionary is isolated by assigning a timestamp-based version number to a single build. The reason for adding version control is that the build task may be executed concurrently. Through version control, the global dictionary built before can be completely read for every code, which ensures that the latest version of the dictionary has the most complete global dictionary code, and the global dictionary will be read the latest version of the dictionary. The dictionary is finally stored by version on the file storage system (HDFS here) as shown in the figure below.
