Google Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
We should have, let say, 3 Counter Server (to duplicate or even triplicate their functionality in case of one or even two Counter Servers fail).
Each of Work Server (there can be thousands of them) sends the information about the requests quantity every (for example) 15 minutes to all 3 Counter Servers.
The Counter Servers summarize the quantity of requests coming from the Work Servers, and when the sum reaches the threshold, sends the action request (to give a special "doodle" to the special client)
back to the Work Server that gave the last requests quantity information.
If there is no information coming in 15 minutes from one of the Work Servers, The Counter Server decides that there is something wrong with the particular Work Server (server failure).
To prevent Counter Server failure, as I said, we need to duplicate or even triplicate their work.
Let's say we have 1000 query servers and we 1 000 000 000 query. Assume that we have one server (tracker server, Server A) to keep track of query count, this server sends 1000000000/1000=1 000 000 coin every other query servers to consume at each query hit.
- serkan.turgut0 November 27, 2015When query servers consume all available coins sends a flag Server A (tracking server) and Server A increase the query counter by 1 000 000. After a query server consumes all local coins, it my request new coins to consume. This design does not give you exact billionth query but optimized for large amount of servers with low network usage and low overhead of tracking server (which is a bottleneck for query servers).
By arranging amount of coin for each server (maybe decreasing to increase precision) we have a good approximation to billionth query without not counting all hits.