CS
Problems Base course RU

Problem

Memory for the filters

optimization membership probabilistic databases in production

An LSM tree has k runs on disk, the i-th with ni keys. M bits of memory are set aside for their Bloom filters. A filter of b bits for n keys, with the best number of hash functions, is wrong (says “possibly present” about a missing key) with probability

$$p(b, n) = e^{-\frac{b}{n} (\ln 2)^2}.$$

If a run gets not a single bit, there is no filter, and p = 1: the run is always read. A search for a key that is nowhere reads Σ pi runs on average. Allocate the memory, any non-negative real bi with a sum of at most M, so that this number is smallest, and print it. The tests include trees from the article through which this site’s git history went.

Input

The first line holds the number of cases q (1 ≤ q ≤ 104). Each case is two lines: k and M (1 ≤ k ≤ 60, 0 ≤ M ≤ 1012), then k numbers ni (1 ≤ ni ≤ 109). The sum of all k is at most 105.

Output

For each case, the smallest average number of runs read, with a relative or absolute error of at most 10−6.

In the first example the tree has three levels of 1000, 10,000 and 100,000 keys and 10 bits per key. Shared equally, 10 bits per key for each, it comes to 0.0246 runs read per search, while the best allocation gives 0.0117. In the third case the runs are identical, and equal shares are best.

Examples

Example 1

Input
3
3 1110000
1000 10000 100000
3 555000
1000 10000 100000
4 40000
1000 1000 1000 1000
Output
0.01166407113
0.128866675
0.03277019787

Example 2

Input
3
3 0
7 70 700
3 10
7 70 700
3 3000
7 70 700
Output
3
2.503404404
0.2227416257

Limits

Time · Python
4000 ms
Time · Go
1000 ms
Memory
256 MB
Judging
5 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Give one bit from a large run to a small one. How much will the error of the large filter grow, and how much will that of the small one fall? The derivative of p with respect to b is −(ln 2)²·p/n.

2Hint 2

At the optimum moving a bit changes nothing: all runs with a filter have the same derivative. What does this say about the ratio pi / ni?

3The idea

Write c = (ln 2)². The function e−cb/n is convex in b, so the minimum of the sum with Σ bi = M is where all runs with a filter have the same rate of decrease: c·pi/ni = const. So pi = λ·ni: a filter’s error is proportional to the size of the run. Small runs get almost error-free filters, large ones worse ones, since a bit per key for a large run costs hundreds of times more. A probability cannot exceed 1, so runs with λ·ni ≥ 1 get no filter at all. This is the result of Niv Dayan, Manos Athanassoulis and Stratos Idreos (the Monkey system, 2017); the article has a paragraph on it.

4Walkthrough

Let the runs of a set S have filters. From pi = λni the bits are bi = (ni/c)·ln(1/(λni)), and the condition Σ bi = M gives

$$\ln \lambda = -\frac{c M + \sum_{S} n_i \ln n_i}{\sum_{S} n_i}.$$

The runs left without a filter are the largest: if some run falls past the line, so do all larger ones. So start with all runs, compute λ and, while the largest has λ·n ≥ 1, remove it from S and recompute. The answer is (k − |S|) + λ·ΣS ni. Use the logarithm of λ so as not to lose precision when λ is around 10−12.

How much this gains can be seen on the site’s tree: at the end of the history the tiered tree with a growth of 10 has eleven runs of 89 to 3432 keys. With 10 bits per key shared equally, it comes to 0.090 extra reads per search, and with the best allocation to 0.051, 1.8 times fewer, without a single extra bit. The more levels and the more the runs differ, the bigger the gain: at one moment of the history, 3.5 times.

4+Solution
5Complexity

O(k log k) per case: a sort, then each run is removed from S at most once, and the sums are updated by subtraction.

6Common mistakes
  • Equal bits per key. M/N bits per key for each run is what is done by default, and in the first example it is twice as bad as the best.
  • Negative bits. The formula with λ without dropping the large runs gives them a negative number of bits, and so a probability above one.
  • Without logarithms. λ can be around 10−12 and smaller, and n up to 109; compute ln λ, not λ itself.

Algorithms behind it

SYS Data structure LSM tree Writes gather in memory and land on disk as sorted runs; background merges keep the number of runs small. a write is O(1) amortised in memory plus O(L·T/B) for rewriting during merges; a read is one run per level 2 problems DS Data structure Bloom filter Says “surely not” or “maybe yes” about set membership, at about 10 bits per item. O(k) 2 problems
The algorithms catalogue