👩🏿‍🎓 🕌 🔞 性能测试的数据混淆 ⛹🏻 🥉 👨🏽‍🎤

ClickHouse用户知道，它的主要优点是处理分析查询的速度很高。但是，我们如何做出这样的表述呢？受信任的性能测试应对此提供支持。今天我们将讨论它们。

我们于2013年开始进行此类测试，远远早于该产品以开源形式提供。像现在一样，那时我们对Yandex.Metrica数据服务的速度最感兴趣。自2009年1月以来，我们已经将数据存储在ClickHouse中。自2012年以来，部分数据已写入数据库，部分数据已从OLAPServer和Metrage转换而来，这些数据结构以前在Yandex.Metrica中使用。因此，对于测试，我们采用了10亿次综合浏览量数据的第一个可用子集。 Metric中还没有查询，我们提出了对我们自己最有趣的查询（各种过滤，聚合和排序）。

ClickHouse已与类似系统（例如Vertica和MonetDB）进行了比较测试。坦白地说，它是由以前不是ClickHouse开发人员的一名员工执行的，并且直到获得结果后，代码中的特定情况才得以优化。同样，我们获得了功能测试的数据集。

ClickHouse在2016年加入开源之后，还有更多关于测试的问题。

专有数据测试的缺点

性能测试：

它们无法从外部复制，因为它们的发布需要无法发布的封闭数据。由于相同的原因，某些功能测试对外部用户不可用。
不发展。需要显着扩展其集合，以便可以以隔离的方式验证系统各个部分的速度变化。
它们不会针对池请求进行强制运行，外部开发人员无法检查其代码以进行性能下降。

您可以解决这些问题-丢弃旧测试，并根据开放数据进行新测试。在开放数据中，您可以获取飞往美国的航班数据，在纽约乘坐出租车的数据，或使用现成的基准TPC-H，TPC-DS和Star Schema Benchmark 。不便之处在于此数据与Yandex.Metrica数据相距甚远，我想保存测试请求。

使用真实数据很重要。

您只需要根据生产中的真实数据来测试服务的性能。让我们看几个例子。

例子1

假设您使用均匀分布的伪随机数填充数据库。在这种情况下，数据压缩将不起作用。但是，数据压缩是分析型DBMS的重要属性。选择正确的压缩算法和正确的方法将其集成到系统中是一项艰巨的任务，其中没有一个正确的解决方案，因为数据压缩需要在压缩和解压缩速度以及潜在的压缩率之间进行折衷。不知道如何压缩数据的系统将丢失。但是，如果我们使用均匀分布的伪随机数进行测试，则不会考虑该因素，所有其他结果都会失真。

结论：测试数据应具有现实的压缩率。

关于我在上一篇文章中谈到的ClickHouse中数据压缩算法的优化。

例子2

让我们对SQL查询的速度感兴趣：

SELECT RegionID, uniq(UserID) AS visitors     FROM test.hits     GROUP BY RegionID     ORDER BY visitors DESC     LIMIT 10

这是对Yandex.Metrica的典型请求。对其速度重要的是什么？

如何执行GROUP BY ？
使用什么数据结构来计算聚合函数uniq。
uniq函数的每个状态需要多少个不同的RegionID，以及需要多少RAM。

但是，不同区域的数据量分布不均也很重要。（可能是根据幂定律分布的。我以对数-对数比例构建了一个图，但我不确定。）如果是这样，对我们来说重要的是，带有少量值的uniq聚合函数的状态使用的内存很少。当有许多不同的聚合密钥时，计数以字节为单位。如何获得具有所有这些属性的生成数据？当然，最好使用真实数据。

许多DBMS实现了HyperLogLog数据结构来进行COUNT（DISTINCT）的近似计算，但是它们都工作得相对较差，因为该数据结构使用固定的内存量。 ClickHouse的功能根据集合的大小使用三种不同的数据结构的组合。

结论：测试数据应代表数据中值分布的属性-基数（列中的值数）和几个不同列的互基数。

例子3

好吧，让我们测试一下ClickHouse分析型DBMS的性能，而不是测试更简单的性能，例如哈希表。对于哈希表，选择正确的哈希函数非常重要。对于std :: unordered_map，它的重要性稍差一些，因为它是基于链的哈希表，并且素数用作数组的大小。在gcc和clang的标准库实现中，普通的哈希函数用作数字类型的默认哈希函数。但是，当我们要获得最大速度时，std :: unordered_map不是最佳选择。当使用开放式地址哈希表时，正确选择哈希函数将成为决定性因素，我们不能使用琐碎的哈希函数。

在不考虑所使用的哈希函数的情况下，很容易找到针对随机数据的哈希表性能测试。找到哈希函数测试也很容易，它着重于计算速度和某些质量标准，但是与所使用的数据结构隔离。但是事实是，哈希表和HyperLogLog对哈希函数要求使用不同的质量标准。

在报告“ ClickHouse中的哈希表的排列方式”中阅读有关此内容的更多信息。由于它不考虑瑞士表，因此有点过时了。

挑战赛

我们希望按结构获取用于结构性能测试的数据，与Yandex.Metrica数据相同，该数据存储了所有对基准测试很重要的属性，但是在此数据中没有留下任何实际的访问者痕迹。也就是说，数据应匿名化，并应存储以下内容：

压缩比
基数（不同值的数量），
几个不同列的共同基数，
可以用来模拟数据的概率分布的属性（例如，如果我们认为区域是根据幂定律分布的，那么人工数据的指数-分布参数-应该与真实数据相同）。

数据具有相似的压缩率又需要什么呢？例如，如果使用LZ4，则二进制数据中的子字符串应以大致相同的距离重复，并且重复的长度应大致相同。对于ZSTD，添加了字节熵匹配。

最大的目标：使外部人员可以使用该工具，每个人都可以匿名使用其数据集进行发布。这样我们就可以调试和测试类似于生产数据的其他人的数据的性能。我希望观看生成的数据会很有趣。

这是对该问题的非正式陈述。但是，没有人打算发表正式声明。

尝试解决

对我们来说，这项任务的重要性不应被夸大。实际上，它从来没有在计划中，甚至没有人打算这样做。我只是不希望自己会遇到一些麻烦，突然之间我心情会好起来，很多事情可能会推迟到以后。

显式概率模型

第一个想法是选择一个概率分布族，为表的每一列建模。然后，根据数据的统计信息，选择模型拟合参数，并使用所选分布生成新数据。可以使用带有预定义种子的伪随机数生成器来获得可重现的结果。

对于文本字段，您可以使用马尔可夫链-一种可以理解的模型，可以对其进行有效的实现。

是的，需要一些技巧：

我们要保留时间序列的连续性-这意味着对于某些数据类型，有必要不对值本身建模，而对相邻模型之间的差异建模。
为了模拟列的条件基数（例如，每个访问者标识符通常只有很少的IP地址），您还需要以显式形式写下列之间的依赖关系（例如，生成IP地址时，将使用访问者标识符的哈希值，但是其他一些伪随机数据）。
尚不清楚如何表达一个访问者经常同时访问具有匹配域的URL的依赖性。

所有这些都以程序的形式呈现，其中所有分布和依赖项都经过硬编码-所谓的“ C ++脚本”。但是，马尔可夫模型仍然是根据统计量，使用噪声进行的平滑和粗化之和计算得出的。我开始编写此脚本，但是由于某种原因，在我明确编写了十列模型之后，它突然变得无聊得令人无法忍受。在2012年的Yandex.Metrica的点击量表中，有100多个列。

 EventTime.day(std::discrete_distribution<>({    0, 0, 13, 30, 0, 14, 42, 5, 6, 31, 17, 0, 0, 0, 0, 23, 10, ...})(random)); EventTime.hour(std::discrete_distribution<>({    13, 7, 4, 3, 2, 3, 4, 6, 10, 16, 20, 23, 24, 23, 18, 19, 19, ...})(random)); EventTime.minute(std::uniform_int_distribution<UInt8>(0, 59)(random)); EventTime.second(std::uniform_int_distribution<UInt8>(0, 59)(random)); UInt64 UserID = hash(4, powerLaw(5000, 1.1)); UserID = UserID / 10000000000ULL * 10000000000ULL    + static_cast<time_t>(EventTime) + UserID % 1000000; random_with_seed.seed(powerLaw(5000, 1.1)); auto get_random_with_seed = [&]{ return random_with_seed(); };

这种方法无法完成任务。如果我更加勤奋地与她接触，可以肯定该脚本将被编写。

优点：

思想简单。

缺点：

实施的复杂性，
实施的解决方案仅适用于一种类型的数据。

我想要一个更通用的解决方案-这样它不仅可以应用于Yandex.Metrica数据，还可以用于混淆其他任何数据。

但是，此处可以进行改进。您不能手动选择模型，但要实现模型目录并在其中选择最佳模型（最佳拟合+某种形式的正则化）。或者，您可以将Markov模型用于所有类型的字段，而不仅仅是文本。数据之间的依赖关系也可以自动理解。为此，您需要计算两列之间的相对熵（相对信息量），或更简单地说，是每对列的相对基数（例如“固定B的平均值平均有多少个不同的A值”）。例如，这将使您很清楚URLDomain完全依赖于URL，反之亦然。

但是我也拒绝了这个想法，因为有太多选择需要考虑，并且需要花费很长时间来编写。

神经网络

我已经告诉过这个任务对我们来说很重要。甚至没有人想到对其实现进行任何改动。幸运的是，同事Ivan Puzyrevsky随后在HSE担任教师，同时正在开发YT核心。他问我是否有任何有趣的任务可以作为文凭课程提供给学生。我给了他这个，他向我保证这是合适的。因此，我把这个任务交给了一个“从街上走出去”的好人-Sharif Anvardinov（NDA已签约处理数据）。

他向他介绍了他的所有想法，但最重要的是，他解释说可以以任何方式解决问题。最好的选择是使用我完全不了解的那些方法：例如，使用LSTM生成文本数据转储。多亏了这篇文章《递归神经网络的不合理的有效性》，这引起了我的注意。

该任务的第一个功能是您需要生成结构化数据，而不仅仅是文本。递归神经网络是否能够生成具有所需结构的数据还不是很明显。有两种解决方法。首先是使用单独的模型来生成结构和“填充物”：神经网络应仅生成值。但是，此选项被推迟到以后，之后他们再也没有这样做。第二种方法是简单地将TSV转储生成为文本。实践表明，在文本中，这些行的一部分与结构不对应，但是在加载时可以将这些行丢弃。

第二个特征-循环神经网络生成数据序列，并且数据中的依存关系只能遵循此序列的顺序。但是在我们的数据中，列的顺序可能相对于它们之间的依赖关系是相反的。我们对此功能未做任何事情。

到了夏天，第一个有效的Python脚本出现了，它可以生成数据。乍一看，数据质量不错：

确实，发现了困难：

该模型的大小约为1 GB。我们试图为数据创建一个模型，该数据的大小约为几千兆字节（对于初学者而言）。结果模型如此之大的事实引起了人们的关注：突然之间，就有可能从模型中获得实际数据并对其进行训练。很有可能不会。但是我不理解机器学习和神经网络，也没有从这个人那里读过Python代码，那么如何确定？然后有关于如何压缩神经网络而不损失质量的文章，但是这没有实现。一方面，这看起来不成问题-您可以拒绝发布模型，而只发布生成的数据。另一方面，在重新训练的情况下，生成的数据可能包含源数据的某些部分。
在具有CPU的单台计算机上，数据生成速率约为每秒100条线。我们有一项任务-生成至少十亿行。计算表明，在辩护文凭之前无法做到这一点。使用其他硬件是不切实际的，因为我有一个目标-使数据生成工具可以广泛使用。

Sharif试图通过比较统计数据来研究数据质量。例如，我计算了不同符号出现在源和生成的数据中的频率。结果令人震惊-最常见的字符是Ð和Ñ。

不用担心-他完美地捍卫了自己的文凭，此后我们安全地忘记了这项工作。

压缩数据变异

假设将问题陈述简化为一点：您需要生成压缩率与原始数据完全相同的数据，而数据必须以相同的速度完全扩展。怎么做？需要直接编辑压缩数据的字节！这样，压缩数据的大小将不会改变，但是数据本身会改变。是的，一切都会很快进行。当这个想法出现时，我立即想实施它，尽管它解决了其他一些问题而不是原来的问题。它总是发生。

如何直接编辑压缩文件？假设我们只对LZ4感兴趣。使用LZ4压缩的数据包含两种类型的指令：

文字：按原样复制接下来的N个字节。
匹配（匹配，最小重复长度为4）：以距离M重复文件中的N个字节。

源数据：
Hello world Hello 。

压缩数据（有条件）：
literals 12 "Hello world " match 5 12 。

在压缩文件中，保留match不变，而在字面量中，我们将更改字节值。结果，在解压缩后，我们获得了一个文件，其中所有重复的序列至少还重复了4个，并且重复了相同的距离，但同时包含一组不同的字节（比方说，从修改后的文件中的原始文件中未取一个字节））

但是如何更改字节？这并不明显，因为除了列类型之外，数据还具有我们自己想要保留的内部隐式结构。例如，文本通常以UTF-8编码存储-我们也希望在生成的数据中使用有效的UTF-8。我做了一个简单的试探法来满足几个条件：

空字节和ASCII控制字符按原样存储，
一些标点符号仍然存在
将ASCII转换为ASCII，剩下的部分将保存最高有效位（或者您可以为不同的UTF-8长度显式编写if设置）。在一个字节类别中，均匀地随机选择一个新值。
并保存https://和类似的片段，否则一切看起来都太傻了。

这种方法的独特之处在于初始数据本身充当数据的模型，这意味着该模型无法发布。它允许您生成的数据量不超过原始数据量。为了进行比较，在以前的方法中，可以创建模型并在其基础上生成无限量的数据。

网址示例：

http://ljc.she/kdoqdqwpgafe/klwlpm&qw=962788775I0E7bs7OXeAyAx
http://ljc.she/kdoqdqwdffhant.am/wcpoyodjit/cbytjgeoocvdtclac
http://ljc.she/kdoqdqwpgafe/klwlpm&qw=962788775I0E7bs7OXe
http://ljc.she/kdoqdqwdffhant.am/wcpoyodjit/cbytjgeoocvdtclac
http://ljc.she/kdoqdqwdbknvj.s/hmqhpsavon.yf#aortxqdvjja
http://ljc.she/kdoqdqw-bknvj.s/hmqhpsavon.yf#aortxqdvjja
http://ljc.she/kdoqdqwpdtu-Unu-Rjanjna-bbcohu_qxht
http://ljc.she/kdoqdqw-bknvj.s/hmqhpsavon.yf#aortxqdvjja
http://ljc.she/kdoqdqwpdtu-Unu-Rjanjna-bbcohu_qxht
http://ljc.she/kdoqdqw-bknvj.s/hmqhpsavon.yf#aortxqdvjja
http://ljc.she/kdoqdqwpdtu-Unu-Rjanjna-bbcohu-702130

结果令我满意-查看数据很有趣。但是，仍然有问题。 URL仍然是结构化的，但是在某些地方，很容易猜测yandex或avito。进行试探，有时会在某些地方重新排列一些字节。

其他考虑因素令人担忧。例如，敏感信息可以二进制形式在FixedString类型的列中表示，由于某种原因，我决定将它们保存为ASCII控制字符和标点符号。而且我不考虑数据类型。

另一个问题：如果将“ length，value”类型的数据存储在一个列中（这是String类型的列的存储方式），那么如何确保在突变后长度保持正确？当我尝试修复它时，任务立即变得无趣。

随机排列

但是问题没有解决。我们进行了几次实验，但情况越来越糟。由于心情已经变坏了，它什么也不做，只能在Internet上阅读随机的页面。幸运的是，在这些页面之一中，是对渲染游戏Wolfenstein 3D中主角死亡场景的算法的分析。

精美的动画-屏幕充满鲜血。本文解释说，这实际上是一个伪随机排列。随机排列-一组的随机选择的一对一转换。即，不重复显示不同参数的结果的整个集合。换句话说，这是一种以随机顺序迭代集合中所有元素的方法。图片中显示的就是这种过程-我们在每个像素上绘画，这些像素是从所有像素中随机选择的，没有重复。如果我们在每一步都选择一个随机像素，那么在最后一个像素上绘制将花费很长时间。

该游戏使用一种非常简单的伪随机置换算法-LFSR （线性反馈移位寄存器）。像伪随机数生成器一样，由密钥参数化的随机排列或它们的族可以具有强大的密码功能-这正是我们转换数据所需要的。虽然可能会有一些不明显的细节。例如，似乎可以将N字节加密为N字节，并使用一个预先固定的密钥和初始化矢量，将其用作许多N字节字符串的伪随机排列。实际上，这种变换是一对一的，并且看起来是随机的。但是，如果我们对所有数据使用相同的转换，则结果可能需要分析，因为多次使用相同的初始化向量和键值。这类似于电子密码书块密码模式。

获得伪随机排列的方法是什么？您可以进行简单的一对一转换，并从中组装出相当复杂的函数，这些函数看起来是随机的。让我举一个我最喜欢的一对一转换示例：

在二进制补码算术中乘以奇数（例如大质数），
异或移位： x ^= x >> N ，
CRC-N，其中N是自变量的位数。

因此，例如，通过三个乘法和两个xor移位运算，组装了murmurhash终结器。此操作是伪随机排列。但是以防万一，我注意到哈希函数（即使N位中的N位）也不必相互唯一。

或者这是来自Jeff Preshing网站的基本数论的另一个有趣示例。

我们如何在任务中使用伪随机排列？您可以使用它们转换所有数字字段。这样就有可能保留所有字段组合的所有基数和互基数。也就是说，COUNT（DISTINCT）将返回与转换之前相同的值，并且返回任何GROUP BY。

值得注意的是，保留所有基数与数据匿名化问题的声明有些许矛盾。 , , , 10 , . 10 — , . , , , — , , . . , , , Google, , - Google. — , , ( ) ( ). , , .

, . , 10, . ?

, size classes ( ). size class , . 0 1 . 2 3 1/2 1/2 . 1024..2047 1024! () . 依此类推。 .

, . , -. , .

, , , .

— , . . . Fabien Sanglard c Hackers News , . Redis — . , .

. — , . , .

:
arg: xxxxyyyy arg_l : xxxx arg_r : yyyy
. xor :
res: yyyyzzzz res_l = yyyy = arg_r res_r = zzzz = arg_l ^ F( arg_r )

, F 4 , .

: , , — , , !

. , , , . :

, , Electronic Codebook mode of operation;
( ) , , .

. , LZ4 , , .

, , , . — . , , , . ( , ). ?

-, : , 256^10 10 , , . -, , .

, . , , . , . , - .

, — , N . N — . , N = 5, «» «». Order-N.

P( | ) = 0.9
P( | ) = 0.05
P( | ) = 0.01
...

. ( vesna.yandex.ru). LSTM, N, , . — , . : , , .

Title:

— . — , . , , — .@Mail.Ru — — - . ) — AUTO.ria.ua

, , . () , — . 0 N, N N − 1).

. , 123456 URL, . . -. . , .

: URL, , -. : https://www.yandex.ru/images/cats/?id=xxxxxx . , URL, , . : http://ftp.google.kz/cgi-bin/index.phtml?item=xxxxxx . - , 8 .

https://www.yandex.ru/ images/c ats/?id=12345
^^^^^^^^

distribution: [aaaa][b][cc][dddd][e][ff][g g ggg][h]...
hash(" images/c ") % total_count: ^

http://ftp.google.kz/c g ...

, . :

 -        | . -    
-  — .:      Lore - dfghf — . -   )  473682  -  
- !   »  -  —      
- !   » , 
-  .  c      @Mail.Ru - 
-     ,  2010 |  . 
- !    : 820 0000 .,    -
-   - DoramaTv.ru -   . -  ..    
-  .  2013 ,       ->  80 .
-  -    (.    , ,  
-   . 5, 69,  W* - ., ,      World of Tanks
- ,     . 2     @Mail.Ru
-      ,  .

结果

, - , - . , . clickhouse obfuscator, : (, CSV, JSONEachRow), ( ) ( , ). .

clickhouse-client, Linux. , ClickHouse. , MySQL PostgreSQL , .

clickhouse obfuscator \
--seed "$(head -c16 /dev/urandom | base64)" \
--input-format TSV --output-format TSV \
--structure 'CounterID UInt32, URLDomain String, \
URL String, SearchPhrase String, Title String' \
< table.tsv > result.tsv

clickhouse obfuscator --help

, . , ? , , . , , . , ( --help ) .

, .

clickhouse-datasets.s3.yandex.net/hits/tsv/hits_v1.tsv.xz
clickhouse-datasets.s3.yandex.net/visits/tsv/visits_v1.tsv.xz

ClickHouse. , ClickHouse .

性能测试的数据混淆