雜湊大雜燴
一致性雜湊一般用來做分散式快取
將各伺服器的雜湊值對映到一個圓環上(一般用0~2^32-1),快取定址時,將快取的鍵取雜湊值放到圓環上,然後順時針尋找第一個伺服器節點,用找到的這個節點做快取伺服器
Java 示例
有快取伺服器5臺,快取鍵30個,分別對每個快取鍵在伺服器上定址
Java程式碼
package bj; import lombok.RequiredArgsConstructor; import org.apache.commons.codec.digest.DigestUtils; import org.junit.Test; import java.nio.ByteBuffer; import java.util.TreeSet; import java.util.stream.IntStream; /** * Created by [email protected] at 2018/12/6 下午2:11 */ public class LinearHashingTest { @RequiredArgsConstructor static class Node implements Comparable<Node> { private final String name; long digest() { byte[] digest = DigestUtils.md5(name); return Integer.toUnsignedLong(ByteBuffer.wrap(digest, 0, 4).getInt()); } @Override public int compareTo(Node o) { return Long.compare(this.digest(), o.digest()); } @Override public String toString() { return String.format("Node(name=%s, digest=%d)", name, digest()); } } @Test public void testAlpha() { TreeSet<Node> set = new TreeSet<>(); for (int i : new int[]{1, 2, 3, 4, 5}) { set.add(new Node("server" + i)); } System.out.println("Server nodes:"); for (Node node : set) { System.out.println(node); } System.out.println("Routing..."); IntStream.rangeClosed(1, 20).forEach(i -> { long hash = new Node("key" + i).digest(); System.out.printf("key%d\t%d\t => %s\n", i, hash, route(set, hash)); }); IntStream.rangeClosed(1, 20).forEach(i -> { set.add(new Node("key" + i)); }); System.out.println("All nodes:"); for (Node node : set) { System.out.println(node); } } private Node route(TreeSet<Node> nodes, long code) { for (Node node : nodes) { if (node.digest() > code) { return node; } } return nodes.first(); } } `` 控制檯輸出: ```log Node(name=server3, digest=232443701) Node(name=server2, digest=424647047) Node(name=server4, digest=648772546) Node(name=server5, digest=1375127456) Node(name=server1, digest=2822999463) Routing... key13266172564 => Node(name=server3, digest=232443701) key22029528490 => Node(name=server1, digest=2822999463) key3909203333 => Node(name=server5, digest=1375127456) key43405308747 => Node(name=server3, digest=232443701) key51034591130 => Node(name=server5, digest=1375127456) key61684928417 => Node(name=server1, digest=2822999463) key74187051213 => Node(name=server3, digest=232443701) key81564577213 => Node(name=server1, digest=2822999463) key9215402731 => Node(name=server3, digest=232443701) key104045919512 => Node(name=server3, digest=232443701) key113930184853 => Node(name=server3, digest=232443701) key123610429654 => Node(name=server3, digest=232443701) key134149020260 => Node(name=server3, digest=232443701) key142302410740 => Node(name=server1, digest=2822999463) key151605175883 => Node(name=server1, digest=2822999463) key164248449615 => Node(name=server3, digest=232443701) key173126975152 => Node(name=server3, digest=232443701) key18533962436 => Node(name=server4, digest=648772546) key191425581655 => Node(name=server1, digest=2822999463) key20180948674 => Node(name=server3, digest=232443701) All nodes: Node(name=key20, digest=180948674) Node(name=key9, digest=215402731) Node(name=server3, digest=232443701) Node(name=server2, digest=424647047) Node(name=key18, digest=533962436) Node(name=server4, digest=648772546) Node(name=key3, digest=909203333) Node(name=key5, digest=1034591130) Node(name=server5, digest=1375127456) Node(name=key19, digest=1425581655) Node(name=key8, digest=1564577213) Node(name=key15, digest=1605175883) Node(name=key6, digest=1684928417) Node(name=key2, digest=2029528490) Node(name=key14, digest=2302410740) Node(name=server1, digest=2822999463) Node(name=key17, digest=3126975152) Node(name=key1, digest=3266172564) Node(name=key4, digest=3405308747) Node(name=key12, digest=3610429654) Node(name=key11, digest=3930184853) Node(name=key10, digest=4045919512) Node(name=key13, digest=4149020260) Node(name=key7, digest=4187051213) Node(name=key16, digest=4248449615)
文章首發:ofollow,noindex" target="_blank">https://baijifeilong.github.io