「シンプルなサーチエンジン用のウェブサーバーをイメージしてください。このシステムは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}
「コンテンツが変わった場合の結果更新について、十分なキャッシュサイズがある場合、頻繁に要求されるため恒久的にキャッシュに残ってしますクエリもあるということを思い出してください。定期的、あるいは要求に応じてキャッシュの内容をリフレッシュする仕組みが必要です。
この問いに答えるためには、結果が変化するのがいつかを考える必要があります。キャッシュの更新を行うのは主に次の場合です。
- そのURLのコンテンツが変わった場合(あるいは、そのURLのページが削除された場合)
- ページランクの変化に応じて結果の順序が変わった場合
- 特定の」クエリに関する新しいページが現れた場合
1と2を扱うには、例えばどのクエリが特定のURLと関連しているかわかるハッシュテーブルを別に作ります。これは完全に他のキャッシュから分離し、別のましんに置くことができます。しかし、この方法では多くのデータが必要になります。
あるいはキャッシュのリフレッシュを即座に行う必要がないなら、各マシンのキャッシュを定期的に調べ、変更されたURLに関連するキャッシュを削除する方法でも良いでしょう。」
この文章では「どのクエリが特定のURLと関連しているかがわかるハッシュテーブル」を別に作ることで1や2の問題に対応できると書いていますが、そのようなハッシュテーブルを作ると1や2のような問題は解決することができるのでしょうか?
このハッシュテーブルをどのように使えば良いのでしょうか?
あなたの回答
tips
プレビュー