文章目錄

• 1、背景
• 2、算法
• • 2.1 分布存儲之哈希取余算法
  • 2.2 分布式存儲之一致性哈希算法
  • 2.3 分布式存儲之哈希槽算法

成都創(chuàng)新互聯(lián)公司于2013年開始，是專業(yè)互聯(lián)網技術服務公司，擁有項目成都網站設計、成都網站建設網站策劃，項目實施與項目整合能力。我們以讓每一個夢想脫穎而出為使命，1280元華陰做網站,已為上家服務,為華陰各地企業(yè)和個人服務,聯(lián)系電話:135182197921、背景

一個經典的面試題目：1～2億條數據需要緩存，請問如何設計這個方案？
回答：單臺單機肯定不可能，需要使用分布存儲

2、算法 2.1 分布存儲之哈希取余算法- 2億條記錄就是2億個k，v，我們單機不行必須要分布式多機，假設有3臺機器構成一個集群，用戶每次讀寫操作都是根據公式：Hash(key) % N個機器臺數，計算出哈希值，用來決定數據映射到哪一個節(jié)點上。 - 優(yōu)點：簡單粗暴，直接有效，只需要預估好數據規(guī)劃好節(jié)點，例如3臺、8臺、10臺，就能保證一段時間的數據支撐。使用Hash算法讓固定的一部分請求落到同一臺服務器上，這樣每臺服務器固定處理一部分請求(并維護這些請求的信息)，起到負載均衡+分而治之的作用。 - 缺點：原來規(guī)劃好的節(jié)點，進行擴容和縮容就比較麻煩了，不管擴縮，每次數據變動導致節(jié)點有變動，映射關系需要重新進行計算，在服務器個數固定不變的時沒有問題，如果需要彈性擴容或故障停機的情況下，原來的取模公式就會發(fā)生變化：Hash(key)/3會變成Hash(key)/?。此時地址經過某個redis機器宕機了，由于臺數數量變化，會導致hash取余全部數據重新洗牌。 2.2 分布式存儲之一致性哈希算法

• 是什么？
  一致性哈希算法背景是在1997年由麻省理工學院提出的，設計目標是為了解決分布式存儲數據變動和映射問題，某個機器宕機了，分母數量改變了，自然取余數就不OK了。
• 能干嘛？
  提出一致性hash算法解決方案目的就是當服務器個數發(fā)生變動時，盡量減少影響客戶端到服務器的映射關系。
• 3大步驟??
  • 算法構建一致性哈希環(huán)
    一致性hash算法必然有個hash函數并按照算法產生hash值，這個算法的所有可能哈希值會構成一個全量集，這個集合可以成為一個hash空間[0,2^32-1],這是一個線性空間，但是在算法中，我們通過適當的邏輯將它首尾相連，這樣讓他構成一個環(huán)形空間。它也是按照使用取模的方法，前面筆記介紹的節(jié)點取模法是對節(jié)點(服務器)的數量進行取模。而一致性Hash算法是對2^32取模,簡單來說，一致性Hash算法將整個哈希值空間組織成一個虛擬的圓環(huán)，如假設某哈希函數H的值空間為0~2^32-1（即哈希值是一個32位無符號整型），整個哈希環(huán)如下圖：整個空間按順時針方向組織，圓環(huán)的正上方的點代表0，0點右側的第一個點代表1，以此類推，2、3、4…直到2^{32-1，也就是0點左側的第一個點代表2}32-1，0和2^{32-1在零點中方向重合，我們把這個由2}32個點組成的圓環(huán)稱為Hash環(huán)。

• 服務器IP節(jié)點映射
  將集群中各個IP映射到環(huán)上的某一個某一位置。將各個服務器使用Hash進行一個哈希，具體可以選擇服務器的IP或主機名作為關鍵字進行哈希，這樣每一臺機器就能確定其在哈希環(huán)上的位置。假如4個結點NodeA、B、C、D，經過IP地址的哈希函數計算(hash(ip)),使用IP地址哈希后在環(huán)空間的位置如下：

2.3 分布式存儲之哈希槽算法

• 是什么？
  哈希槽實質就是一個數組，數組[0,2^14-1]形成hash slot空間
• 能干什么？
  解決均勻分配的問題，在數據和節(jié)點之間又加入了一層，把這層稱為哈希槽（slot）,用于管理數據和節(jié)點之間的關系，現(xiàn)在就相當于節(jié)點上放的是槽，槽里放的是數據。槽解決的是粒度問題，相當于把粒度變大，這樣便于數據移動。哈希解決的是映射問題，使用key的哈希值來計算所在的槽，便于數據分配。
• 有多少個hash槽？
  一個集群只能有16384個槽，編號0-16383。這些槽會分配給集群中的所有主節(jié)點，分配策略沒有要求?？梢灾付男┚幪柕牟鄯峙浣o哪些主節(jié)點。集群會記錄節(jié)點和槽的對應關系。解決了節(jié)點和槽的關系后，接下來就需要對key求哈希值，然后對16384取余，余數是幾key就落入對應的槽里。slot=CRC16(key)%16384。以槽為單位移動數據，因為槽的數目是固定的，處理起來比較容器，這樣數據移動問題就解決了。
  

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

網站名稱：3大經典分布式存儲算法-創(chuàng)新互聯(lián)
文章位置：http://www.weahome.cn/article/cdcoih.html