談談一致性哈希演算法

来源:https://www.cnblogs.com/jilodream/archive/2023/06/02/17452331.html
-Advertisement-
Play Games

一致性哈希演算法是1997年由麻省理工的幾位學者提出的用於解決分散式緩存中的熱點問題。大家有沒有發現,我們之前介紹的例如快排之類的演算法是更早的六七十年代,此時分散式還沒有發展起來,大家往往還在提高單機性能。但是九十年代開始,逐漸需要用分散式集群來解決大型問題,相應的演算法研究也就應運而生。在說到一致性哈 ...


一致性哈希演算法是1997年由麻省理工的幾位學者提出的用於解決分散式緩存中的熱點問題。大家有沒有發現,我們之前介紹的例如快排之類的演算法是更早的六七十年代,此時分散式還沒有發展起來,
大家往往還在提高單機性能。但是九十年代開始,逐漸需要用分散式集群來解決大型問題,相應的演算法研究也就應運而生。
在說到一致性哈希演算法,我們還是得先從緩存的發展談起:
緩存,我們一般是用來提速的,當規模或者說數據量小時,我們往往用單機來部署一套緩存系統即可,如下圖:

多台客戶端在查詢數據時,只要根據key進入緩存伺服器查詢到自己想要的內容即可。
但是隨著業務的發展,單一的緩存伺服器往往無法支撐住我們的業務需要。比如緩存數據太大,多城多活的網路部署等,
我們就需要多台緩存伺服器來支撐,如下圖:

客戶端需要查詢緩存時,先根據哈希演算法,講key進行計算,得到哈希值。然後通過哈希值對機器數取模(%n)來判定落在哪台機器上。
這個架構很簡單,也很易實現,我們就不多說了。
但是這裡會存在一個緩存伺服器伸縮的問題:什麼意思呢?比如目前是三台,我們由於業務的需要,需要變為四台,或者變為兩台。那麼我們需要調整一遍所有數據所處的伺服器位置,因為他們存在的位置都有可能改變。

分散式緩存本來就是為瞭解決大數據量問題的,此時重新調整,勢必會極度影響可用性。那麼如何解決呢?
來看看一致性哈希演算法的思路:
我們假設存在一個虛擬環,這個環足夠大,上邊存在2^32個節點,三台器機器呢,我們根據id計算出他們在環中所處的位置,如圖所示:

 

當我們計算數據所處的緩存位置,不再是根據n來取模,而是根據2^32來取模,此時會有相當多的數據並沒有落在緩存伺服器所處的節點上。
那怎麼辦呢?我們按照順時針方向計算,將數據落在下一個最*的順時針節點上。
如下圖所示:

這樣當我們新增或者刪除節點時,只會影響有限的節點上的數據,極大的縮小了受影響的節點和數據。我們只需要重新計算受影響的數據即可,但是這樣還會存在新的問題:
1、緩存伺服器計算出的位置不均勻,導致覆蓋的節點數差異明顯;
2、數據並不均衡:數據經過哈希和取模運算後,可能落在集中的一片區域中,造成對應的緩存伺服器的數據特別大。
以上問題我們稱之為數據傾斜。數據傾斜的程度明顯後,可能會導致所解決的問題再次出現(前文中的紅字部分)。
那如何解決這種問題呢?很簡單,加節點,只要節點足夠多,那麼就會越來越趨*於*均,數據傾斜的情況就會越不突出。但是緩存伺服器是有限的,並不是想加多少都可以的。
那怎麼辦呢?

我們可以採用虛擬緩存節點的形式解決問題。什麼是虛擬緩存節點,就是並不實際存在的緩存節點。只是一個虛擬的點。
每個真實的緩存伺服器對應多個虛擬緩存節點,兩者是一對多的關係,如下圖所示:

虛擬節點--圖中連接在環上的就是虛擬緩存節點。
真實緩存節點--Cache
每個Cache對應若幹的虛擬節點。當增減Cache時,我們只要調整對應的虛擬節點所對應的數據即可。

 

如果你覺得寫的不錯,歡迎轉載和點贊。 轉載時請保留作者署名jilodream/王若伊_恩賜解脫(博客鏈接:http://www.cnblogs.com/jilodream/


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

-Advertisement-
Play Games
更多相關文章
  • **原文鏈接:** [為什麼說 Go 語言字元串是不可變的?](https://mp.weixin.qq.com/s/AOb6AjKwyTwLeAUou0AU-Q) 最近有讀者留言說,平時在寫代碼的過程中,是會對字元串進行修改的,但網上都說 Go 語言字元串是不可變的,這是為什麼呢? 這個問題本身並 ...
  • aliases: [] tags : " " summary: [基於TCP/IP和UDP協議的Java Socket網路通信編程] author : [yaenli] notekey: [20230512-143738] # Socket 網路模型 Socket編程是在TCP/IP、UDP協議上的 ...
  • # Rust Web 全棧開發之增加教師管理功能 ## 增加教師管理功能 ### 目標 #### Actix HTTP Server #### Actix App - Routes - GET /teachers - GET / teachers /{teacher_id} - POST /teac ...
  • ## 教程簡介 Google Charts 是一個純粹的基於JavaScript的圖表庫,旨在通過添加互動式圖表功能來增強Web應用程式.它支持各種圖表.在Chrome,Firefox,Safari,Internet Explorer(IE)等標準瀏覽器中使用SVG繪製圖表.在傳統的IE 6中,VM ...
  • ## 教程簡介 Excel是辦公室自動化中非常重要的一款軟體,Excel函數則是Excel中的內置函數。Excel函數共包含11類,分別是資料庫函數、日期與時間函數、工程函數、財務函數、信息函數、邏輯函數、查詢和引用函數、數學和三角函數、統計函數、文本函數以及用戶自定義函數。 熟練且高效的使用Exc ...
  • 前端組件 <hd-flex> <el-dialog v-model="isUploadDialog" width="50%" lock-scroll=false> <el-upload class="upload-demo" drag :action="url" :on-success="succe ...
  • 基於java的酒店管理系統設計與實現,酒店訂票系統,酒店預訂系統,酒店信息管理系統,app訂房系統設計與實現; ...
  • 本章將繼續探索內核中解析PE文件的相關內容,PE文件中FOA與VA,RVA之間的轉換也是很重要的,所謂的FOA是文件中的地址,VA則是記憶體裝入後的虛擬地址,RVA是記憶體基址與當前地址的相對偏移,本章還是需要用到`《驅動開發:內核解析PE結構導出表》`中所封裝的`KernelMapFile()`映射函... ...
一周排行
    -Advertisement-
    Play Games
  • PasteSpider是什麼? 一款使用.net編寫的開源的Linux容器部署助手,支持一鍵發佈,平滑升級,自動伸縮, Key-Value配置,項目網關,環境隔離,運行報表,差量升級,私有倉庫,集群部署,版本管理等! 30分鐘上手,讓開發也可以很容易的學會在linux上部署你得項目! [從需求角度介 ...
  • SQLSugar是什麼 **1. 輕量級ORM框架,專為.NET CORE開發人員設計,它提供了簡單、高效的方式來處理資料庫操作,使開發人員能夠更輕鬆地與資料庫進行交互 2. 簡化資料庫操作和數據訪問,允許開發人員在C#代碼中直接操作資料庫,而不需要編寫複雜的SQL語句 3. 支持多種資料庫,包括但 ...
  • 在C#中,經常會有一些耗時較長的CPU密集型運算,因為如果直接在UI線程執行這樣的運算就會出現UI不響應的問題。解決這類問題的主要途徑是使用多線程,啟動一個後臺線程,把運算操作放在這個後臺線程中完成。但是原生介面的線程操作有一些難度,如果要更進一步的去完成線程間的通訊就會難上加難。 因此,.NET類 ...
  • 一:背景 1. 講故事 前些天有位朋友在微信上丟了一個崩潰的dump給我,讓我幫忙看下為什麼出現了崩潰,在 Windows 的事件查看器上顯示的是經典的 訪問違例 ,即 c0000005 錯誤碼,不管怎麼說有dump就可以上windbg開幹了。 二:WinDbg 分析 1. 程式為誰崩潰了 在 Wi ...
  • CSharpe中的IO+NPOI+序列化 文件文件夾操作 學習一下常見的文件、文件夾的操作。 什麼是IO流? I:就是input O:就是output,故稱:輸入輸出流 將數據讀入記憶體或者記憶體輸出的過程。 常見的IO流操作,一般說的是[記憶體]與[磁碟]之間的輸入輸出。 作用 持久化數據,保證數據不再 ...
  • C#.NET與JAVA互通之MD5哈希V2024 配套視頻: 要點: 1.計算MD5時,SDK自帶的計算哈希(ComputeHash)方法,輸入輸出參數都是byte數組。就涉及到字元串轉byte數組轉換時,編碼選擇的問題。 2.輸入參數,字元串轉byte數組時,編碼雙方要統一,一般為:UTF-8。 ...
  • CodeWF.EventBus,一款靈活的事件匯流排庫,實現模塊間解耦通信。支持多種.NET項目類型,如WPF、WinForms、ASP.NET Core等。採用簡潔設計,輕鬆實現事件的發佈與訂閱。通過有序的消息處理,確保事件得到妥善處理。簡化您的代碼,提升系統可維護性。 ...
  • 一、基本的.NET框架概念 .NET框架是一個由微軟開發的軟體開發平臺,它提供了一個運行時環境(CLR - Common Language Runtime)和一套豐富的類庫(FCL - Framework Class Library)。CLR負責管理代碼的執行,而FCL則提供了大量預先編寫好的代碼, ...
  • 本章將和大家分享在ASP.NET Core中如何使用高級客戶端NEST來操作我們的Elasticsearch。 NEST是一個高級別的Elasticsearch .NET客戶端,它仍然非常接近原始Elasticsearch API的映射。所有的請求和響應都是通過類型來暴露的,這使得它非常適合快速上手 ...
  • 參考delphi的代碼更改為C# Delphi 檢測密碼強度 規則(仿 google) 仿 google 評分規則 一、密碼長度: 5 分: 小於等於 4 個字元 10 分: 5 到 7 字元 25 分: 大於等於 8 個字元 二、字母: 0 分: 沒有字母 10 分: 全都是小(大)寫字母 20 ...