关于ABtest哈希算法正交性讨论
关于ABtest哈希算法正交性讨论
Hash正交性
正交性定义：首先任意一个hash_type都可以均匀的将流量均匀分成100份。使用hash_type1 进行哈希后得到\(x_i,i\in[0,100)\),即每份百分之1的流量，再使用hash_type2进行哈希后得到\(y_i,i\in[0,100)\)。如果某个key在被hash_type1进行hash后得到的流量与被hash_type2得到的流量是无关的，那么就说明hash_type1与hash_type2是两中hash方式是正交的。
例如一个1000000用户的流量，经过hash_type1与hash_type2进行hash，理想情况下 中具有相同每份y中的相同x流量的个数也是同样多的，即100个。如果使用数组命中计数的话，list[\(x*100 + y\)], list[\(n\)] = 100。越不均匀，也就代表这越相关。
BKDRhash算法
BKDRhash算法主要是针对字符串进行加密的方法。具体计算方法如下所示：
\[\begin{aligned} n =& Len(string)\\ hash\_num=&\sum_{i=0}^nseed^{n - i}*string[i] \end{aligned}\]ABtest采用方法
目前ABtest 的imei_level和guid_level使用的hash方式是如下伪代码如下所示：
hash(string key, string type){
string union_key = key + type;
return BKDRhash(union_key, seed = 13131) % 10000;
}
关于level1与level2这两个hash算法
当使用imei_level1 与 imei_level2 或者 guid_level1与guid_level2时，发现相关性很强：
(list 很不均匀) list[x*100 + 0-100] 只有4个有数，其余都是0。
分析：首先imei_level1 与 imei_level2在进行BKDRhash时 union_key的长度都相同即 key+multi_level_one, key+multi_level_two，而且使用的时同一个种子seed = 13131。guid_level同理。那么这样得到的BKDR：
\[sum_1 = seed^n*s[0] + seed^{n-1}*s[1] + \cdots+ seed^2*ord(o)+seed^1*ord(n)+ord(e)\\ sum_2 = seed^n*s[0] + seed^{n-1}*s[1] + \cdots+ seed^2*ord(t)+seed^1*ord(w)+ord(o)\]可以看出sum2 - sum1 是一个定值，我们记为$D$,
\[设\\ \begin{aligned} sum_1 =& A\ \ a,b\in[0,99]\ \\ sum_1\pmod {10000} =& A\pmod {10000} = a *100+b\ \\ imei\_level1(key+multi\_level\_one) =& a\\[2ex] sum_2 =& A+D \ \ \ q,p\in[0,99]\\ sum_2\pmod {10000} =& (A + D)\pmod {10000} \\ =&(A\pmod {10000} + D\pmod {10000})\pmod {10000}\\ =&(a * 100 + b + p*100 + q)\pmod {10000}\\ \end{aligned}\\ \begin{aligned} \begin{cases} imei\_level2(key+multi\_level\_two) = (a + p + 1)\ mod \ 100&,\ if\ b + q \ge 100\\ imei\_level2(key+multi\_level\_two) = (a + p)\ mod \ 100&,\ if\ b + q \lt 100 \end{cases} \end{aligned}\]因为无论\(A\)的值等于多少，\(D\)的值时固定的。那么\(p,q\)的值是固定的。所以会导致如果imei_level1命中了\(x\)号流量，那么imei_level2要么命中\((x + p )\ mod \ 100\)号，要么命中\((x + p + 1)\ mod \ 100\)号，结论肯定是imei_level1与imei_level2两种hash方式非常相关。
但是从结论上看，list[x*100 + 0-100] 命中了4份，而不是刚才推出来的2份。那是因为\(D\)有两个。ABtest access 最后取值的时候mod了10000的原因。这样子在计算时，会有两个\(D\)。当进位影响时有一个\(D\)，没有影响时是另一个\(D\)。这样产生了两个\(D\)，就命中了4份流量。我跑了433260份数据的imei_level1 和imei_level2数据。进位影响的有174900，约占40%，没有影响60%
相邻两份命中编号相差1，\((951+803)/(951+803+135+2498) \approx 40\%\)都与推算吻合。
解决办法
只要使D变的无规律即可，
- 如果union_key长度如果不相同，seed的值不相同就可以很好的解决这个问题
- 两种hash方法产生的union_key的长度不相同也可以
29 Jan 2019 by John Brown