什麼是一致性哈希?一致性哈希是如何工作的?如何設計一致性哈希?

来源:https://www.cnblogs.com/powerai/archive/2023/05/25/17433152.html
-Advertisement-
Play Games

如果你有 *n* 個緩存伺服器,一個常見的負載均衡方式是使用以下的哈希方法: *伺服器索引 = 哈希(鍵) % N*,其中 *N* 是伺服器池的大小。 讓我們通過一個例子來說明這是如何工作的。如表5-1所示,我們有4台伺服器和8個字元串鍵及其哈希值。 ![image-2023052022160981 ...


如果你有 n 個緩存伺服器,一個常見的負載均衡方式是使用以下的哈希方法:

伺服器索引 = 哈希(鍵) % N,其中 N 是伺服器池的大小。

讓我們通過一個例子來說明這是如何工作的。如表5-1所示,我們有4台伺服器和8個字元串鍵及其哈希值。

image-20230520221609818

為了獲取存儲某個鍵的伺服器,我們執行模運算 f(鍵) % 4。例如,哈希(鍵0) % 4 = 1 意味著客戶端必須聯繫伺服器1來獲取緩存的數據。圖5-1展示了基於表5-1的鍵的分佈。

image-20230520221627093

當伺服器池的大小固定且數據分佈均勻時,這種方法工作得很好。然而,當新的伺服器被添加,或者現有的伺服器被移除時,就會出現問題。例如,如果伺服器1離線,伺服器池的大小就變成了3。使用相同的哈希函數,我們得到的鍵的哈希值是相同的。但是應用模運算會因為伺服器數量減少了1而得到不同的伺服器索引。我們應用 哈希 % 3 得到的結果如表5-2所示:

image-20230520221638743

圖5-2展示了基於表5-2的新鍵分佈。

image-20230520221651912

如圖5-2所示,大多數鍵都被重新分配了,而不僅僅是那些最初存儲在離線伺服器(伺服器1)中的鍵。這意味著,當伺服器1離線時,大多數緩存客戶端將連接到錯誤的伺服器來獲取數據。這導致了一場緩存未命中的風暴。一致性哈希是一種有效的技術來緩解這個問題。

一致性哈希

引用自維基百科:"一致性哈希是一種特殊的哈希,使得當哈希表大小改變且使用一致性哈希時,平均只有 k/n 個鍵需要被重新映射,其中 k 是鍵的數量,n 是槽位的數量。相比之下,在大多數傳統哈希表中,數組槽位數量的變化導致幾乎所有的鍵都需要被重新映射[1]”。

哈希空間和哈希環

現在我們理解了一致性哈希的定義,讓我們瞭解它是如何工作的。假設使用SHA-1作為哈希函數f,哈希函數的輸出範圍是:x0, x1, x2, x3, ..., xn。在密碼學中,SHA-1的哈希空間從0到2^160 - 1。也就是說,x0 對應0,xn 對應2^160 - 1,所有其他的哈希值都落在0和2^160 - 1之間。圖5-3展示了哈希空間。

image-20230520221712073

通過連接兩端,我們得到一個如圖5-4所示的哈希環:

image-20230520221721241

哈希伺服器

使用相同的哈希函數f,我們根據伺服器的IP或名字將伺服器映射到環上。圖5-5顯示了4台伺服器被映射到哈希環上。

image-20230520221733973

哈希鍵

值得一提的是,這裡使用的哈希函數與“重哈希問題”中的不同,並且沒有模運算。如圖5-6所示,4個緩存鍵(key0,key1,key2和key3)被哈希到哈希環上。

image-20230520221804796

伺服器查找

為了確定一個鍵存儲在哪個伺服器上,我們從環上的鍵位置順時針方向進行尋找,直到找到一個伺服器。圖5-7解釋了這個過程。順時針方向,key 0 存儲在 server 0上;key1 存儲在 server 1 上;key2 存儲在 server 2 上;key3 存儲在 server 3 上。

image-20230520221817073

添加伺服器

使用上述邏輯,添加新伺服器只需要重新分配一部分鍵。

在圖5-8中,新增 server 4 後,只有 key0 需要被重新分配。k1, k2,k3 仍然在相同的伺服器上。讓我們仔細看看這個邏輯。在 server 4 添加之前,key0 存儲在 server 0 上。現在,key0 將存儲在 server 4 上,因為 server 4 是它從環上的 key0 位置順時針方向遇到的第一個伺服器。其他的鍵根據一致性哈希演算法不需要重新分配。

image-20230520221838084

移除伺服器

當伺服器被移除時,只有少部分的鍵需要通過一致性哈希進行重新分配。在圖5-9中,當 server 1 被移除時,只有 key1 必須被映射到 server 2。其餘的鍵不受影響。

image-20230520221851239

基本方法中的兩個問題

一致性哈希演算法是由MIT的Karger等人提出的[1]。基本步驟如下:

  • 使用均勻分佈的哈希函數將伺服器和鍵映射到環上。
  • 要找出鍵映射到哪個伺服器,從鍵位置開始順時針方向找到環上的第一個伺服器。

這種方法存在兩個問題。首先,考慮到伺服器可能會被添加或移除,不可能在環上為所有伺服器保持相同大小的分區。分區是相鄰伺服器之間的哈希空間。每個伺服器被分配到的環上的分區大小可能非常小或者相當大。在圖5-10中,如果s1被移除,s2的分區(雙向箭頭高亮表示)就是s0s3分區的兩倍大。

image-20230520221901282

第二,環上的鍵分佈可能非均勻。例如,如果伺服器映射到圖5-11中列出的位置,大部分的鍵都存儲在server 2上。然而,server 1server 3 沒有任何數據。

image-20230520221911034

一種被稱為虛擬節點或副本的技術被用來解決這些問題。

虛擬節點

虛擬節點是指實際節點,每個伺服器在環上都由多個虛擬節點表示。在圖5-12中,server 0server 1 都有3個虛擬節點。這個3是隨意選擇的;在實際系統中,虛擬節點的數量要多得多。我們不再使用 s0,而是使用 s0_0, s0_1s0_2 來在環上表示 server 0。同樣,s1_0, s1_1s1_2 在環上表示 server 1。有了虛擬節點,每個伺服器就負責多個分區。標簽為 s0 的分區(邊)由 server 0 管理。另一方面,標簽為 s1 的分區由 server 1 管理。

image-20230520221923607

要找出一個鍵存儲在哪個伺服器上,我們從鍵的位置順時針方向去找環上遇到的第一個虛擬節點。在圖5-13中,要找出k0存儲在哪個伺服器上,我們從k0的位置順時針方向找到虛擬節點s1_1,它指向server 1

image-20230520221943844

隨著虛擬節點數量的增加,鍵的分佈變得更加均衡。這是因為隨著虛擬節點數量的增加,標準差變得更小,導致數據分佈均衡。標準差衡量了數據的分散程度。線上研究的一項實驗結果[2]表明,當有一百或兩百個虛擬節點時,標準差在均值的5%(200個虛擬節點)到10%(100個虛擬節點)之間。當我們增加虛擬節點數量時,標準差會變小。然而,我們需要更多的空間來存儲虛擬節點的數據。這是一個權衡,我們可以調整虛擬節點的數量以適應我們的系統需求。

找到受影響的鍵

當添加或移除一個伺服器時,部分數據需要被重新分佈。我們如何找到受影響的範圍以重新分配鍵呢?

在圖5-14中,server 4被添加到環中。受影響的範圍從s4(新添加的節點)開始,逆時針移動到找到一個伺服器(s3)。因此,位於s3s4之間的鍵需要被重新分配給s4

image-20230520221954742

當一個伺服器(s1)如圖5-15所示被移除時,受影響的範圍從s1(被移除的節點)開始,逆時針繞環移動到找到一個伺服器(s0)。因此,位於s0s1之間的鍵必須被重新分配給s2

image-20230520222004501

總結

在這一章,我們深入討論了一致性哈希,包括為什麼需要它以及它是如何工作的。一致性哈希的好處包括:

  • 當伺服器被添加或移除時,最小化鍵的重新分佈。
  • 因為數據更均勻地分佈,所以易於橫向擴展。
  • 緩解熱點鍵問題。過度訪問特定的分片可能導致伺服器過載。想象一下,Katy Perry、Justin Bieber和Lady Gaga的數據全部都在同一個分片上。一致性哈希通過更均勻地分佈數據來緩解這個問題。

一致性哈希在現實世界的系統中被廣泛應用,包括一些著名的系統:

  • Amazon的Dynamo資料庫的分區組件 [3]
  • Apache Cassandra中跨集群的數據分區 [4]
  • Discord聊天應用 [5]
  • Akamai內容分髮網絡 [6]
  • Maglev網路負載均衡器 [7]

恭喜你走到這一步!現在給自己一個贊。幹得好!

參考資料

[1] 一致性哈希:https://en.wikipedia.org/wiki/Consistent_hashing

[2] 一致性哈希:

https://tom-e-white.com/2007/11/consistent-hashing.html

[3] Dynamo:亞馬遜的高可用鍵值存儲:
https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf

[4] Cassandra - 一個去中心化的結構化存儲系統:

http://www.cs.cornell.edu/Projects/ladis2009/papers/Lakshman-ladis2009.PDF

[5] 如何將Discord Elixir擴展到500萬併發用戶:
https://blog.discord.com/scaling-elixir-f9b8e1e7c29b

[6] CS168:現代演算法工具箱第一課:簡介和一致性哈希:http://theory.stanford.edu/~tim/s16/l/l1.pdf

[7] Maglev:一個快速可靠的軟體網路負載均衡器:
https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/44824.pdf


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Iframe是一個歷史悠久的HTML元素,根據MDN WEB DOCS官方介紹,Iframe定義為HTML內聯框架元素,表示嵌套的Browsing Context,它能夠將另一個HTML頁面嵌入到當前頁面中。Iframe可以廉價實現跨應用級的頁面共用,並且具有使用簡單、高相容性、內容隔離等優點,因此... ...
  • 比如老王我,用npm init新建一個包,改把改把,然後來個npm publish,so easy ✌️!Too young too naive, baby
  • 在 CSS 中,存在許多數學函數,這些函數能夠通過簡單的計算操作來生成某些屬性值,例如 : * calc():用於計算任意長度、百分比或數值型數據,並將其作為 CSS 屬性值。 * min() 和 max():用於比較一組數值中的最大值或最小值,也可以與任意長度、百分比或數值型數據一同使用。 * c ...
  • 1.轉換 轉換(transform)是CSS3中具有顛覆性的特征之一,可以實現元素的位移、旋轉、縮放等效果。 轉換(transform)可以簡單理解為變形。 移動:translate 旋轉:rotate 縮放:scale 1.1 二維坐標系 2D轉換是改變在二維平面上的位置和形狀的一種技術。 1.2 ...
  • > 隨著人工智慧技術的不斷發展,阿裡體育等IT大廠,推出的“樂動力”、“天天跳繩”AI運動APP,讓**雲上運動會、線上運動會、健身打卡、AI體育指導**等概念空前火熱。那麼,能否將這些在APP成功應用的場景搬上小程式,分享這些概念的紅利呢?本系列文章就帶您一步一步從零開始開發一個AI運動小程式,本 ...
  • 相信很多公司的前端開發人員都會選擇使用vue+element-ui的形式來開發公司的管理後臺系統,基於element-ui很豐富的組件生態,我們可以很快速的開發管理後臺系統的頁面(管理後臺系統的頁面也不複雜,大多都是分頁查詢類需求和增刪改查)。但一個前端框架有優點,就必然會有一些缺點或bug存在,e... ...
  • 寫這篇的目的是,今天在重新學習javascript時發現了HttpOnly這個標簽,所以專門的mark了下。 誰在什麼時候發明瞭HttpOnly 2002年微軟為ie6的sp1創造了HttpOnly 什麼是HttpOnly HttpOnly是包含在http返回頭Set-Cookie裡面的一個附加的f ...
  • 本文將學習如何使用滾動控制 ScrollControls 來控制模型的的動畫播放和相機動畫,通過滾動滑鼠滾輪或者上下移動觸摸板,來控制模型的動畫播放進度或者相機的方位視角,從而呈現出驚艷的視覺效果。通過本文的閱讀和案例頁面的實現,你將學習到的知識包括:R3F 生態中的 ScrollControls、... ...
一周排行
    -Advertisement-
    Play Games
  • 1. 說明 /* Performs operations on System.String instances that contain file or directory path information. These operations are performed in a cross-pla ...
  • 視頻地址:【WebApi+Vue3從0到1搭建《許可權管理系統》系列視頻:搭建JWT系統鑒權-嗶哩嗶哩】 https://b23.tv/R6cOcDO qq群:801913255 一、在appsettings.json中設置鑒權屬性 /*jwt鑒權*/ "JwtSetting": { "Issuer" ...
  • 引言 集成測試可在包含應用支持基礎結構(如資料庫、文件系統和網路)的級別上確保應用組件功能正常。 ASP.NET Core 通過將單元測試框架與測試 Web 主機和記憶體中測試伺服器結合使用來支持集成測試。 簡介 集成測試與單元測試相比,能夠在更廣泛的級別上評估應用的組件,確認多個組件一起工作以生成預 ...
  • 在.NET Emit編程中,我們探討了運算操作指令的重要性和應用。這些指令包括各種數學運算、位操作和比較操作,能夠在動態生成的代碼中實現對數據的處理和操作。通過這些指令,開發人員可以靈活地進行算術運算、邏輯運算和比較操作,從而實現各種複雜的演算法和邏輯......本篇之後,將進入第七部分:實戰項目 ...
  • 前言 多表頭表格是一個常見的業務需求,然而WPF中卻沒有預設實現這個功能,得益於WPF強大的控制項模板設計,我們可以通過修改控制項模板的方式自己實現它。 一、需求分析 下圖為一個典型的統計表格,統計1-12月的數據。 此時我們有一個需求,需要將月份按季度劃分,以便能夠直觀地看到季度統計數據,以下為該需求 ...
  • 如何將 ASP.NET Core MVC 項目的視圖分離到另一個項目 在當下這個年代 SPA 已是主流,人們早已忘記了 MVC 以及 Razor 的故事。但是在某些場景下 SSR 還是有意想不到效果。比如某些靜態頁面,比如追求首屏載入速度的時候。最近在項目中回歸傳統效果還是不錯。 有的時候我們希望將 ...
  • System.AggregateException: 發生一個或多個錯誤。 > Microsoft.WebTools.Shared.Exceptions.WebToolsException: 生成失敗。檢查輸出視窗瞭解更多詳細信息。 內部異常堆棧跟蹤的結尾 > (內部異常 #0) Microsoft ...
  • 引言 在上一章節我們實戰了在Asp.Net Core中的項目實戰,這一章節講解一下如何測試Asp.Net Core的中間件。 TestServer 還記得我們在集成測試中提供的TestServer嗎? TestServer 是由 Microsoft.AspNetCore.TestHost 包提供的。 ...
  • 在發現結果為真的WHEN子句時,CASE表達式的真假值判斷會終止,剩餘的WHEN子句會被忽略: CASE WHEN col_1 IN ('a', 'b') THEN '第一' WHEN col_1 IN ('a') THEN '第二' ELSE '其他' END 註意: 統一各分支返回的數據類型. ...
  • 在C#編程世界中,語法的精妙之處往往體現在那些看似微小卻極具影響力的符號與結構之中。其中,“_ =” 這一組合突然出現還真不知道什麼意思。本文將深入剖析“_ =” 的含義、工作原理及其在實際編程中的廣泛應用,揭示其作為C#語法奇兵的重要角色。 一、下劃線 _:神秘的棄元符號 下劃線 _ 在C#中並非 ...