Optimal Grouping Algorithm for COVID-19 Detection

 In response to the outbreak, countries around the world need to test potentially infected people. Due to the relative shortage of detection reagents, how to use as few reagents as possible for detection has become an interesting problem. It is assumed here that the sampling volume is sufficient, and the detection time requirement is not considered.

At present, many countries use the group testing mechanism, that is, the groups to be tested are divided into groups, and the samples in the same group are mixed for testing. If a group is positive, the group is tested further.

A natural question: how to group to save reagents?

Consider first the two extreme cases.

A small number of infected people

Usually, infected people within a group are a minority.

Suppose there are 64 people in the group, and there is only 1 infected person, using the 2, 4, 8, 64 equal division method.

• 2-point method requires 6 rounds of testing, a total of 2*6=12 times;
• 4-point method requires 3 rounds to be tested, a total of 4*3=12 times;
• 8-point method requires 2 rounds to be tested, a total of 8*2=16 times;
• 64-point method requires 1 round of tests, 64 times in total.

In fact, when there are a large number of people, such as N people, the x-division method is used, and the total number of tests is about y=x*log(x, N). It is easy to know that the function takes a minimum value when x=e.

In this case, an x ​​value near e should be taken, such as 2 or 3, to save reagents. At the same time, the number of people N is best chosen to be a value that divides x.

A large number of infected people

In the second scenario, all 64 people are infected, and the 2, 4, 8, and 64 division method is also used.

• 2-points method requires 6 rounds to be tested, a total of 2+4+8+16+32+64 = 126 times;
• 4-point method requires 3 rounds of testing, a total of 4+16+32+64=116 times;
• 8-point method requires 2 rounds of testing, a total of 8+64=72 times.
• 64-point method requires 1 round of tests, 64 times in total.

It is easy to find that when the 64-point method is used at this time, the total number of detections is the least.

N people, using the x-point method, the total number of tests is about S=x*\frac{1-x^log(x,N)}{1-x}, which is obviously a decreasing function.

In this case, a larger number of groups should be taken.

Promotion as a general case

If N people are known and the infection rate is p, how much should x be selected at this time?

This problem is a bit more complicated than the above two cases, we adopt the idea of ​​backward push.

First draw the detection route, which is a typical tree structure, as shown in the following figure.

Among them, there are p*N people who are infected (in the worst case they do not have a common parent node), then in the last round, it needs to be checked p*N*x times. Pushing back to the next level, it still needs to detect pNx times. Until the last sample to be detected has a common parent node, starting from this layer, each layer needs to be detected x times.

That is, p*N*x + p*N*x + … x + x + ….

In the worst case, infected samples are separated as far as possible from each other until the second layer, where all samples to be detected have a common parent node. At this time, the total number of detections is S=p*N*x*(log(x, N)-1)+x. At this time, the optimal x value is around 3.

Usually, this formula is accurate when the infection rate p is not high; when p is high, the total number of detections predicted by the formula is higher than the actual value because multiple infected people at the bottom have a common parent node. Therefore, the consensus obtained is the upper limit of the required number of reagents.

Applied to real life

Assuming that the resident population of a city is N=20000000 (20 million), and the infection rate is p=0.0001 (one ten thousandth), then insert the formula to get

S=2000*x*(log(x,20000000)-1)+x, it is easy to find that when x=2.91 (which can be rounded to 3), the minimum value of S is 85782, and the number of detection rounds is 16 rounds.

Therefore, if the optimal detection algorithm is adopted, the number of reagents used in the city accounts for only 0.43% of the overall population to be tested, which can save a lot of reagents. The cost is the need for multiple rounds of testing.

In practice, only the first few rounds can be grouped to achieve a balance between the optimal number of reagents and the detection time. For example, the detection must be completed within a given time, and the number of detection packets at each layer can be adjusted at this time.

ps, interestingly, no matter what value p takes, the final optimal x will never exceed 4.

分布式系统中的算法设计（一） -- 一致性 Hash

Hash 大家都知道，把某个要存储的内容的索引 key 通过某个规则计算一下，算出来一个值，这个值往往范围比原来小，且概率意义上不会冲突。

由于 Hash 计算复杂度往往比查找要快，被大量应用到各种大规模的系统中，特别是分布式系统。具体实践中有几个典型的问题。

问题来源

一致性 Hash 讨论地已经很多，基本故事就是分布式存储系统中，通过 Hash 来决定内容存到哪个节点上。

典型的比如 cache 系统，后面放若干节点，查找某个 key，hash 到某个节点，再进一步检索。

最简单的自然是按照节点数量取个模，理想状态下不会有啥问题。

但是如果发生如下情况，就无法正常工作了。 加节点（一般是有计划的） 减节点（可能突然故障，无法预知）

所以提出了一致性 hash，即考虑如下四个方面的算法： 平衡性(Balance)：哈希结果尽可能分布到所有的节点，这样可以使得所有的节点都得到利用； 单调性(Monotonicity)：加入新的节点后，已经分配节点的 hash 结果 被映射到原有的或者新的节点上去，而不会被映射到其他节点； 分散性(Spread)：同样内容尽量避免 hash 到不同节点； 负载(Load)：不同内容避免 hash 到同样节点。

简单的说，就是有一个算法，首先分配尽量均匀，其次，当节点个数变化的时候，尽量维持原来内容的映射，并进行局部调整。

能满足的算法有很多，这里介绍两个比较经典的。

基于环的实现

该算法最初于 1997 年在论文 Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web 中提出。算法复杂度为 O(log(n))。

主要设计思想为：构造一个环（顺序标上编号比如 0 ~ 2^32-1），将已有节点编号并分配到这个环上，分割环为不同的段。

对每个内容，hash 后是一个独一无二的数字，这个数字肯定会落入某个段上，按照固定方向往前找到的第一个节点编号即为要分配到的节点。

考虑两个相邻的节点 A 和 C，如果要在中间添加一个节点 B，那么 AB 段上内容会从 C 节点重新分配到 B 节点。反之，如果删除掉 B 节点，那么 AB 段上内容会再次分配到 C 节点上。

这种算法很好的满足性质 2-4，唯独平衡性没有解决。即当节点个数不多的时候，内容可能会集中在某些段，划分到部分节点上。要解决这个问题也很简单，把一个节点虚拟为多个虚节点，提高整体节点个数，然后再分散放到环上。这样就提高了平衡性。

基于概率转移的实现

该算法最初于 2014 年在论文 A Fast, Minimal Memory, Consistent Hash Algorithm 中由 Google 工程师 John Lamping 和 Eric Veach 提出。算法复杂度为 O(log(n))。

主要设计思想为：假设原先有 n 个节点，新加上一个节点后，每个 key 都有 1/n+1 的概率转移到新的节点上，n/n+1 的概率留在原先分配的节点。

举个例子，原先有 1 个节点，再加一个节点，那么已有内容有 1/2 的概率跳转到到第二个节点。原先有 2 个节点（每个里面有 1/2 的内容），再加一个节点，则已分配内容应该有 1/3 的概率转移到新的节点。

一个简单的实现代码为：

int ch(int key, int num_buckets) {
    random.seed(key) ;
    int b = 0; // This will track ch(key, j +1) .
    for (int j = 1; j < num_buckets; j++) {
        if (random.next() < 1.0/(j+1)) b = j ;
    }
    return b;
}

即根据 key 生成 num_buckets-1 个（0~1.0）的伪随机数，依次检查随机数序列：

• 第一个随机数 <1/2，则放第二个节点；
• 第二个随机数 <1/3，则放第三个节点；
• ...

注意伪装随机数序列由 key 唯一确定。意味着同样的内容在多次分配中，分配结果将是一致的。

另外，可以计算出如果当前分配为 b，下一个结果 j >= i 的概率（即 b+1 到 i-1 的过程都不发生跳变）

P(j>=i) = (b+1)/i

最终优化为如下代码：

int32_t JumpConsistentHash(uint64_t key, int32_t num_buckets) {
    int64_t b = -1, j = 0;
    while (j < num_buckets) {
        b = j;
        key = key * 2862933555777941757ULL + 1;
        j = (b + 1) * (double(1LL << 31) / double((key >> 33) + 1));
    }
    return b;
}

这个算法依赖于伪随机算法的输出，特点有： 分布均匀性由伪随机算法决定，而跟 key 自身均匀性无关，实践均匀性远好于基于环的算法； 不需要对 key 进行计算，复杂度低，实践计算时间也比基于环的算法好。

算法没解决的问题：当中间减掉节点的时候，序号会发生变化，变为 0...n-1。因此需要在外面维护一个映射关系，动态映射到原先的节点上。