电脑知识|欧美黑人一区二区三区|软件|欧美黑人一级爽快片淫片高清|系统|欧美黑人狂野猛交老妇|数据库|服务器|编程开发|网络运营|知识问答|技术教程文章 - 好吧啦网

您的位置:首頁技術文章
文章詳情頁

詳解Java分布式系統中一致性哈希算法

瀏覽:32日期:2022-08-13 18:47:05
業務場景

近年來B2C、O2O等商業概念的提出和移動端的發展,使得分布式系統流行了起來。分布式系統相對于單系統,解決了流量大、系統高可用和高容錯等問題。功能強大也意味著實現起來需要更多技術的支持。例如系統訪問層的負載均衡,緩存層的多實例主從復制備份,數據層的分庫分表等。

我們以負載均衡為例,常見的負載均衡方法有很多,但是它們的優缺點也都很明顯:

隨機訪問策略。系統隨機訪問,缺點:可能造成服務器負載壓力不均衡,俗話講就是撐的撐死,餓的餓死。 輪詢策略。請求均勻分配,如果服務器有性能差異,則無法實現性能好的服務器能夠多承擔一部分。 權重輪詢策略。權值需要靜態配置,無法自動調節,不適合對長連接和命中率有要求的場景。 Hash取模策略。不穩定,如果列表中某臺服務器宕機,則會導致路由算法產生變化,由此導致命中率的急劇下降。 一致性哈希策略。

以上幾個策略,排除本篇介紹的一致性哈希,可能使用最多的就是 Hash取模策略了。Hash取模策略的缺點也是很明顯的,這種缺點也許在負載均衡的時候不是很明顯,但是在涉及數據訪問的主從備份和分庫分表中就體現明顯了。

使用Hash取模的問題1.負載均衡

負載均衡時,假設現有3臺服務器(編號分別為0、1、2),使用哈希取模的計算方式則是:對訪問者的IP,通過固定算式hash(IP) % N(N為服務器的個數),使得每個IP都可以定位到特定的服務器。

例如現有IP地址 10.58.34.31,對IP哈希取模策時,計算結果為2,即訪問編號為2的服務器:

String ip = '10.58.34.31';int v1 = hash(ip) % 3;System.out.println('訪問服務器:' + v1);// 訪問服務器:2

如果此時服務器2宕機了,則會導致所有計算結果為2的 IP 對應的用戶都訪問異常(包括上例中的IP)?;蛘吣阈略隽艘慌_服務器3,這時不修改N值的話那么服務器3永遠不會被訪問到。

詳解Java分布式系統中一致性哈希算法

當然如果你能動態獲取到當前可用服務器的個數,亦即N值是根據當前可用服務器個數動態來變化的,則可解決此問題。但是對于類似要在特定地區或特定IP來訪問特定服務器的這種需求就會造成訪問偏差。

2.分庫分表

負載均衡中有這種問題,那么分庫分表中同樣也有這樣的問題。例如隨著業務的飛速增長,我們的注冊用戶也越來越多,單個用戶表數量已經達到千萬級甚至更大。由于Mysql的單表建議百萬級數據存儲,所以這時為了保證系統查詢和運行效率,肯定會考慮到分庫分表。

對于分庫分表,數據的分配是個重要的問題,你需要保證數據分配在這個服務器,那么在查詢時也需要到該服務器上來查詢,否則會造成數據查詢丟失的問題。

通常是根據用戶的 ID 哈希取模得到的值然后路由到對應的存儲位置,計算公式為:hash(userId) % N,其中N為分庫或分表的個數。

例如分庫數為2時,計算結果為1,則ID為1010的用戶存儲在編號為1對應的庫中:

String userId = '1010';int v1 = hash(userId) % 2;System.out.println('存儲:' + v1);// 存儲:1

詳解Java分布式系統中一致性哈希算法

之后業務數量持續增長,又新增一臺用戶服務庫,當我們根據ID=1010去查詢數據時,路由計算方式為:

int v2 = hash(userId) % 3;System.out.println('存儲:' + v2);// 存儲:0

我們得到的路由值是0,最后的結果就不用說了,存在編號1上的數據我們去編號為0的庫上去查詢肯定是得不到查詢結果的。

詳解Java分布式系統中一致性哈希算法

為了數據可用,你需要做數據遷移,按照新的路由規則對所有用戶重新分配存儲地址。每次的庫或表的數量改變你都需要做一次全部用戶信息數據的遷移。不用想這其中的工作量是有多費時費力了。

是否有某種方法,有效解決這種分布式存儲結構下動態增加或刪除節點所帶來的問題,能保證這種不受實例數量變化影響而準確路由到正確的實例上的算法或實現機制呢?解決這些問題,一致性哈希算法誕生了。

基本思想原理

一致性哈希算法在1997年由麻省理工學院的Karger等人在解決分布式Cache中提出的,設計目標是為了解決因特網中的熱點(Hot spot)問題,初衷和CARP十分類似。一致性哈希修正了CARP使用的簡單哈希算法帶來的問題,使得DHT可以在P2P環境中真正得到應用。

上面說的哈希取模方法,它是針對一個點的,業務布局嚴重依賴于這個計算的點值結果。你結算的結果是2,那么就對應到編號為2的服務器上。這樣的映射就造成了業務容錯性和可擴展性極低。

我們思考下,是否可以將這個計算結果的點值賦予范圍的意義?我們知道Hash取模之后得到的是一個 int 型的整值。

//Objects 類中默認的 hash 方法 public static int hash(Object... values) { return Arrays.hashCode(values);}

既然 hash的計算結果是 int 類型,而 java 中 int 的最小值是-2^31,最大值是2^31-1。意味著任何通過哈希取模之后的無符號值都會在 0 ~ 2^31-1范圍之間,共2^32個數。那我們是否可以不對服務器的數量進行取模而是直接對2^32取模。這就形成了一致性哈希的基本算法思想,什么意思呢?

這里需要注意一點:

默認的 hash 方法結果是有負值的情況,因此需要我們重寫hash方法,保證哈希值的非負性。

簡單來說,一致性Hash算法將整個哈希值空間組織成一個虛擬的圓環,如假設某哈希函數 H 的值空間為 0 ~ 2^32-1(即哈希值是一個32位無符號整形),整個哈希環如下:

詳解Java分布式系統中一致性哈希算法

整個空間圓按順時針方向布局,圓環的正上方的點代表0,0點右側的第一個點代表1。以此類推2、3、4、5、6……直到232-1,也就是說0點左側的第一個點代表232-1, 0和2^32-1在零點中方向重合,我們把這個由2^32個點組成的圓環稱為 Hash環。

那么,一致性哈希算法與上圖中的圓環有什么關系呢?仍然以之前描述的場景為例,假設我們有4臺服務器,服務器0、服務器1、服務器2,服務器3,那么,在生產環境中,這4臺服務器肯定有自己的 IP 地址或主機名,我們使用它們各自的 IP 地址或主機名作為關鍵字進行哈希計算,使用哈希后的結果對2^32取模,可以使用如下公式示意:

hash(服務器的IP地址) % 2^32

最后會得到一個 [0, 2^32-1]之間的一個無符號整形數,這個整數就代表服務器的編號。同時這個整數肯定處于[0, 2^32-1]之間,那么,上圖中的 hash 環上必定有一個點與這個整數對應。那么這個服務器就可以映射到這個環上。

多個服務器都通過這種方式進行計算,最后都會各自映射到圓環上的某個點,這樣每臺機器就能確定其在哈希環上的位置,如下圖所示。

詳解Java分布式系統中一致性哈希算法

如何提高容錯性和擴展性的

那么用戶訪問,如何分配訪問的服務器呢?我們根據用戶的 IP 使用上面相同的函數 Hash 計算出哈希值,并確定此數據在環上的位置,從此位置沿環 順時針行走,遇到的第一臺服務器就是其應該定位到的服務器。

詳解Java分布式系統中一致性哈希算法

從上圖可以看出 用戶1 順時針遇到的第一臺服務器是 服務器3 ,所以該用戶被分配給服務器3來提供服務。同理可以看出用戶2被分配給了服務器2。

1. 新增服務器節點

如果這時需要新增一臺服務器節點,一致性哈希策略是如何應對的呢?如下圖所示,我們新增了一臺服務器4,通過上述一致性哈希算法計算后得出它在哈希環的位置。

詳解Java分布式系統中一致性哈希算法

可以發現,原來訪問服務器3的用戶1現在訪問的對象是服務器4,用戶能正常訪問且服務不需要停機就可以自動切換。

2. 刪除服務器節點

如果這時某臺服務器異常宕機或者運維撤銷了一臺服務器,那么這時會發生什么情況呢?如下圖所示,假設我們撤銷了服務器2。

詳解Java分布式系統中一致性哈希算法

可以看出,我們服務仍然能正常提供服務,只不過這時用戶2會被分配到服務1上了而已。

通過一致性哈希的方式,我們提高了我們系統的容錯性和可擴展性,分布式節點的變動不會影響整個系統的運行且不需要我們做一些人為的調整策略。

Hash環的數據傾斜問題

一致性哈希雖然為我們提供了穩定的切換策略,但是它也有一些小缺陷。因為 hash取模算法得到的結果是隨機的,我們并不能保證各個服務節點能均勻的分配到哈希環上。

例如當有4個服務節點時,我們把哈希環認為是一個圓盤時鐘,我們并不能保證4個服務節點剛好均勻的落在時鐘的 12、3、6、9點上。

分布不均勻就會產生一個問題,用戶的請求訪問就會不均勻,同時4個服務承受的壓力就會不均勻。這種問題現象我們稱之為,Hash環的數據傾斜問題。

詳解Java分布式系統中一致性哈希算法

如上圖所示,服務器0 到 服務器1 之間的哈希點值占據比例最大,大量請求會集中到 服務器1 上,而只有極少量會定位到 服務器0 或其他幾個節點上,從而出現 hash環偏斜的情況。

如果想要均衡的將緩存分布到每臺服務器上,最好能讓這每臺服務器盡量多的、均勻的出現在hash環上,但是如上圖中所示,真實的服務器資源只有4臺,我們怎樣憑空的讓它們多起來呢?

既然沒有多余的真正的物理服務器節點,我們就只能將現有的物理節點通過虛擬的方法復制出來。

這些由實際節點虛擬復制而來的節點被稱為 '虛擬節點',即對每一個服務節點計算多個哈希,每個計算結果位置都放置一個此服務節點,稱為虛擬節點。具體做法可以在服務器IP或主機名的后面增加編號來實現。

如上圖所示,假如 服務器1 的 IP 是 192.168.32.132,那么原 服務器1 節點在環形空間的位置就是hash('192.168.32.132') % 2^32。

我們基于 服務器1 構建兩個虛擬節點,Server1-A 和 Server1-B,虛擬節點在環形空間的位置可以利用(IP+后綴)計算,例如:

hash('192.168.32.132#A') % 2^32hash('192.168.32.132#B') % 2^32

此時,環形空間中不再有物理節點 服務器1,服務器2,……,替代的是只有虛擬節點 Server1-A,Server1-B,Server2-A,Server2-B,……。

詳解Java分布式系統中一致性哈希算法

同時數據定位算法不變,只是多了一步虛擬節點到實際節點的映射,例如定位到 “Server1-A”、“Server1-B” 兩個虛擬節點的數據均定位到 服務器1上。這樣就解決了服務節點少時數據傾斜的問題。

在實際應用中,通常將虛擬節點數設置為32甚至更大,因此即使很少的服務節點也能做到相對均勻的數據分布。由于虛擬節點數量較多,與虛擬節點的映射關系也變得相對均衡了。

總結

一致性哈希一般在分布式緩存中使用的也比較多,本篇只介紹了服務的負載均衡和分布式存儲,對于分布式緩存其實原理是類似的,讀者可以自己舉一反三來思考下。

其實,在分布式存儲和分布式緩存中,當服務節點發生變化時(新增或減少),一致性哈希算法并不能杜絕數據遷移的問題,但是可以有效避免數據的全量遷移,需要遷移的只是更改的節點和它的上游節點它們兩個節點之間的那部分數據。

另外,我們都知道 hash算法 有一個避免不了的問題,就是哈希沖突。對于用戶請求IP的哈希沖突,其實只是不同用戶被分配到了同一臺服務器上,這個沒什么影響。但是如果是服務節點有哈希沖突呢?這會導致兩個服務節點在哈希環上對應同一個點,其實我感覺這個問題也不大,因為一方面哈希沖突的概率比較低,另一方面我們可以通過虛擬節點也可減少這種情況。

以上就是詳解Java分布式系統中一致性哈希算法的詳細內容,更多關于Java算法的資料請關注好吧啦網其它相關文章!

標簽: Java
相關文章:
主站蜘蛛池模板: 国产频谱分析仪-国产网络分析仪-上海坚融实业有限公司 | ph计,实验室ph计,台式ph计,实验室酸度计,台式酸度计 | 江苏全风,高压风机,全风环保风机,全风环形高压风机,防爆高压风机厂家-江苏全风环保科技有限公司(官网) | 风信子发稿-专注为企业提供全球新闻稿发布服务 | 电销卡 防封电销卡 不封号电销卡 电话销售卡 白名单电销卡 电销系统 外呼系统 | 工业车间焊接-整体|集中除尘设备-激光|等离子切割机配套除尘-粉尘烟尘净化治理厂家-山东美蓝环保科技有限公司 | 澳门精准正版免费大全,2025新澳门全年免费,新澳天天开奖免费资料大全最新,新澳2025今晚开奖资料,新澳马今天最快最新图库-首页-东莞市傲马网络科技有限公司 | 密集架-手摇-智能-移动-价格_内蒙古档案密集架生产厂家 | 泰州物流公司_泰州货运公司_泰州物流专线-东鑫物流公司 | 粉末包装机-给袋式包装机-全自动包装机-颗粒-液体-食品-酱腌菜包装机生产线【润立机械】 | 上海质量认证办理中心 | 论文查重_免费论文查重_知网学术不端论文查重检测系统入口_论文查重软件 | 深圳天际源广告-形象堆头,企业文化墙,喷绘,门头招牌设计制作专家 | 液压升降平台_剪叉式液压/导轨式升降机_传菜机定做「宁波日腾升降机厂家」 | 泥浆在线密度计厂家-防爆数字压力表-膜盒-远传压力表厂家-江苏大亚自控设备有限公司 | 【同风运车官网】一站式汽车托运服务平台,验车满意再付款 | 酵素生产厂家_酵素OEM_酵素加盟_酵素ODM_酵素原料厂家_厦门益力康 | 衬塑设备,衬四氟设备,衬氟设备-淄博鲲鹏防腐设备有限公司 | 山东PE给水管厂家,山东双壁波纹管,山东钢带增强波纹管,山东PE穿线管,山东PE农田灌溉管,山东MPP电力保护套管-山东德诺塑业有限公司 | 旗帜网络笔记-免费领取《旗帜网络笔记》电子书 | 退火炉,燃气退火炉,燃气热处理炉生产厂家-丹阳市丰泰工业炉有限公司 | 示波器高压差分探头-国产电流探头厂家-南京桑润斯电子科技有限公司 | 送料机_高速冲床送料机_NC伺服滚轮送料机厂家-东莞市久谐自动化设备有限公司 | Q361F全焊接球阀,200X减压稳压阀,ZJHP气动单座调节阀-上海戎钛 | uv机-uv灯-uvled光固化机-生产厂家-蓝盾机电 | 全自动过滤器_反冲洗过滤器_自清洗过滤器_量子除垢环_量子环除垢_量子除垢 - 安士睿(北京)过滤设备有限公司 | 蓄电池回收,ups电池后备电源回收,铅酸蓄电池回收,机房电源回收-广州益夫铅酸电池回收公司 | 嘉兴泰东园林景观工程有限公司_花箱护栏 | 一体化污水处理设备,一体化污水设备厂家-宜兴市福源水处理设备有限公司 | 聚丙烯酰胺_厂家_价格-河南唐达净水材料有限公司 | 欧盟ce检测认证_reach检测报告_第三方检测中心-深圳市威腾检验技术有限公司 | 抖音短视频运营_企业网站建设_网络推广_全网自媒体营销-东莞市凌天信息科技有限公司 | 乙炔气体报警装置|固定式氯化氢检测仪|河南驰诚电气百科 | 污水提升器,污水提升泵,地下室排水,增压泵,雨水泵,智能供排水控制器-上海智流泵业有限公司 | 广州小程序开发_APP开发公司_分销商城系统定制_小跑科技 | 鹤壁创新仪器公司-全自动量热仪,定硫仪,煤炭测硫仪,灰熔点测定仪,快速自动测氢仪,工业分析仪,煤质化验仪器 | 不干胶标签-不干胶贴纸-不干胶标签定制-不干胶标签印刷厂-弗雷曼纸业(苏州)有限公司 | 连续密炼机_双转子连续密炼机_连续式密炼机-南京永睿机械制造有限公司 | 平面钻,法兰钻,三维钻-山东兴田阳光智能装备股份有限公司 | 培训无忧网-教育培训咨询招生第三方平台 | 电地暖-电采暖-发热膜-石墨烯电热膜品牌加盟-暖季地暖厂家 |