is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.
CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.
Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.
Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.
Let's say that there are N search servers, and let's assume that during any given day that N is constant. No servers fail, and no servers are added.
- merrells October 07, 2012Let's assume that all servers are identical in performance, and that requests are load balancing evenly across the servers.
At midnight we send a message to each of the servers. The message includes the server's allocated server number S, which is in the range 0 to N-1. Each server begins counting search requests from S*(1b/N) to (S+1)*(1b/N).
If a server's counter reaches 1b, then we have a winner. The search results returned from that search server would include some flag that indicates this, which would be used by the front end page rendering servers to mark up the page with the special winner banner.
Although highly performant this solution is not very resilient to failures.But working through this approach is useful as it forms the basis of a better solution.
Let's introduce a new server, of which there is only one, called the counter server. The counter server has a request/response interface that the search servers can use to request a range of numbers. The range allocated could be between 1 and 1b/N... but we'd pick a number greater than 1 to reduce the contention for the counter server, and less than 1b/N so that we were more resilient to failures. Perhaps we'd measure the QPS of the search server and then multiply that by 10s, 30s, or 60s... Let's call the range extent R.
Now if a search server fails or a search server is added the change to N has little effect. We'll have to accept that this weakening of consistency has introduced some fuzziness. If a server fails having processed R/2 requests... the counter server sill thinks that R were counted. So the billionth query is now really the 1b-R/2 query.... which may, or may not, be acceptable...
But, having a single counter server introduces a single point of failure, so we would actually want M counter servers, and we would want them to co-ordinate with each other to ensure that any failure of an individual server has no effect. Co-ordination is expensive in terms of latency as to reach agreement a server has to talk with M-1 servers, twice. But by tuning R to take account of M, then we can build a system that is performant, reliable... and quite accurate.