A storm of retries
Model a retry storm after an outage, as in the article. Time goes in ticks. At tick 0 all n clients (numbered 0 to n − 1) have a request fail, and each retries it until it gets an answer. For the first D ticks the server is down: all requests are refused. After that the server spends at most W units of work per tick: an answer costs A units, a refusal R (0 ≤ R < A). If x requests arrived in a tick, the largest s ≤ x with s·A + (x − s)·R ≤ W are served (zero if even that is impossible).
Clients arriving in one tick line up by number: the first s get an answer and leave, the rest get a refusal in turn. A client that has just got its k-th refusal chooses a pause p ≥ 1 and knocks again at tick “current + p”. Let g = min(cap, base·2k−1). The rules:
immediately: p = 1;constant: p = base;exponential: p = g;full: p = between(1, g);equal: p = g − ⌊g/2⌋ + between(0, ⌊g/2⌋);decorrelated: p = min(cap, between(base, max(base, 3·q))), where q is this client's previous pause, and base before the first one.
between(lo, hi) is a splitmix64 generator shared by everyone, with initial state seed; it is called as refusals happen, in the order described. All operations are on unsigned 64-bit numbers:
state = state + 0x9E3779B97F4A7C15
z = state
z = (z xor (z >> 30)) * 0xBF58476D1CE4E5B9
z = (z xor (z >> 27)) * 0x94D049BB133111EB
z = z xor (z >> 31)
between = lo + (z >> 11) mod (hi − lo + 1)Model the ticks from 0 to H − 1.
Input
One line: n, W, A, R, D, H, the rule, seed, base, cap (1 ≤ n ≤ 5·104, 1 ≤ A ≤ W ≤ 106, 0 ≤ D < H ≤ 2·105, 0 ≤ seed < 263, 1 ≤ base ≤ cap ≤ 104). There are at most 106 requests in all over the H ticks.
Output
Three numbers: how many clients got an answer within H ticks; the tick in which the last of them got it, or −1 if not everyone did; how many requests arrived in total over the H ticks.
The first sample has five clients, two answers per tick and exponential pauses without jitter: all five knock at ticks 0, 1, 3, 7 and on together, and those refused come back together again. The second has full jitter and refusals costing 2 units.
Examples
Example 1
5 20 10 0 2 50 exponential 1 1 8
5 15 19
Example 2
5 20 10 2 2 50 full 7 1 8
5 8 19
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 10 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
In how many of the H ticks does anyone knock on the server at all? And how many clients are there in each?
2The idea
Keeping for every client “when it will knock” and going through all of them every tick is H·n, up to 1010. Instead, sort the clients into buckets: a dictionary “tick → list of clients”. A tick costs as much as the clients in it, and empty ticks are almost free; the total work is the number of requests, at most 106. This is the same “event queue” as in simulations: instead of a dictionary a heap of pairs (tick, client) will do too, and it hands out the clients of a tick by number by itself.
3Walkthrough
The rest is care: sort the clients of a tick by number, serve the first ones, call the generator strictly in the order of refusals, and compute pauses in integers. In Python the 64-bit arithmetic has to be cut by the mask 264 − 1 after every multiplication; in Go a uint64 overflows by itself, as it should.
The third test is the storm from the article with full jitter: all 2000 clients are served by tick 296 (29.6 s), with 18,435 requests. The fourth is exponential pauses without jitter and refusals that cost something: nobody is served in a minute, because all 2000 clients arrive in the same tick, and refusing two thousand takes more work than the server can spend in a tick.
3+Solution
4Complexity
O(H + Q log Q), where Q is the number of requests: the ticks are gone through once, and each request is sorted and put into a bucket.
5Common mistakes
- Going through all clients every tick. The same answer, but in the long tests, where not everyone gets an answer, it is billions of checks.
- The order of generator calls. The random numbers are shared by all clients, so the order matters: tick by tick, and within a tick by the numbers of those refused.
- A pause of 0. Full jitter takes the pause from 1, not from 0: a client cannot knock in the same tick.
- Overflow of 2k. After a few dozen refusals base·2k−1 goes beyond 64 bits; the power is capped before comparing with cap.