Google Interview Question
Software Engineer / Developerswe can design it using the token-ring topology. Distribute the (key,value) set among the processors connected in token-ring fashion. For query processing just pass the token in ring if local processor does not have enough data to serve. After getting and serving the data , the processor may maintain a cache for further queries related to this field.For replication purpose: we need some naming scheme which i think if number of systems in ring are less and connected over LAN then there physical id may be sufficiently added to duplicate data. For updation problems we can use "log write ahead" technique.
We can have a number of systems serving a range of key-val pairs.
Periodically, each system will broadcast its range of keys served to other systems.
A client can connect to any system to get the value for a key.
If that particular server doesn't have the answer, it can redirect the client to the
appropriate system.
We can have a master and a number of slave storage server with the replication factor of 3 synchronised by the master. When master gets the query, it evaluates a hash and returns the user the location handle of the slave storage server that actually has the data. The client can now go directly to the server holding the value of his requested key and get it. This works just like the google file system and scales to a huge number of queries per second. The main benefit is that the data never flows through the master, so the latency is very low.
We can have a master and a number of slave storage server with the replication factor of 3 synchronised by the master. When master gets the query, it evaluates a hash and returns the user the location handle of the slave storage server that actually has the data. The client can now go directly to the server holding the value of his requested key and get it. This works just like the google file system and scales to a huge number of queries per second. The main benefit is that the data never flows through the master, so the latency is very low.
- Ankur December 15, 2013