The INFO service manages a potentially very large set of resources, each of which can be accessed by users throughout the Internet by means of a key (a string name). Discuss an approach to the design of the names of the resources that achieves the minimum loss of performance as the number of resources in the service increases. Suggest how the INFO service can be implemented so as to avoid performance bottlenecks when the number of users becomes very large.

Question

What will be an ideal response?

Answer 1

Algorithms that use hierarchic structures scale better than those that use linear structures. Therefore the
solution should suggest a hierarchic naming scheme. e.g. that each resource has an name of the form ’A.B.C’
etc. where the time taken is O(log n) where there are n resources in the system.
To allow for large numbers of users, the resources are partitioned amongst several servers, e.g. names
starting with A at server 1, with B at server 2 and so forth. There could be more than one level of partitioning
as in DNS. To avoid performance bottlenecks the algorithm for looking up a name must be decentralised. That
is, the same server must not be involved in looking up every name. (A centralised solution would use a single
root server that holds a location database that maps parts of the information onto particular servers). Some
replication is required to avoid such centralisation. For example: i) the location database might be replicatedat multiple root servers or ii) the location database might be replicated in every server. In both cases, different
clients must access different servers (e.g. local ones or randomly).