An avalanche of retries
A site is built as a set of services that call one another. A user presses a button: the request arrives at service 1, which calls its dependencies, they call theirs, and so on. The calls form no cycles. On every link “u calls v” retries are set up: if a call ends in an error, u repeats it r more times, at most r + 1 attempts in all.
Some services are broken: a broken service answers any request with an error at once and calls nothing further. A healthy service, for every request it receives, calls all its dependencies and answers with an error if at least one of them finally answered with an error, after all the retries. A service's answer does not depend on the attempt: what is broken stays broken, and what is healthy answers the same way. So a call to a service that is healthy all the way down succeeds at the first attempt, and a call to a service that answers with an error is made all r + 1 times.
How many requests will each service get from one press of the button? Print the total number of requests to all services and the service that got the most.
Input
The first line holds the number of services n, the number of links m and the number of broken ones k (1 ≤ n ≤ 105, 0 ≤ m ≤ 2·105, 0 ≤ k ≤ n). Then m lines “u v r”: u calls v and repeats a failed call r more times (1 ≤ u, v ≤ n, 0 ≤ r ≤ 10). Each pair u, v occurs at most once, and there are no cycles. The last line holds the numbers of the broken services (an empty line if k = 0). The user's request arrives at service 1. The total number of requests is guaranteed to be at most 1018.
Output
Three numbers: how many requests all services got in total, including the first, the number of the service that got the most (among equals, the smallest number), and how many it got.
The first sample is from Google's book on site reliability: three layers above a database, each making four attempts, and the database gets 43 = 64 requests from one user action. In the second the cache (service 5) is broken: the catalogue (3) calls it four times for each of its three attempts, 12 requests to the cache in all, while the healthy authorisation (2) and database (4) get one request per call.
Examples
Example 1
4 3 1 1 2 3 2 3 3 3 4 3 4
85 4 64
Example 2
6 6 1 1 2 2 1 3 2 3 4 1 3 5 3 2 6 0 5 6 1 5
21 5 12
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 9 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
To know how many attempts a call to v costs, you first need to know whether v will answer with an error. And that depends only on what lies below v.
2Hint 2
If a service got x requests, and its call to v is made with t attempts, then v gets x·t from it. Do you need to know along which paths those x requests came?
3The idea
Two waves in topological order. Bottom up: a service answers with an error if it is broken itself or if at least one of its dependencies answers with an error; retries do not change the answer, so a “failed” dependency stays failed. Top down: the number of requests to a service is the sum over its callers of the caller's requests times the number of attempts (r + 1 if v fails, otherwise 1). A broken service calls nobody. This is dynamic programming over an acyclic graph: there may be exponentially many paths, but each vertex's value is computed once.
4Walkthrough
Kahn's algorithm gives the order: vertices with no incoming links, removing links, new zeros. Then a pass in reverse order for the errors and in forward order for the numbers of requests. The numbers are large, but the statement keeps them below 1018, and an int64 is enough in Go.
What this means for live systems shows in the answers. In the first sample retries at every layer multiply: three layers of four attempts give 64 requests to a database that is down anyway. In the test with a chain of 10,000 services retries are on only for the bottom 34 links, three attempts each, and the last service gets 334 ≈ 1.7·1016 requests. That is why the advice is to retry at one layer, usually the topmost, and at the others to pass the error up at once; and to limit the share of retries among all requests.
4+Solution
5Complexity
O(n + m): a topological sort and two passes over the links.
6Common mistakes
- Walking all paths. A recursion “go down every link, multiplying by the attempts” gives the right numbers but visits each path separately; in a graph of 28 layers of two services there are 227 of them.
- Retries on healthy calls. Only a failed call is retried: if v answered without an error, there is one attempt.
- A broken service calls its dependencies. It answers with an error at once, and its links do not work this time.
- An error but no retry. A service fails if at least one dependency failed, even if r = 0 on that link.