Problems Base course RU

Replica pairs

hashing load balancing replication distributed systems in production

Each key is stored on two servers: the two on which this key’s rendezvous weight is largest. The weight is computed as follows. For a string s its FNV-1a hash is a 64-bit number: start with 0xCBF29CE484222325 and for each byte c of the string do h ← (h XOR c) · 0x100000001B3 modulo 2⁶⁴. The scrambling mix(z): z ← (z XOR (z >> 30)) · 0xBF58476D1CE4E5B9, then z ← (z XOR (z >> 27)) · 0x94D049BB133111EB, then z ← z XOR (z >> 31), all modulo 2⁶⁴. The weight of key k on server s is mix(FNV(k) XOR FNV(s)), with names taken as bytes.

Count how many pairs each server belongs to. Then one server goes offline, and each key that was stored on it gets a new pair: the two heaviest of the remaining servers. How many keys does each of the remaining servers take on? Two tests are real addresses of the Kennedy Space Center’s web server over a week in July 1995.

Input

The first line holds the number of servers n and the number of keys m (3 ≤ n ≤ 30, 1 ≤ m ≤ 30,000). Then n lines with server names, all different, then m lines with keys, then the name of the server that went offline. Names and keys are non-empty strings of visible ASCII characters without spaces, up to 100 long.

Output

The first line holds n numbers: how many pairs each server belongs to, in input order. The second holds n − 1 numbers: how many new keys each of the remaining servers gets, in the same order.

In the second example server c belonged to four pairs, and after it goes offline these four keys pass to a (one) and to b (three): for each of them the new partner is the server third by weight.

Examples

Example 1

Input

4 5
alpha
beta
gamma
delta
/
/index.html
/images/logo.gif
/news
/shuttle
beta

Output

2 2 3 3
0 0 2

Example 2

Input

3 4
a
b
c
x
y
z
xyz
c

Output

3 1 4
1 3

Limits

Time · Python: 8000 ms
Time · Go: 1500 ms
Memory: 256 MB
Judging: 6 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

When a server goes offline, the order of the other servers’ weights for a key does not change: their weights do not depend on it. Whose pair can change after that, and to whom?

2The idea

A key’s pair is the first two servers in its list in decreasing order of weight. If the server that went offline was not in this pair, the first two places stay with the same servers, and the pair does not change. If it was, its place is taken by the third by weight. So for each key it is enough to find the three heaviest servers, and there is no need to “replay” the failure: the answer to the second question is how many times each server was third for keys where the offline server was in the top two.

3Walkthrough

Compute the FNV of each server once. For a key: its FNV, then the weight on each server and the three largest; with n ≤ 30 one pass with three slots is enough. The first two servers each get a pair; if the offline server is among them, the third gets a new key.

Arithmetic is modulo 2⁶⁴: in Go that is an ordinary uint64, where multiplication overflows exactly as needed; in Python, a mask & (2**64 − 1) after each multiplication. On the NASA addresses with eight proxies the switched-off proxy-3 was in 1068 pairs, and its keys spread almost evenly over the other seven, from 141 to 162 each.

3+Solution

4Complexity

O(n · (m + the length of the keys)): the weight of each key on each server is computed once.

5Common mistakes

Scrambling separately. mix(FNV(k)) XOR mix(FNV(s)) is not the same as mix(FNV(k) XOR FNV(s)): with such a “weight” the order of servers for a key is set by one mask applied to the same server numbers, and the pairs come out different. The first example catches this.
Recomputing the pairs from scratch without the offline server and comparing. Correct, but twice as slow, and it misses the point: nothing changes except the pairs with the offline server.
The bytes of names. The hash is computed over the bytes of the string, without the line break at the end.

Algorithms behind it

SYS Algorithm Rendezvous hashing Each key goes to the server with the largest hash of the pair “key, server”: even, table-free, and a failure moves only the failed server’s keys. O(N) per key 2 problems SYS Algorithm Consistent hashing Spreads keys over servers so that adding a server moves only its share. O(log(N·v)) to find a server 1 problem