【golang】分散式緩存 - 一致性哈希演算法

来源:https://www.cnblogs.com/freeyw/archive/2022/08/05/16554169.html
-Advertisement-
Play Games

前言 之前也瞭解到過一致性哈希演算法,但是沒有用go實現過,剛好最近看GeeCache,動手實現下一致性哈希演算法 正文: 我們先來想下一致性哈希演算法的數據結構含有哪些內容: 1.map 用來存儲虛擬節點對應的真實節點,是一個映射表 2.hash 哈希函數 3.key 哈希環,存儲所有虛擬節點 4.re ...


前言

  之前也瞭解到過一致性哈希演算法,但是沒有用go實現過,剛好最近看GeeCache,動手實現下一致性哈希演算法

正文:

  我們先來想下一致性哈希演算法的數據結構含有哪些內容:

  1.map 用來存儲虛擬節點對應的真實節點,是一個映射表

  2.hash 哈希函數

  3.key 哈希環,存儲所有虛擬節點

  4.replicas 虛擬節點的倍數

瞭解過一致性哈希演算法的朋友,應該是能夠理解為什麼要有上面的內容,下麵我們用代碼實現下:

type Hash func([]byte) uint32
type Map struct {
    hash    Hash  // hash演算法
    key     []int // hash環
    replicas int  // 虛擬節點的數量
    m      map[int]string // 虛擬節點和真實節點的映射表
}

下麵,我們實現獲取節點的方法:

  將key經過hash運算,在哈希環上順時針找到第一個節點,存入

func (m *Map) Get(key string) string {
    hash := int(m.hash([]byte(key)))  // 獲取key對應的hash值
//    順時針找到第一個虛擬節點
    idx := sort.Search(len(m.key), func(i int) bool {
        return m.key[i] >= hash
    })
//    返回對應的真實節點:記得對哈希環取餘
    return m.m[m.key[idx % len(m.key)]]
}

添加節點的方法

func (m *Map) Add(key ...string)  {
    for _,realKey := range key{
        for i := 0; i < m.replicas; i++ {
        //    真實節點對應的虛擬節點
            hash := int(m.hash([]byte(strconv.Itoa(i)+realKey)))
        //    添加到換上
            m.key = append(m.key,hash)
        //    添加到映射表上
            m.m[hash] = realKey
        }
    }
    // 遞增排序,方便順時針查找
    sort.Ints(m.key)
}

以上就是一致性哈希的實現方法,也挺好理解的。記錄下~

| 不驕不躁,保持學習


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

-Advertisement-
Play Games
更多相關文章
  • 單元測試JUnit 單元測試的目的是針對方法進行測試, **JUnit的兩個要點:**①必須是公開的,無參數,無返回值的方法 ②測試方法必須使用@Test註解標記 public class JUnitTest { @Test public void Testusername() { way way ...
  • 目錄 一.簡介 二.效果演示 三.源碼下載 四.猜你喜歡 零基礎 OpenGL (ES) 學習路線推薦 : OpenGL (ES) 學習目錄 >> OpenGL ES 基礎 零基礎 OpenGL (ES) 學習路線推薦 : OpenGL (ES) 學習目錄 >> OpenGL ES 轉場 零基礎 O ...
  • 多線程併發 在多核CPU中,利用多線程併發編程,可以更加充分地利用每個核的資源 在Java中,一個應用程式對應著一個JVM實例(也有地方稱為JVM進程),如果程式沒有主動創建線程,則只會創建一個主線程。但這不代表JVM中只有一個線程,JVM實例在創建的時候,同時會創建很多其他的線程(比如垃圾收集器線 ...
  • Java多線程(三) 五、線程的通信 5.1 wait() 與 notify() 和 notifyAll() 介紹: wait():令當前線程掛起並放棄CPU、同步資源並等待,使別的線程可訪問並修改共用資源,而當前線程排隊等候其他線程調用notify() 或 notifyAll() 方法喚醒,喚醒後 ...
  • (目錄) turtle庫的介紹 turtle庫也叫海龜庫,1969年誕生,是turtle繪圖體系的Python實現。turtle庫是Python語言的標準庫之一,是入門級的圖形繪製函數庫。 turtle庫的使用 方法一:import turtle 這種方法在之後每次引用turtle庫裡面的函數都需要 ...
  • Java多線程(二) 四、線程的同步 4.1 線程同步的引入: 多線程出現了安全問題。 問題的原因: 當多條語句在操作同一個線程共用數據時,一個線程對多條語句只執行了一部分,還沒有執行完,另一個線程參與進來執行。導致共用數據的錯誤。例如:買票問題、銀行卡消費問題等等。 解決辦法: 對多條操作共用數據 ...
  • 一、 編碼規約 1.1 標簽 (1)【強制】PHP 程式可以使用或來界定 PHP 代碼,在 HTML 頁面中嵌入純變數時,可以使用這樣的形式,不可使用其他的標簽變種。 正例: <?php /** * 編碼規約 * Created by PhpStorm. * User: [email protected] ...
  • 在SpringBoot中配置 Druid 數據源及密碼加密的方法 前文集成 MyBatis Plus,實現了一組增刪改查介面。在啟動服務時,從控制臺中可以看出 Spring Boot 預設使用 Hikari 作為資料庫連接池,Hikari性能很優秀。在國內使用較多的連接池還屬阿裡開源的 Druid, ...
一周排行
    -Advertisement-
    Play Games
  • 使用原因: 在我們服務端調用第三方介面時,如:支付寶,微信支付,我們服務端需要模擬http請求並加上一些自己的邏輯響應給前端最終達到我們想要的效果 1.使用WebClient 引用命名空間 using System.Net; using System.Collections.Specialized; ...
  • WPF 實現帶蒙版的 MessageBox 消息提示框 WPF 實現帶蒙版的 MessageBox 消息提示框 作者:WPFDevelopersOrg 原文鏈接: https://github.com/WPFDevelopersOrg/WPFDevelopers.Minimal 框架使用大於等於.N ...
  • 一、JSON(JavaScript Object Notation)的簡介: ① JSON和XML類似,主要用於存儲和傳輸文本信息,但是和XML相比,JSON更小、更快、更易解析、更易編寫與閱讀。 ② C、Python、C++、Java、PHP、Go等編程語言都支持JSON。 二、JSON語法規則: ...
  • 1.避免Scoped模式註冊的服務變成Singleton模式 當提供一個生命周期模式為Singleton的服務實例時,如果發現該服務中還依賴生命周期模式為Scoped的服務實例(Scoped服務實例將被一個Singleton服務實例所引用),那麼這個被依賴的Scoped服務實例最終會成為一個Sing ...
  • 索引時資料庫提高數據查詢處理性能的一個非常關鍵的技術,索引的使用可以對性能產生上百倍甚至上千倍的影響。接下來,會介紹索引的基本原理、概念,並深入學習資料庫中所使用的索引結構和存儲方式,以及如何管理、維護索引等。 1.索引的基本概念 索引時用來快速查詢表記錄的一種存儲結構,一般使用索引有一下兩個方面: ...
  • django2 路由控制器 Route路由,是一種映射關係。路由是把客戶端請求的url路徑和用戶請求的應用程式,這裡意指django裡面的視圖進行綁定映射的一種關係。 請求路徑和視圖函數不是一一對應的關係 在django中所有的路由最終都被保存到一個叫urlpatterns的文件里,並且該文件必須在 ...
  • 1、我們的目標是獲取微博某博主的全部圖片、視頻 2、拿到網址後 我們先觀察 打開F12 隨著下滑我們發現載入出來了一個叫mymblog的東西,展開響應發現需要的東西就在裡面 3、重點來了!!! 通過觀察發現第二頁比第一頁多了參數since_id 而第二頁的since_id參數剛好在上一頁中能獲取到, ...
  • 一、實現原理 在Servlet3協議規範中,包含在JAR文件/META-INFO/resources/路徑下的資源可以直接訪問。 二、舉例說明 如下圖所示,是我新建的一個Spring Boot Starter項目:zimug-minitor-threadpool,用於實現可配置、可觀測的線程池。其中 ...
  • 精華筆記: static final常量:應用率高 必須聲明同時初始化 由類名打點來訪問,不能被改變 建議:常量所有字母都大寫,多個單詞用_分隔 編譯器在編譯時會將常量直接替換為具體的數,效率高 何時用:數據永遠不變,並且經常使用 抽象方法: 由abstract修飾 只有方法的定義,沒有具體的實現( ...
  • Python有一個for...else語法,它的寫法如下 for i in range(0,100): if i == 3: break else: print("Not found") 該語句表示:若for迴圈遍歷完畢,則執行else部分的語句。也就是說上述代碼不會有任何輸出,而下述代碼會輸出“N ...