{"id":1105,"date":"2012-11-22T16:43:41","date_gmt":"2012-11-22T16:43:41","guid":{"rendered":"http:\/\/brain.payzip.co.kr\/?p=1105"},"modified":"2012-11-22T16:43:41","modified_gmt":"2012-11-22T16:43:41","slug":"1105","status":"publish","type":"post","link":"https:\/\/blog.goorigo.com\/?p=1105","title":{"rendered":"\ubd84\uc0b0 \uce90\uc2dc \uc774\ub860 – Consistent Hashing"},"content":{"rendered":"

\ucd9c\ucc98 :\u00a0http:\/\/www.mimul.com\/pebble\/default\/2012\/05\/04\/1336102052449.html<\/a><\/p>\n

NoSQL \uad00\ub828 \uae30\uc220 \uc911\uc5d0 \ud558\ub098\uc778 Consistent Hashing\uc758 \uac1c\ub150\uc740 1997\ub144\uc5d0 MIT\uc758 karger\uac00 \uc6f9\uc11c\ubc84\uc758 \uc22b\uc790\uac00 \uc218\uc2dc\ub85c \ubcc0\uacbd\ub418\ub294 \uc911\uc5d0 \ubd84\uc0b0 \uc694\uccad\uc744 \ucc98\ub9ac\ud558\uae30 \uc704\ud574 \ucc98\uc74c \uace0\uc548\ud588\ub2e4\uace0 \ud558\ub294\ub370 \uadf8 \ub0b4\uc6a9\uc744 \uc0b4\ud3b4\ubcf4\uace0\uc790 \ud55c\ub2e4.
\n\uc544\ub798\uc758 \ub0b4\uc6a9\uc740\u00a0‘Consistent Hashing’<\/a>\u00a0\uc774\ub77c\ub294 \uc544\ud2f0\ud074\uc744 \ub9ce\uc774 \ucc38\uc870\ud574\uc11c \uc791\uc131\ud588\ub2e4.<\/p>\n

\uc65c \ud544\uc694\ud55c\uac00?<\/strong><\/h3>\n

N\uac1c\uc758 \uce90\uc2dc \uc2dc\uc2a4\ud15c(\ub178\ub4dc)\uc774 \uc788\ub2e4\uace0 \ud558\uace0 \uc774\ub54c \ubd80\ud558 \ubd84\uc0b0\uc5d0 \uc0ac\uc6a9\ud558\ub294 \uc77c\ubc18\uc801\uc778 \ubc29\ubc95\uc740 Object o\ub97c hash(o) mod n \ubc88\uc9f8 \uce90\uc2dc \uc2dc\uc2a4\ud15c\uc5d0 \uc800\uc7a5\ud558\ub294 \ubc29\uc2dd\uc774\ub2e4. \uc774\ub7f0 \ubc29\uc2dd\uc740 \uce90\uc2dc \uc2dc\uc2a4\ud15c\uc774 \ucd94\uac00\ub418\uac70\ub098 \uc81c\uac70\ub418\uae30 \uc804\uae4c\uc9c0\ub294 \uc798 \uc6b4\uc601\ub41c\ub2e4.
\n\uadf8\ub7ec\ub098 \uce90\uc2dc \uc2dc\uc2a4\ud15c\uc774 \ucd94\uac00\ub418\uac70\ub098 \uc7a5\uc560\ub85c \uc81c\uac70 \ub418\uc5c8\uc744 \uacbd\uc6b0, n\uc774 \ube60\ub00c\uac8c \ub418\uba74 \ubaa8\ub4e0 Object\ub294 \uc0c8\ub85c\uc6b4 \uc704\uce58\uc5d0 \ubaa8\ub450 \uc7ac\ud560\ub2f9\uc744 \ud574\uc57c\ud558\ub294\ub370 \uadf8\ub7ec\uae30\uc5d4 \ubd80\ud558 \ubd80\ub2f4\uc774 \ud06c\ub2e4.
\n\uc774 \ub54c Consistent Hashing \ubc29\ubc95\uc744 \uc0ac\uc6a9\ud558\uac8c \ub418\uba74 \uce90\uc2dc \uc2dc\uc2a4\ud15c\uc774 \ucd94\uac00\ub418\uac70\ub098 \uc791\ub3d9\uc774 \uc911\ub2e8\ub418\uc5b4\ub3c4 \ubaa8\ub4e0 Object\ub97c \ud560\ub2f9\uc744 \ud558\ub294 \uac83\uc774 \uc544\ub2c8\ub77c \ucd94\uac00\ub418\uba74 \uc778\uc811\ud55c \ub2e4\ub978 \uce90\uc2dc \uc2dc\uc2a4\ud15c\uc5d0\uc11c \uc801\uc815\ud55c \uc591\uc758 Object \ub97c \ubc1b\uac8c\ub418\uace0 \ub9c8\ucc2c\uac00\uc9c0\ub85c \uc81c\uac70\ub41c\ub2e4\uba74 \ub0a8\uc740 \uce90\uc2dc \uc2dc\uc2a4\ud15c\ub4e4\uc774 \ub098\ub204\ub294 \ud615\ud0dc\uac00 \ub418\uc5b4 \uc77c\uad00\ub418\uac8c \uc77c\ubd80 Object\uc5d0 \ub300\ud574\uc11c \uc7ac \ud560\ub2f9\uc744 \uc218\ud589\ud558\uac8c \ub41c\ub2e4. \uadf8\ub7ec\ubbc0\ub85c \uae30\uc874\uc5d0 \uc800\uc7a5\ub41c \ub300\ubd80\ubd84\uc758 \uce90\uc2dc\ub97c \uc0ac\uc6a9\ud560 \uc218 \uc788\uc73c\uba70 \uc2dc\uc2a4\ud15c \ubcc0\ub3d9\uc774 \ud788\ud2b8\uc728\uc5d0 \uc601\ud5a5\uc744 \ubbf8\uce58\uc9c0 \uc54a\uac8c \ub41c\ub2e4.
\n\uae30\ubcf8 \uc6d0\ub9ac\ub294 Consistent hashing \uc54c\uace0\ub9ac\uc998\uc740 Object\uc640 \uce90\uc2dc \uc2dc\uc2a4\ud15c \ub458\ub2e4 \ub3d9\uc77c\ud55c Hash \ud568\uc218\ub97c \uc0ac\uc6a9\ud574\uc11c \ud574\uc2f1\ud558\ub294 \uac83\uc774\ub2e4. \uce90\uc2dc \uc2dc\uc2a4\ud15c\uc740 \uad6c\uac04\uc744 \uc815\ud558\uace0 \uadf8 \uad6c\uac04\uc5d0\ub294 \ub9ce\uc740 Object\uc758 \ud574\uc2dc\uac12\uc744 \uac00\uc9c0\uace0 \uc788\ub294\ub2e4. \uce90\uc2dc \uc2dc\uc2a4\ud15c\uc774 \uc81c\uac70\ub3c4\uba74 \uc778\uc811\ud55c \uad6c\uac04\uc758 \uce90\uc2dc \uc2dc\uc2a4\ud15c\uc774 \uc81c\uac70\ub41c \uad6c\uac04\uc744 \ub9de\uac8c\ub418\uace0 \ub2e4\ub978 \uce90\uc2dc \uc2dc\uc2a4\ud15c\uc740 \uc601\ud5a5\uc744 \ubc1b\uc9c0 \uc54a\ub294\ub2e4.
\nPerformance\ub294 O(log n).<\/p>\n

\uc791\ub3d9 \ubc29\uc2dd\uc740?<\/strong><\/h3>\n

Hash \ud568\uc218\ub294 Object\uc640 \uce90\uc2dc \uc2dc\uc2a4\ud15c\uc774 \uc77c\uc815 \uad6c\uac04\uc744 \uc815\ud558\uac8c \ud55c\ub2e4. Java \uc5b8\uc5b4\uc758 \uc608\ub97c \ubcf4\uba74 Object\uc758 hashCode() \ud568\uc218\ub294 \ub9ac\ud134\uc744 int\ub85c \ud558\uace0 \ub9ac\ud134\uac12 int\uc758 \uad6c\uac04\uc740 -2^31\uc5d0\uc11c 2^31-1\uc744 \uac00\uc9c4\ub2e4.
\n\ub2e4\uc74c \uadf8\ub9bc\uc740 \ub124 \uac1c\uc758 Object(1,2,3,4)\uc640 3\uac1c\uc758 \uce90\uc2dc \uc2dc\uc2a4\ud15c(A, B, C)\uac00 \ub9c1\uc5d0 \ubc30\uce58\ub418\uc5b4 \uc788\ub2e4.<\/p>\n

\"\"
\n\uc704\uc758 \uadf8\ub9bc\uc5d0\uc11c 1,4\ub294 \uce90\uc2dc \uc2dc\uc2a4\ud15c A\uc5d0 \ub4e4\uc5b4\uac00\uace0 2\ub294 B, 3\uc740 C\uc5d0 \ub4e4\uc5b4 \uac04\ub2e4. \uc774\ub54c C\uac00 \uc81c\uac70\ub418\uc5c8\ub2e4\uace0 \uac00\uc815\ud558\uba74 Object 3\uc740 A\uc5d0 \ub4e4\uc5b4\uac04\ub2e4. \uae30\ud0c0 \uc9c0\uc6d0\uc740 \ubcc0\ud558\uc9c0 \uc54a\ub294\ub2e4. \ub2e4\uc74c \uadf8\ub9bc\ucc98\ub7fc \uce90\uc2dc D\uac00 \ucd94\uac00\ub418\uba74, 3, 4\ub294 D\ub85c \uc62e\uae34\ub2e4. \uadf8\ub9ac\uace0 1 \ub9cc A\uc5d0 \ub0a8\uc544\uc788\ub2e4.<\/p>\n

\"\"
\n\uc774\ub807\uac8c \ud568\uc73c\ub85c\uc368 \uac01 \uce90\uc2dc \uc2dc\uc2a4\ud15c\uc5d0 \ud560\ub2f9\ub41c \uad6c\uac04\uc758 \uc0ac\uc774\uc988\uc5d0 \uc608\uc678\uac00 \ubc1c\uc0dd\ud574\ub3c4 \uc798 \ub3d9\uc791\ud558\uac8c \ub41c\ub2e4. \ud55c\uac00\uc9c0 \uace0\ubbfc\ud574\uc57c\ud560 \uc810\uc740 \ubb34\uc791\uc704\ub85c \ubd84\ud3ec\ub418\uae30 \ub54c\ubb38\uc5d0 \uce90\uc2dc \uc2dc\uc2a4\ud15c \uc0ac\uc774\uc758 Object\uc758 \ubd84\ud3ec\ub294 \uade0\uc77c\ud558\uc9c0 \uc54a\uc744 \uc218 \uc788\ub2e4. \uc774\ub97c \uc704\ud55c \ud574\uacb0\ucc45\uc73c\ub85c ‘\uac00\uc0c1 \ub178\ub4dc’\ub97c \uc0ac\uc6a9\ud558\ub294 \ubc29\ubc95\uc774 \uc788\ub2e4. \uac00\uc0c1 \ub178\ub4dc\ub294 \uce90\uc2dc \uc2dc\uc2a4\ud15c\uc758 \ub9c1\uc548\uc5d0\uc11c \ubcf5\uc81c\ud558\ub294\ub370 \uc774\ub294 \uce90\uc2dc \uc2dc\uc2a4\ud15c \ud558\ub098 \ucd94\uac00\ud560\ub54c\ub9c8\ub2e4 \ub9c1\uc5d0 \uc5ec\ub7ec\uac1c \ubc30\uce58\ub418\uac8c \ub418\ub294 \ubc29\uc2dd\uc774\ub2e4.
\n\uac00\uc0c1 \ub178\ub4dc\uc758 \ud6a8\uacfc\ub294 \ub2e4\uc74c \uadf8\ub798\ud504\uc640 \uac19\uc740\ub370 10,000\uac1c\uc758 Object\ub97c 10\uac1c\uc758 \uce90\uc2dc \uc2dc\uc2a4\ud15c\uc73c\ub85c \uc2dc\ubbac\ub808\uc774\uc158\ud55c \uacb0\uacfc\uc774\ub2e4. X\ucd95\uc774 \uce90\uc2dc \uc2dc\uc2a4\ud15c\uc758 \ubcf5\uc81c\uc218\uac00 \ub418\uace0 Y\ucd95\uc740 \ud45c\uc900 \ud3b8\ucc28.
\n\ubcf5\uc81c \uc218\uac00 \uc791\uc740 Object\ub4e4\uc758 \ubd84\uc0b0\ub3c4\uac00 \uc5b8\ubc1c\ub780\uc2a4\ud55c\ub370 \uc774\ub294 \uce90\uc2dc \uc2dc\uc2a4\ud15c\uc758 Object\uc218\uc758 \ud3c9\uade0\uc758 \ud45c\uc900 \ud3b8\ucc28\uac00 \ud06c\uae30 \ub54c\ubb38\uc77c \uac83\uc774\ub2e4. \uc774 \uc2e4\ud5d8\uc5d0\uc11c \ubcf5\uc81c\ub97c 100\uc774\ub098 200\uc73c\ub85c \ud588\uc744 \uacbd\uc6b0 \ud569\ub9ac\uc801\uc778 \uade0\ud615\uc744 \uc2e4\ud604\ud560 \uc218 \uc788\ub2e4\uace0 \ud560 \uc218 \uc788\uc5c8\ub2e4\uace0 \ud55c\ub2e4. (\ud45c\uc900 \ud3b8\ucc28\uac00 \ud3c9\uade0 5-10% \uc815\ub3c4\uac00 \uc801\ub2f9\ud568)<\/p>\n

\"\"
\n\uc2dc\uc2a4\ud15c\ub9c8\ub2e4 \ub2e4\uc218\uc758 Virtual Nodes(\uac00\uc0c1 \ub178\ub4dc)\ub97c \ub9cc\ub4e4\uc5b4\uc11c \ub85c\ub4dc\ubc1c\ub780\uc2f1\uc744 \uc88b\uac8c \ud55c \uc608\ub294\u00a0libketema<\/a>\uc774\ub2e4.<\/p>\n

\uad6c\ud604 \ubc29\ubc95\uc740?<\/strong><\/h3>\n

Consistent Hashing \ubc29\ubc95\uc774 \ud6a8\ub825\uc774 \ubc1c\ud718\ud558\uae30 \uc704\ud574\uc11c\ub294 \ud574\uc2f1 \ud568\uc218\uac00 \uc798 \ub3d9\uc791\ud574\uc57c\ud558\ub294\ub370 Object\uc758 hashCode\ub85c\ub294 \ubd80\uc871\ud558\uace0 MD5\ub97c \ucd94\ucc9c\ud55c\ub2e4.<\/p>\n

[java]
\npublic class ConsistentHash {<\/p>\n

private final HashFunction hashFunction;
\n private final int numberOfReplicas;
\n private final SortedMap circle =
\n new TreeMap();<\/p>\n

public ConsistentHash(HashFunction hashFunction,
\n int numberOfReplicas, Collection nodes) {<\/p>\n

this.hashFunction = hashFunction;
\n this.numberOfReplicas = numberOfReplicas;<\/p>\n

for (T node : nodes) {
\n add(node);
\n }
\n }<\/p>\n

public void add(T node) {
\n for (int i = 0; i < numberOfReplicas; i++) {
\n circle.put(hashFunction.hash(node.toString() + i),
\n node);
\n }
\n }<\/p>\n

public void remove(T node) {
\n for (int i = 0; i < numberOfReplicas; i++) {
\n circle.remove(hashFunction.hash(node.toString() + i));
\n }
\n }<\/p>\n

public T get(Object key) {
\n if (circle.isEmpty()) {
\n return null;
\n }
\n int hash = hashFunction.hash(key);
\n if (!circle.containsKey(hash)) {
\n SortedMap tailMap =
\n circle.tailMap(hash);
\n hash = tailMap.isEmpty() ?
\n circle.firstKey() : tailMap.firstKey();
\n }
\n return circle.get(hash);
\n }<\/p>\n

}
\n[\/java]<\/p>\n

\uc0ac\uc6a9 \uc0ac\ub840\ub294?<\/strong><\/h3>\n

– NoSQL<\/h3>\n