キャッシュのシステムについて

「シンプルなサーチエンジン用のウェブサーバーをイメージしてください。このシステムはprocessSearch(String query)の形で検索クエリを受け付け、結果を返すのに100台のマシンを使用します。どのマシンが要求を受け付けるかはランダムに選ばれるので、同じリクエストに対して常に同じマシンが応答するとは限りません。また、processSearchは高負荷なメソッドです。この時、最近のクエリに対するキャッシュのシステムを設計してください。特に、変更されるデータに対するキャッシュの更新の仕方については必ず説明してください。」

以下のような仮定を置きます。
・必要に応じてprocessSearchを呼び出す以外のすべてのクエリ処理は、最初に呼び出されたマシンで発生する。

・キャッシュしたいクエリの数は大きい。

・ましん間の呼び出しは比較的速い。

・クエリによる処理は50文字のタイトルと200文字の概要を合わせたURLのリストとして整理される。

・最も人気のあるクエリは、常にキャッシュにふくまれているほど非常に人気がある。

単一マシンのキャッシュを以下のように設計しました。(このコード自体は質問とあまり関係ないのですが、一応載せておきます）

Java
1import java.util.HashMap;
2
3public class Cache {
4	public static int MAX_SIZE = 10;
5	public Node head;
6	public Node tail;
7	public HashMap<String, Node> map;
8	public int size = 0;
9	
10	public Cache() {
11		map = new HashMap<String, Node>();
12	}
13	
14	public void moveToFront(Node node) {
15		if (node == head) {
16			return;
17		}
18		removeFromLinkedList(node);
19		node.next = head;
20		if (head != null) {
21			head.prev = node;
22		}
23		head = node;
24		size++;
25		
26		if (tail == null) {
27			tail = node;
28		}
29	}
30	
31	public void moveToFront(String query) {
32		Node node = map.get(query);
33		moveToFront(node);
34	}	
35	
36	public void removeFromLinkedList(Node node) {
37		if (node == null) {
38			return;
39		}
40		
41		if (node.next != null || node.prev != null) {
42			size--;
43		}
44		
45		Node prev = node.prev;
46		if (prev != null) {
47			prev.next = node.next;
48		} 
49		
50		Node next = node.next;
51		if (next != null) {
52			next.prev = prev;
53		}
54		
55		if (node == head) {
56			head = next;
57		}
58		
59		if (node == tail) {
60			tail = prev;
61		}
62		
63		node.next = null;
64		node.prev = null;
65	}
66	
67	public String[] getResults(String query) {
68		if (map.containsKey(query)) {
69			Node node = map.get(query);
70			moveToFront(node);
71			return node.results;
72		}
73		return null;
74	}
75	
76	public void insertResults(String query, String[] results) {
77		if (map.containsKey(query)) {
78			Node node = map.get(query);
79			node.results = results;
80			moveToFront(node);
81			return;
82		}
83		
84		Node node = new Node(query, results);
85		moveToFront(node);
86		map.put(query, node);
87		
88		if (size > MAX_SIZE) {
89			map.remove(tail.query);
90			removeFromLinkedList(tail);
91		}
92	}
93}