bootstracp实现树形列表_Java实现一致性哈希算法，并搭建环境测试其负载均衡特性...
實(shí)現(xiàn)負(fù)載均衡是后端領(lǐng)域一個(gè)重要的話題，一致性哈希算法是實(shí)現(xiàn)服務(wù)器負(fù)載均衡的方法之一，你很可能已在一些遠(yuǎn)程服務(wù)框架中使用過它。下面我們嘗試一下自己實(shí)現(xiàn)一致性哈希算法。
一. 簡(jiǎn)述一致性哈希算法
這里不詳細(xì)介紹一致性哈希算法的起源了，網(wǎng)上能方便地搜到許多介紹一致性哈希算法的好文章。本文主要想動(dòng)手實(shí)現(xiàn)一致性哈希算法，并搭建一個(gè)環(huán)境進(jìn)行實(shí)戰(zhàn)測(cè)試。
在開始之前先整理一下算法的思路:
一致性哈希算法通過把每臺(tái)服務(wù)器的哈希值打在哈希環(huán)上，把哈希環(huán)分成不同的段，然后對(duì)到來的請(qǐng)求計(jì)算哈希值從而得知該請(qǐng)求所歸屬的服務(wù)器。這個(gè)辦法解決了傳統(tǒng)服務(wù)器增減機(jī)器時(shí)需要重新計(jì)算哈希的麻煩。
但如果服務(wù)器的數(shù)量較少，可能導(dǎo)致計(jì)算出的哈希值相差較小，在哈希環(huán)上分布不均勻，導(dǎo)致某臺(tái)服務(wù)器過載。為了解決負(fù)載均衡問題，我們引入虛擬節(jié)點(diǎn)技術(shù)，為每臺(tái)服務(wù)器分配一定數(shù)量的節(jié)點(diǎn)，通過節(jié)點(diǎn)的哈希值在哈希環(huán)上進(jìn)行劃分。這樣一來，我們就可以根據(jù)機(jī)器的性能為其分配節(jié)點(diǎn)，性能好就多分配一點(diǎn)，差就少一點(diǎn)，從而達(dá)到負(fù)載均衡。
二. 實(shí)現(xiàn)一致性哈希算法
奠定了整體思路后我們開始考慮實(shí)現(xiàn)的細(xì)節(jié)
哈希算法的選擇
選擇能散列出32位整數(shù)的 FNV 算法, 由于該哈希函數(shù)可能產(chǎn)生負(fù)數(shù), 需要作取絕對(duì)值處理.
請(qǐng)求節(jié)點(diǎn)在哈希環(huán)上尋找對(duì)應(yīng)服務(wù)器的策略
策略為：新節(jié)點(diǎn)尋找最近比且它大的節(jié)點(diǎn), 比如說現(xiàn)在已經(jīng)有環(huán)[0, 5, 7, 10], 來了個(gè)哈希值為6的節(jié)點(diǎn), 那么它應(yīng)該由哈希值為7對(duì)應(yīng)的服務(wù)器處理. 如果請(qǐng)求節(jié)點(diǎn)所計(jì)算的哈希值大于環(huán)上的所有節(jié)點(diǎn), 那么就取第一個(gè)節(jié)點(diǎn). 比如來了個(gè)11, 將分配到0所對(duì)應(yīng)的節(jié)點(diǎn).
哈希環(huán)的組織結(jié)構(gòu)
開始的時(shí)候想過用順序存儲(chǔ)的結(jié)構(gòu)存放，但是在一致性哈希中，最頻繁的操作是在集合中查找最近且比目標(biāo)大的數(shù). 如果用順序存儲(chǔ)結(jié)構(gòu)的話，時(shí)間復(fù)雜度是收斂于O(N)的，而樹形結(jié)構(gòu)則為更優(yōu)的O(logN)。
但凡事有兩面，采用樹形結(jié)構(gòu)存儲(chǔ)的代價(jià)是數(shù)據(jù)初始化的效率較低，而且運(yùn)行期間如果有節(jié)點(diǎn)插入刪除的話效率也比較低。但是在現(xiàn)實(shí)中，服務(wù)器在一開始注冊(cè)后基本上就不怎么變了，期間增減機(jī)器，宕機(jī)，機(jī)器修復(fù)等事件的頻率相比起節(jié)點(diǎn)的查詢簡(jiǎn)直是微不足道。所以本案例決定使用使用樹形結(jié)構(gòu)存儲(chǔ)。
貼合上述要求，并且提供有序存儲(chǔ)的，首先想到的是紅黑樹，而且Java中提供了紅黑樹的實(shí)現(xiàn)TreeMap。
虛擬節(jié)點(diǎn)與真實(shí)節(jié)點(diǎn)的映射關(guān)系
如何確定一個(gè)虛擬節(jié)點(diǎn)對(duì)應(yīng)的真實(shí)節(jié)點(diǎn)也是個(gè)問題。理論上應(yīng)該維護(hù)一張表記錄真實(shí)節(jié)點(diǎn)與虛擬節(jié)點(diǎn)的映射關(guān)系。本案例為了演示，采用簡(jiǎn)單的字符串處理。
比方說服務(wù)器192.168.0.1:8888分配了 1000 個(gè)虛擬節(jié)點(diǎn), 那么它的虛擬節(jié)點(diǎn)名稱從192.168.0.1:8888@1一直到192.168.0.1:8888@1000。通過這樣的處理，我們?cè)谕ㄟ^虛擬節(jié)點(diǎn)找真實(shí)節(jié)點(diǎn)時(shí)只需要裁剪字符串即可。
計(jì)劃定制好后, 下面是具體代碼：
public class ConsistentHashTest { /** * 服務(wù)器列表,一共有3臺(tái)服務(wù)器提供服務(wù), 將根據(jù)性能分配虛擬節(jié)點(diǎn) */ public static String[] servers = { "192.168.0.1#100", //服務(wù)器1: 性能指數(shù)100, 將獲得1000個(gè)虛擬節(jié)點(diǎn) "192.168.0.2#100", //服務(wù)器2: 性能指數(shù)100, 將獲得1000個(gè)虛擬節(jié)點(diǎn) "192.168.0.3#30" //服務(wù)器3: 性能指數(shù)30, 將獲得300個(gè)虛擬節(jié)點(diǎn) }; /** * 真實(shí)服務(wù)器列表, 由于增加與刪除的頻率比遍歷高, 用鏈表存儲(chǔ)比較劃算 */ private static List realNodes = new LinkedList<>(); /** * 虛擬節(jié)點(diǎn)列表 */ private static TreeMap virtualNodes = new TreeMap<>(); static{ for(String s : servers){ //把服務(wù)器加入真實(shí)服務(wù)器列表中 realNodes.add(s); String[] strs = s.split("#"); //服務(wù)器名稱, 省略端口號(hào) String name = strs[0]; //根據(jù)服務(wù)器性能給每臺(tái)真實(shí)服務(wù)器分配虛擬節(jié)點(diǎn), 并把虛擬節(jié)點(diǎn)放到虛擬節(jié)點(diǎn)列表中. int virtualNodeNum = Integer.parseInt(strs[1]) * 10; for(int i = 1; i <= virtualNodeNum; i++){ virtualNodes.put(FVNHash(name + "@" + i), name + "@" + i); } } } public static void main(String[] args) { new Thread(new RequestProcess()).start(); } static class RequestProcess implements Runnable{ @Override public void run() { String client = null; while(true){ //模擬產(chǎn)生一個(gè)請(qǐng)求 client = getN() + "." + getN() + "." + getN() + "." + getN() + ":" + (1000 + (int)(Math.random() * 9000)); //計(jì)算請(qǐng)求的哈希值 int hash = FVNHash(client); //判斷請(qǐng)求將由哪臺(tái)服務(wù)器處理 System.out.println(client + " 的請(qǐng)求將由 " + getServer(client) + " 處理"); try { Thread.sleep(500); } catch (InterruptedException e) { e.printStackTrace(); } } } } private static String getServer(String client) { //計(jì)算客戶端請(qǐng)求的哈希值 int hash = FVNHash(client); //得到大于該哈希值的所有map集合 SortedMap subMap = virtualNodes.tailMap(hash); //找到比該值大的第一個(gè)虛擬節(jié)點(diǎn), 如果沒有比它大的虛擬節(jié)點(diǎn), 根據(jù)哈希環(huán), 則返回第一個(gè)節(jié)點(diǎn). Integer targetKey = subMap.size() == 0 ? virtualNodes.firstKey() : subMap.firstKey(); //通過該虛擬節(jié)點(diǎn)獲得真實(shí)節(jié)點(diǎn)的名稱 String virtualNodeName = virtualNodes.get(targetKey); String realNodeName = virtualNodeName.split("@")[0]; return realNodeName; } public static int getN(){ return (int)(Math.random() * 128); } public static int FVNHash(String data){ final int p = 16777619; int hash = (int)2166136261L; for(int i = 0; i < data.length(); i++) hash = (hash ^ data.charAt(i)) * p; hash += hash << 13; hash ^= hash >> 7; hash += hash << 3; hash ^= hash >> 17; hash += hash << 5; return hash < 0 ? Math.abs(hash) : hash; }}/* 運(yùn)行結(jié)果片段55.1.13.47:6240 的請(qǐng)求將由 192.168.0.1 處理5.49.56.126:1105 的請(qǐng)求將由 192.168.0.1 處理90.41.8.88:6884 的請(qǐng)求將由 192.168.0.2 處理26.107.104.81:2989 的請(qǐng)求將由 192.168.0.2 處理114.66.6.56:8233 的請(qǐng)求將由 192.168.0.1 處理123.74.52.94:5523 的請(qǐng)求將由 192.168.0.1 處理104.59.60.2:7502 的請(qǐng)求將由 192.168.0.2 處理4.94.30.79:1299 的請(qǐng)求將由 192.168.0.1 處理10.44.37.73:9332 的請(qǐng)求將由 192.168.0.2 處理115.93.93.82:6333 的請(qǐng)求將由 192.168.0.2 處理15.24.97.66:9177 的請(qǐng)求將由 192.168.0.2 處理100.39.98.10:1023 的請(qǐng)求將由 192.168.0.2 處理61.118.87.26:5108 的請(qǐng)求將由 192.168.0.2 處理17.79.104.35:3901 的請(qǐng)求將由 192.168.0.1 處理95.36.5.25:8020 的請(qǐng)求將由 192.168.0.2 處理126.74.56.71:7792 的請(qǐng)求將由 192.168.0.2 處理14.63.56.45:8275 的請(qǐng)求將由 192.168.0.1 處理58.53.44.71:2089 的請(qǐng)求將由 192.168.0.3 處理80.64.57.43:6144 的請(qǐng)求將由 192.168.0.2 處理46.65.4.18:7649 的請(qǐng)求將由 192.168.0.2 處理57.35.27.62:9607 的請(qǐng)求將由 192.168.0.2 處理81.114.72.3:3444 的請(qǐng)求將由 192.168.0.1 處理38.18.61.26:6295 的請(qǐng)求將由 192.168.0.2 處理71.75.18.82:9686 的請(qǐng)求將由 192.168.0.2 處理26.11.98.111:3781 的請(qǐng)求將由 192.168.0.1 處理62.86.23.37:8570 的請(qǐng)求將由 192.168.0.3 處理*/經(jīng)過上面的測(cè)試我們可以看到性能較好的服務(wù)器1和服務(wù)器2分擔(dān)了大部分的請(qǐng)求，只有少部分請(qǐng)求落到了性能較差的服務(wù)器3上，已經(jīng)初步實(shí)現(xiàn)了負(fù)載均衡。
下面我們將結(jié)合zookeeper，搭建一個(gè)更加逼真的服務(wù)器集群，看看在部分服務(wù)器上線下線的過程中，一致性哈希算法是否仍能夠?qū)崿F(xiàn)負(fù)載均衡。
三. 結(jié)合zookeeper搭建環(huán)境
環(huán)境介紹
首先會(huì)通過啟動(dòng)多臺(tái)虛擬機(jī)模擬服務(wù)器集群，各臺(tái)服務(wù)器都提供一個(gè)相同的接口供消費(fèi)者消費(fèi)。
同時(shí)會(huì)有一個(gè)消費(fèi)者線程不斷地向服務(wù)器集群發(fā)起請(qǐng)求，這些請(qǐng)求會(huì)經(jīng)過一致性哈希算法均衡負(fù)載到各個(gè)服務(wù)器。
為了能夠模擬上述場(chǎng)景, 我們必須在客戶端維護(hù)一個(gè)服務(wù)器列表, 使得客戶端能夠通過一致性哈希算法選擇服務(wù)器發(fā)送。 (現(xiàn)實(shí)中可能會(huì)把一致性哈希算法實(shí)現(xiàn)在前端服務(wù)器, 客戶先訪問前端服務(wù)器, 再路由到后端服務(wù)器集群)。
但是我們的重點(diǎn)是模擬服務(wù)器的宕機(jī)和上線，看看一致性哈希算法是否仍能實(shí)現(xiàn)負(fù)載均衡。所以客戶端必須能夠感知服務(wù)器端的變化并動(dòng)態(tài)地調(diào)整它的服務(wù)器列表。
為了完成這項(xiàng)工作, 我們引入zookeeper, zookeeper的數(shù)據(jù)一致性算法保證數(shù)據(jù)實(shí)時(shí), 準(zhǔn)確, 客戶端能夠通過zookeeper得知實(shí)時(shí)的服務(wù)器情況。
具體操作是這樣的: 服務(wù)器集群先以臨時(shí)節(jié)點(diǎn)的方式連接到zookeeper, 并在zookeeper上注冊(cè)自己的接口服務(wù)(注冊(cè)節(jié)點(diǎn)). 客戶端連接上zookeeper后, 把已注冊(cè)的節(jié)點(diǎn)(服務(wù)器)添加到自己的服務(wù)器列表中。
如果有服務(wù)器宕機(jī)的話, 由于當(dāng)初注冊(cè)的是瞬時(shí)節(jié)點(diǎn)的原因, 該臺(tái)服務(wù)器節(jié)點(diǎn)會(huì)從zookeeper中注銷。客戶端監(jiān)聽到服務(wù)器節(jié)點(diǎn)有變時(shí), 也會(huì)動(dòng)態(tài)調(diào)整自己的服務(wù)器列表, 把當(dāng)宕機(jī)的服務(wù)器從服務(wù)器列表中刪除, 因此不會(huì)再向該服務(wù)器發(fā)送請(qǐng)求, 負(fù)載均衡的任務(wù)將交到剩余的機(jī)器身上。
當(dāng)有服務(wù)器從新連接上集群后, 客戶端的服務(wù)器列表也會(huì)更新, 哈希環(huán)也將做出相應(yīng)的變化以提供負(fù)載均衡。
具體操作:
I. 搭建zookeeper集群環(huán)境:
由于zookeeper不是本案例的重點(diǎn), 細(xì)節(jié)暫不展開講了.
II. 創(chuàng)建服務(wù)器集群, 提供RPC遠(yuǎn)程調(diào)用服務(wù)
3.封裝操作zookeeper和發(fā)布遠(yuǎn)程服務(wù)的接口供自己調(diào)用, 本案例中發(fā)布遠(yuǎn)程服務(wù)使用Java自身提供的rmi包完成, 如果沒有了解過可以參考這篇
public class ServiceProvider { private CountDownLatch latch = new CountDownLatch(1); /** * 連接zookeeper集群 */ public ZooKeeper connectToZK(){ ZooKeeper zk = null; try { zk = new ZooKeeper(Constant.ZK_HOST, Constant.ZK_TIME_OUT, new Watcher() { @Override public void process(WatchedEvent watchedEvent) { //如果連接上了就喚醒當(dāng)前線程. latch.countDown(); } }); latch.await();//還沒連接上時(shí)當(dāng)前線程等待 } catch (Exception e) { e.printStackTrace(); } return zk; } /** * 創(chuàng)建znode節(jié)點(diǎn) * @param zk * @param url 節(jié)點(diǎn)中寫入的數(shù)據(jù) */ public void createNode(ZooKeeper zk, String url){ try{ //要把寫入的數(shù)據(jù)轉(zhuǎn)化為字節(jié)數(shù)組 byte[] data = url.getBytes(); zk.create(Constant.ZK_RMI, data, ZooDefs.Ids.OPEN_ACL_UNSAFE, CreateMode.EPHEMERAL_SEQUENTIAL); } catch (Exception e) { e.printStackTrace(); } } /** * 發(fā)布rmi服務(wù) */ public String publishService(Remote remote, String host, int port){ String url = null; try{ LocateRegistry.createRegistry(port); url = "rmi://" + host + ":" + port + "/rmiService"; Naming.bind(url, remote); } catch (Exception e) { e.printStackTrace(); } return url; } /** * 發(fā)布rmi服務(wù), 并且將服務(wù)的url注冊(cè)到zookeeper集群中 */ public void publish(Remote remote, String host, int port){ //調(diào)用publishService, 得到服務(wù)的url地址 String url = publishService(remote, host, port); if(null != url){ ZooKeeper zk = connectToZK();//連接到zookeeper if(null != zk){ createNode(zk, url); } } }}III. 編寫客戶端程序(運(yùn)用一致性哈希算法實(shí)現(xiàn)負(fù)載均衡
IV. 對(duì)服務(wù)器調(diào)用數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析
重溫一遍模擬的過程: 首先分別在7777, 8888, 9999端口啟動(dòng)了3臺(tái)服務(wù)器. 然后啟動(dòng)客戶端進(jìn)行訪問. 7777, 8888端口的兩臺(tái)服務(wù)器設(shè)置性能指數(shù)為1000, 而9999端口的服務(wù)器性能指數(shù)設(shè)置為300。
在客戶端運(yùn)行期間, 我手動(dòng)關(guān)閉了8888端口的服務(wù)器, 客戶端正常打印出服務(wù)器變化信息。此時(shí)理論上不會(huì)有訪問被路由到8888端口的服務(wù)器。當(dāng)我重新啟動(dòng)8888端口服務(wù)器時(shí), 客戶端打印出服務(wù)器變化信息, 訪問能正常到達(dá)8888端口服務(wù)器。
下面對(duì)各服務(wù)器的訪問量進(jìn)行統(tǒng)計(jì), 看是否實(shí)現(xiàn)了負(fù)載均衡。
測(cè)試程序如下:
public class DataStatistics { private static float ReqToPort7777 = 0; private static float ReqToPort8888 = 0; private static float ReqToPort9999 = 0; public static void main(String[] args) { BufferedReader br = null; try { br = new BufferedReader(new FileReader("C://test.txt")); String line = null; while(null != (line = br.readLine())){ if(line.contains("7777")){ ReqToPort7777++; }else if(line.contains("8888")){ ReqToPort8888++; }else if(line.contains("9999")){ ReqToPort9999++; }else{ print(false); } } print(true); } catch (Exception e) { e.printStackTrace(); }finally { if(null != br){ try { br.close(); } catch (IOException e) { e.printStackTrace(); } br = null; } } } private static void print(boolean isEnd){ if(!isEnd){ System.out.println("------------- 服務(wù)器集群發(fā)生變化 -------------"); }else{ System.out.println("------------- 最后一次統(tǒng)計(jì) -------------"); } System.out.println("截取自上次服務(wù)器變化到現(xiàn)在: "); float total = ReqToPort7777 + ReqToPort8888 + ReqToPort9999; System.out.println("7777端口服務(wù)器訪問量為: " + ReqToPort7777 + ", 占比" + (ReqToPort7777 / total)); System.out.println("8888端口服務(wù)器訪問量為: " + ReqToPort8888 + ", 占比" + (ReqToPort8888 / total)); System.out.println("9999端口服務(wù)器訪問量為: " + ReqToPort9999 + ", 占比" + (ReqToPort9999 / total)); ReqToPort7777 = 0; ReqToPort8888 = 0; ReqToPort9999 = 0; }}/* 以下是輸出結(jié)果------------- 服務(wù)器集群發(fā)生變化 -------------截取自上次服務(wù)器變化到現(xiàn)在: 7777端口服務(wù)器訪問量為: 198.0, 占比0.44196438888端口服務(wù)器訪問量為: 184.0, 占比0.41071439999端口服務(wù)器訪問量為: 66.0, 占比0.14732143------------- 服務(wù)器集群發(fā)生變化 -------------截取自上次服務(wù)器變化到現(xiàn)在: 7777端口服務(wù)器訪問量為: 510.0, 占比0.75892868888端口服務(wù)器訪問量為: 1.0, 占比0.00148809539999端口服務(wù)器訪問量為: 161.0, 占比0.23958333------------- 最后一次統(tǒng)計(jì) -------------截取自上次服務(wù)器變化到現(xiàn)在: 7777端口服務(wù)器訪問量為: 410.0, 占比0.432489458888端口服務(wù)器訪問量為: 398.0, 占比0.419831229999端口服務(wù)器訪問量為: 140.0, 占比0.14767933*/V. 結(jié)果
從測(cè)試數(shù)據(jù)可以看出, 不管是8888端口服務(wù)器宕機(jī)之前, 還是宕機(jī)之后, 三臺(tái)服務(wù)器接收的訪問量和性能指數(shù)成正比，成功地驗(yàn)證了一致性哈希算法的負(fù)載均衡作用。
四. 擴(kuò)展思考
初識(shí)一致性哈希算法的時(shí)候, 對(duì)這種奇特的思路佩服得五體投地。但是一致性哈希算法除了能夠讓后端服務(wù)器實(shí)現(xiàn)負(fù)載均衡, 還有一個(gè)特點(diǎn)可能是其他負(fù)載均衡算法所不具備的。
這個(gè)特點(diǎn)是基于哈希函數(shù)的, 我們知道通過哈希函數(shù), 固定的輸入能夠產(chǎn)生固定的輸出. 換句話說, 同樣的請(qǐng)求會(huì)路由到相同的服務(wù)器. 這點(diǎn)就很牛逼了, 我們可以結(jié)合一致性哈希算法和緩存機(jī)制提供后端服務(wù)器的性能。
比如說在一個(gè)分布式系統(tǒng)中, 有一個(gè)服務(wù)器集群提供查詢用戶信息的方法, 每個(gè)請(qǐng)求將會(huì)帶著用戶的uid到達(dá), 我們可以通過哈希函數(shù)進(jìn)行處理(從上面的演示代碼可以看到, 這點(diǎn)是可以輕松實(shí)現(xiàn)的), 使同樣的uid路由到某個(gè)獨(dú)定的服務(wù)器. 這樣我們就可以在服務(wù)器上對(duì)該的uid背后的用戶信息進(jìn)行緩存, 從而減少對(duì)數(shù)據(jù)庫(kù)或其他中間件的操作, 從而提高系統(tǒng)效率。
當(dāng)然如果使用該策略的話, 你可能還要考慮緩存更新等操作, 但作為一種優(yōu)良的策略, 我們可以考慮在適當(dāng)?shù)膱?chǎng)合靈活運(yùn)用。
以上思考受啟發(fā)于Dubbo框架中對(duì)其實(shí)現(xiàn)的四種負(fù)載均衡策略的描述。
總結(jié)
以上是生活随笔為你收集整理的bootstracp实现树形列表_Java实现一致性哈希算法，并搭建环境测试其负载均衡特性...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： mysql忽略表名大小写_Mysql 表
- 下一篇： 一般首刷信用卡都送什么 首刷礼品通常都有