分布式緩存的演算法
❶ EhCache 分布式緩存/緩存集群
一 緩存系統簡介 EhCache 是一個純 java 的進程內緩存框架 具有快速 精乾等特點 是 Hibernate 中默認的 CacheProvider 鍵源 EhCache 應用架構圖 下圖是 EhCache 在應用程序中的位置
EhCache 的主要特性有 快速 精幹 簡單 多種緩存策略 緩存數據有兩級 內存和磁碟 因此無需擔心容量問題 緩存數據會在虛稿亮態擬機重啟的過程中寫入磁碟 可以通過 RMI 可插入 API 等方式進行分布式緩存 具有緩存和緩存管理器的偵聽介面 支持多緩存管理器實例 以及一個實例的多個緩存區域 提供 Hibernate 的緩存實現 由於 EhCache 是進程中的緩存系統 一旦將應用部署在集群環境中 每一個節點維護各自的緩存數據 當某個節點對緩存數據進行更新 這些更新的數據無法在其它節點 *** 享 這不僅會降低節點運行的效率 而且會導致數據不同步的情況發生 例如某個網站採用 A B 兩個節點作為集群部署 當 A 節點的緩存更新後 而 B 節點緩存尚未更新就可能出現用戶在瀏覽頁面的時候 一會是更新後的數據 一會是尚未更新的數據 盡管我們也可以通過 Session Sticky 技術來將用戶鎖定在某個節點上 但對於一些交互性比較強或者是非 Web 方式的系統來說 Session Sticky 顯然不太適合 所以就需要用到 EhCache 的集群解決方案 從 版本開始 Ehcache可以使用分布式的緩存了 EhCache 從 版本開始 支持五種集群方案 分別是 ? Terracotta ? RMI ? JMS ? JGroups ? EhCache Server 其中的三種最為常用集群方式 分別是 RMI JGroups 以及 EhCache Server 本文主要介紹RMI的方式 分布式這個特性是以plugin的方鍵殲式實現的 Ehcache自帶了一些默認的分布式緩存插件實現 這些插件可以滿足大部分應用的需要 如果需要使用其他的插件那就需要自己開發了 開發者可以通過查看distribution包里的源代碼及JavaDoc來實現它 盡管不是必須的 在使用分布式緩存時理解一些ehcahce的設計思想也是有幫助的 這可以參看分布式緩存設計的頁面 以下的部分將展示如何讓分布式插件同ehcache一起工作 下面列出的是一些分布式緩存中比較重要的方面 ? 你如何知道集群環境中的其他緩存？ ? 分布式傳送的消息是什麼形式？ ? 什麼情況需要進行復制？增加（Puts） 更新（Updates）或是失效（Expiries）？ ? 採用什麼方式進行復制？同步還是非同步方式？ 為了安裝分布式緩存 你需要配置一個PeerProvider 一個CacheManagerPeerListener 它們對於一個CacheManager來說是全局的 每個進行分布式操作的cache都要添加一個cacheEventListener來傳送消息
二 集群緩存概念及其配置 正確的元素類型 只有可序列化的元素可以進行復制 一些操作 比如移除 只需要元素的鍵值而不用整個元素 在這樣的操作中即使元素不是可序列化的但鍵值是可序列化的也可以被復制 成員發現（Peer Discovery） Ehcache進行集群的時候有一個cache組的概念 每個cache都是其他cache的一個peer 沒有主cache的存在 剛才我們問了一個問題 你如何知道集群環境中的其他緩存？這個問題可以命名為成員發現（Peer Discovery） Ehcache提供了兩種機制用來進行成員發現 就像一輛汽車 手動檔和自動檔 要使用一個內置的成員發現機制要在ehcache的配置文件中指定元素的class屬性為 net sf ehcache distribution 自動的成員發現 自動的發現方式用TCP廣播機制來確定和維持一個廣播組 它只需要一個簡單的配置可以自動的在組中添加和移除成員 在集群中也不需要什麼優化伺服器的知識 這是默認推薦的 成員每秒向群組發送一個 心跳 如果一個成員 秒種都沒有發出信號它將被群組移除 如果一個新的成員發送了一個 心跳 它將被添加進群組 任何一個用這個配置安裝了復制功能的cache都將被其他的成員發現並標識為可用狀態 要設置自動的成員發現 需要指定ehcache配置文件中元素的properties屬性 就像下面這樣 peerDiscovery=automatic multicastGroupAddress=multicast address | multicast host name multicastGroupPort=port timeToLive= （timeToLive屬性詳見常見問題部分的描述） 示例 假設你在集群中有兩台伺服器 你希望同步sampleCache 和sampleCache 每台獨立的伺服器都要有這樣的配置 配置server 和server <class= net sf ehcache distribution properties= peerDiscovery=automatic multicastGroupAddress= />multicastGroupPort= timeToLive= 手動進行成員發現 進行手動成員配置要知道每個監聽器的IP地址和埠 成員不能在運行時動態地添加和移除 在技術上很難使用廣播的情況下就可以手動成員發現 例如在集群的伺服器之間有一個不能傳送廣播報文的路由器 你也可以用手動成員發現進行單向的數據復制 只讓server 知道server 而server 不知道server 配置手動成員發現 需要指定ehcache配置文件中的properties屬性 像下面這樣 peerDiscovery=manual rmiUrls=//server:port/cacheName //server:port/cacheName … rmiUrls配置的是伺服器cache peers的列表 注意不要重復配置 示例 假設你在集群中有兩台伺服器 你要同步sampleCache 和sampleCache 下面是每個伺服器需要的配置 配置server <class= net sf ehcache distribution properties= peerDiscovery=manual />rmiUrls=//server : /sampleCache |//server : /sampleCache 配置server <class= net sf ehcache distribution properties= peerDiscovery=manual />rmiUrls=//server : /sampleCache |//server : /sampleCache 配置CacheManagerPeerListener 每個CacheManagerPeerListener監聽從成員們發向當前CacheManager的消息 配置CacheManagerPeerListener需要指定一個 它以插件的機制實現 用來創建CacheManagerPeerListener 的屬性有 class – 一個完整的工廠類名 properties – 只對這個工廠有意義的屬性 使用逗號分隔 Ehcache有一個內置的基於RMI的分布系統 它的監聽器是RMICacheManagerPeerListener 這個監聽器可以用 RMI來配置 <class= net sf ehcache distribution RMI properties= hostName=localhost port= />socketTimeoutMillis= 有效的屬性是 hostname （可選） – 運行監聽器的伺服器名稱 標明了做為集群群組的成員的地址 同時也是你想要控制的從集群中接收消息的介面在CacheManager初始化的時候會檢查hostname是否可用 如果hostName不可用 CacheManager將拒絕啟動並拋出一個連接被拒絕的異常 如果指定 hostname將使用InetAddress getLocalHost（） getHostAddress（）來得到 警告 不要將localhost配置為本地地址 因為它在網路中不可見將會導致不能從遠程伺服器接收信息從而不能復制 在同一台機器上有多個CacheManager的時候 你應該只用localhost來配置 port – 監聽器監聽的埠 socketTimeoutMillis （可選） – Socket超時的時間 默認是 ms 當你socket同步緩存請求地址比較遠 不是本地區域網 你可能需要把這個時間配置大些 不然很可能延時導致同步緩存失敗 配置CacheReplicators 每個要進行同步的cache都需要設置一個用來向CacheManagerr的成員復制消息的緩存事件監聽器 這個工作要通過為每個cache的配置增加一個cacheEventListenerFactory元素來完成 <! Sample cache named sampleCache ><cache name= sampleCache maxElementsInMemory= eternal= false timeToIdleSeconds= timeToLiveSeconds= overflowToDisk= false ><cacheEventListenerFactory class= net sf ehcache distribution RMICacheReplicatorFactory properties= replicateAsynchronously=true replicatePuts=true replicateUpdates=true replicateUpdatesViaCopy=false replicateRemovals=true /></cache>class – 使用net sf ehcache distribution RMICacheReplicatorFactory 這個工廠支持以下屬性 replicatePuts=true | false – 當一個新元素增加到緩存中的時候是否要復制到其他的peers 默認是true replicateUpdates=true | false – 當一個已經在緩存中存在的元素被覆蓋時是否要進行復制 默認是true replicateRemovals= true | false – 當元素移除的時候是否進行復制 默認是true replicateAsynchronously=true | false – 復制方式是非同步的（指定為true時）還是同步的（指定為false時） 默認是true replicatePutsViaCopy=true | false – 當一個新增元素被拷貝到其他的cache中時是否進行復制指定為true時為復制 默認是true replicateUpdatesViaCopy=true | false – 當一個元素被拷貝到其他的cache中時是否進行復制（指定為true時為復制） 默認是true 你可以使用ehcache的默認行為從而減少配置的工作量 默認的行為是以非同步的方式復制每件事 你可以像下面的例子一樣減少RMICacheReplicatorFactory的屬性配置 <! Sample cache named sampleCache All missing RMICacheReplicatorFactory properties default to true ><cache name= sampleCache maxElementsInMemory= eternal= true overflowToDisk= false memoryStoreEvictionPolicy= LFU ><cacheEventListenerFactory class= net sf ehcache distribution RMICacheReplicatorFactory /></cache> 常見的問題 Windows上的Tomcat 有一個Tomcat或者是JDK的bug 在tomcat啟動時如果tomcat的安裝路徑中有空格的話 在啟動時RMI監聽器會失敗 參見 bin/wa?A =ind &L=rmi users&P= 和 doc/faq howto bugs/l 由於在Windows上安裝Tomcat默認是裝在 Program Files 文件夾里的 所以這個問題經常發生 廣播阻斷 自動的peer discovery與廣播息息相關 廣播可能被路由阻攔 像Xen和VMWare這種虛擬化的技術也可以阻攔廣播 如果這些都打開了 你可能還在要將你的網卡的相關配置打開 一個簡單的辦法可以告訴廣播是否有效 那就是使用ehcache remote debugger來看 心跳 是否可用 廣播傳播的不夠遠或是傳得太遠 你可以通過設置badly misnamed time to live來控制廣播傳播的距離 用廣播IP協議時 timeToLive的值指的是數據包可以傳遞的域或是范圍 約定如下 是限制在同一個伺服器 是限制在同一個子網 是限制在同一個網站 是限制在同一個region 是限制在同一個大洲 是不限制 譯者按 上面這些資料翻譯的不夠准確 請讀者自行尋找原文理解吧 在Java實現中默認值是 也就是在同一個子網中傳播 改變timeToLive屬性可以限制或是擴展傳播的范圍
三 RMI方式緩存集群/配置分布式緩存 RMI 是 Java 的一種遠程方法調用技術 是一種點對點的基於 Java 對象的通訊方式 EhCache 從 版本開始就支持 RMI 方式的緩存集群 在集群環境中 EhCache 所有緩存對象的鍵和值都必須是可序列化的 也就是必須實現 java io Serializable 介面 這點在其它集群方式下也是需要遵守的 下圖是 RMI 集群模式的結構圖
採用 RMI 集群模式時 集群中的每個節點都是對等關系 並不存在主節點或者從節點的概念 因此節點間必須有一個機制能夠互相認識對方 必須知道其它節點的信息 包括主機地址 埠號等 EhCache 提供兩種節點的發現方式 手工配置和自動發現 手工配置方式要求在每個節點中配置其它所有節點的連接信息 一旦集群中的節點發生變化時 需要對緩存進行重新配置 由於 RMI 是 Java 中內置支持的技術 因此使用 RMI 集群模式時 無需引入其它的 Jar 包 EhCache 本身就帶有支持 RMI 集群的功能 使用 RMI 集群模式需要在 ehcache xml 配置文件中定義 節點 分布式同步緩存要讓這邊的cache知道對方的cache 叫做Peer Discovery（成員發現） EHCache實現成員發現的方式有兩種 手動查找 A 在ehcache xml中配置PeerDiscovery成員發現對象 Server 配置 配置本地hostName port是 分別監聽 : 的mobileCache和 : 的mobileCache 注意這里的mobileCache是緩存的名稱 分別對應著server server 的cache的配置 <?xml version= encoding= gbk ?><ehcache xmlns:xsi= instance xsi:noNamespaceSchemaLocation= ehcache xsd > <diskStore path= java io tmpdir /> <! 集群多台伺服器中的緩存 這里是要同步一些伺服器的緩存 server hostName: port: cacheName:mobileCache server hostName: port: cacheName:mobileCache server hostName: port: cacheName:mobileCache 注意 每台要同步緩存的伺服器的RMI通信socket埠都不一樣 在配置的時候注意設置 > <! server 的配置 > < class= net sf ehcache distribution properties= hostName=localhost port= socketTimeoutMillis= peerDiscovery=manual rmiUrls=// : /mobileCache|// : /mobileCache /></ehcache>以上注意元素出現的位置在diskStore下
同樣在你的另外 台伺服器上增加配置 Server 配置本地host port為 分別同步 : 的mobileCache和 : 的mobileCache <! server 的配置 >< class= net sf ehcache distribution properties= hostName=localhost port= socketTimeoutMillis= peerDiscovery=manual rmiUrls=// : /mobileCache|// : /mobileCache />Server 配置本地host port為 分別同步 : 的mobileCache緩存和 : 的mobileCache緩存 <! server 的配置 >< class= net sf ehcache distribution properties= hostName=localhost port= socketTimeoutMillis= peerDiscovery=manual rmiUrls=// : /mobileCache|// : /mobileCache />這樣就在三台不同的伺服器上配置了手動查找cache的PeerProvider成員發現的配置了 值得注意的是你在配置rmiUrls的時候要特別注意url不能重復出現 並且埠 地址都是對的 如果指定 hostname將使用InetAddress getLocalHost（） getHostAddress（）來得到 警告 不要將localhost配置為本地地址 因為它在網路中不可見將會導致不能從遠程伺服器接收信息從而不能復制 在同一台機器上有多個CacheManager的時候 你應該只用localhost來配置 B 下面配置緩存和緩存同步監聽 需要在每台伺服器中的ehcache xml文件中增加cache配置和cacheEventListenerFactory cacheLoaderFactory的配置 <defaultCache maxElementsInMemory= eternal= false timeToIdleSeconds= timeToLiveSeconds= overflowToDisk= false /><! 配置自定義緩存 maxElementsInMemory:緩存中允許創建的最大對象數 eternal:緩存中對象是否為永久的 如果是 超時設置將被忽略 對象從不過期 timeToIdleSeconds:緩存數據空閑的最大時間 也就是說如果有一個緩存有多久沒有被訪問就會被銷毀 如果該值是 就意味著元素可以停頓無窮長的時間 timeToLiveSeconds:緩存數據存活的時間 緩存對象最大的的存活時間 超過這個時間就會被銷毀 這只能在元素不是永久駐留時有效 如果該值是 就意味著元素可以停頓無窮長的時間 overflowToDisk:內存不足時 是否啟用磁碟緩存 memoryStoreEvictionPolicy:緩存滿了之後的淘汰演算法 每一個小時更新一次緩存（ 小時過期） ><cache name= mobileCache maxElementsInMemory= eternal= false overflowToDisk= true timeToIdleSeconds= timeToLiveSeconds= memoryStoreEvictionPolicy= LFU > <! RMI緩存分布同步查找 class使用net sf ehcache distribution RMICacheReplicatorFactory 這個工廠支持以下屬性 replicatePuts=true | false – 當一個新元素增加到緩存中的時候是否要復制到其他的peers 默認是true replicateUpdates=true | false – 當一個已經在緩存中存在的元素被覆蓋時是否要進行復制 默認是true replicateRemovals= true | false – 當元素移除的時候是否進行復制 默認是true replicateAsynchronously=true | false – 復制方式是非同步的 指定為true時 還是同步的 指定為false時 默認是true replicatePutsViaCopy=true | false – 當一個新增元素被拷貝到其他的cache中時是否進行復制 指定為true時為復制 默認是true replicateUpdatesViaCopy=true | false – 當一個元素被拷貝到其他的cache中時是否進行復制 指定為true時為復制 默認是true = > <! 監聽RMI同步緩存對象配置 注冊相應的的緩存監聽類 用於處理緩存事件 如put remove update 和expire > <cacheEventListenerFactory class= net sf ehcache distribution RMICacheReplicatorFactory properties= replicateAsynchronously=true /> replicatePuts=true replicateUpdates=true replicateUpdatesViaCopy=false replicateRemovals=true <! 用於在初始化緩存 以及自動設置 > <bootstrapCacheLoaderFactory class= net sf ehcache bootstrap BootstrapCacheLoaderFactory /></cache> C 這樣就完成了 台伺服器的配置 下面給出server 的完整的ehcache xml的配置 <?xml version= encoding= gbk ?><ehcache xmlns:xsi= instance xsi:noNamespaceSchemaLocation= ehcache xsd > <diskStore path= java io tmpdir /> <!集群多台伺服器中的緩存 這里是要同步一些伺服器的緩存 server hostName: port: cacheName:mobileCache server hostName: port: cacheName:mobileCache server hostName: port: cacheName:mobileCache 注意每台要同步緩存的伺服器的RMI通信socket埠都不一樣 在配置的時候注意設置 > <! server 的配置 > < class= net sf ehcache distribution properties= hostName=localhost port= socketTimeoutMillis= peerDiscovery=manual rmiUrls=// : /mobileCache|// : /mobileCache /> <defaultCache maxElementsInMemory= eternal= false timeToIdleSeconds= timeToLiveSeconds= overflowToDisk= false /> <! 配置自定義緩存 maxElementsInMemory:緩存中允許創建的最大對象數 eternal:緩存中對象是否為永久的 如果是 超時設置將被忽略 對象從不過期 timeToIdleSeconds:緩存數據空閑的最大時間 也就是說如果有一個緩存有多久沒有被訪問就會被銷毀 如果該值是 就意味著元素可以停頓無窮長的時間 timeToLiveSeconds:緩存數據存活的時間 緩存對象最大的的存活時間 超過這個時間就會被銷毀 這只能在元素不是永久駐留時有效 如果該值是 就意味著元素可以停頓無窮長的時間 overflowToDisk:內存不足時 是否啟用磁碟緩存 memoryStoreEvictionPolicy:緩存滿了之後的淘汰演算法 每一個小時更新一次緩存（ 小時過期） > <cache name= mobileCache maxElementsInMemory= eternal= false overflowToDisk= true timeToIdleSeconds= timeToLiveSeconds= memoryStoreEvictionPolicy= LFU > <! RMI緩存分布同步查找 class使用net sf ehcache distribution RMICacheReplicatorFactory 這個工廠支持以下屬性 replicatePuts=true | false – 當一個新元素增加到緩存中的時候是否要復制到其他的peers 默認是true replicateUpdates=true | false – 當一個已經在緩存中存在的元素被覆蓋時是否要進行復制 默認是true replicateRemovals= true | false – 當元素移除的時候是否進行復制 默認是true replicateAsynchronously=true | false – 復制方式是非同步的 指定為true時 還是同步的 指定為false時 默認是true replicatePutsViaCopy=true | false – 當一個新增元素被拷貝到其他的cache中時是否進行復制 指定為true時為復制 默認是true replicateUpdatesViaCopy=true | false – 當一個元素被拷貝到其他的cache中時是否進行復制 指定為true時為復制 默認是true = > <! 監聽RMI同步緩存對象配置 注冊相應的的緩存監聽類 用於處理緩存事件 如put remove update 和expire > <cacheEventListenerFactory class= net sf ehcache distribution RMICacheReplicatorFactory properties= replicateAsynchronously=true /> replicatePuts=true replicateUpdates=true replicateUpdatesViaCopy=false replicateRemovals=true <! 用於在初始化緩存 以及自動設置 > <bootstrapCacheLoaderFactory class= net sf ehcache bootstrap BootstrapCacheLoaderFactory /> </cache></ehcache> 自動發現 自動發現配置和手動查找的方式有一點不同 其他的地方都基本是一樣的 同樣在ehcache xml中增加配置 配置如下 <! 搜索某個網段上的緩存timeToLive 是限制在同一個伺服器 是限制在同一個子網 是限制在同一個網站 是限制在同一個region 是限制在同一個大洲 是不限制 >< class= net sf ehcache distribution properties= peerDiscovery=automatic multicastGroupAddress= multicastGroupPort= timeToLive= /> lishixin/Article/program/Java/hx/201311/25706
❷ Redis分布式緩存搭建
花了兩天時間整理了之前記錄的Redis單體與哨兵模式的搭建與使用，又補齊了集群模式的使用和搭建經驗，並對集群的一些個原理做了理解。
筆者安裝中遇到的一些問題：
如果make報錯，可能是沒裝gcc或者gcc++編輯器，安裝之 yum -y install gcc gcc-c++ kernel-devel ，有可能還是提示一些個c文件編譯不過，gcc -v查看下版本，如果不到5.3那麼升級一下gcc：
在 /etc/profile 追加一行 source /opt/rh/devtoolset-9/enable
scl enable devtoolset-9 bash
重新make clean, make
這回編譯通過了，提示讓你最好make test一下/
執行make test ，如果提示 You need tcl 8.5 or newer in order to run the Redis test
那就升級tcl， yum install tcl
重新make test，如果還有error就刪了目錄，重新tar包解壓重新make , make test
o/ All tests passed without errors! ，表示編譯成功。
然後make install即可。
直接運行命令： ./redis-server /usr/redis-6.0.3/redis.conf &
redis.conf 配置文件里 bind 0.0.0.0 設置外部訪問， requirepass xxxx 設置密碼。
redis高可用方案有兩種：
常用搭建方案為1主1從或1主2從+3哨兵監控主節點， 以及3主3從6節點集群。
（1）sentinel哨兵
/usr/redis-6.0.3/src/redis-sentinel /usr/redis-6.0.3/sentinel2.conf &
sentinel2.conf配置：
坑1：master節點也會在故障轉移後成為從節點，也需要配置masterauth
當kill master進程之後，經過sentinel選舉，slave成為了新的master，再次啟動原master，提示如下錯誤：
原因是此時的master再次啟動已經是slave了，需要向現在的新master輸入密碼，所以需要在master.conf
中配置：
坑2：哨兵配置文件要暴露客戶端可以訪問到的master地址
在 sentinel.conf 配置文件的 sentinel monitor mymaster 122.xx.xxx.xxx 6379 2 中，配置該哨兵對應的master名字、master地址和埠，以及達到多少個哨兵選舉通過認為master掛掉。其中master地址要站在redis訪問者（也就是客戶端）的角度、配置訪問者能訪問的地址，例如sentinel與master在一台伺服器（122.xx.xxx.xxx）上，那麼相對sentinel其master在本機也就是127.0.0.1上，這樣 sentinel monitor mymaster 127.0.0.1 6379 2 邏輯上沒有問題，但是如果另外伺服器上的springboot通過lettuce訪問這個redis哨兵，則得到的master地址為127.0.0.1，也就是springboot所在伺服器本機，這顯然就有問題了。
附springboot2.1 redis哨兵配置：
坑3：要注意配置文件.conf會被哨兵修改
redis-cli -h localhost -p 26379 ，可以登到sentinel上用info命令查看一下哨兵的信息。
曾經遇到過這樣一個問題，大致的信息如下
slaves莫名其妙多了一個，master的地址也明明改了真實對外的地址，這里又變成127.0.0.1 !
最後，把5個redis進程都停掉，逐個檢查配置文件，發現redis的配置文件在主從哨兵模式會被修改，master的配置文件最後邊莫名其妙多了一行replicaof 127.0.0.1 7001， 懷疑應該是之前配置錯誤的時候（見坑2）被哨兵動態加上去的！ 總之，實踐中一定要多注意配置文件的變化。
（2）集群
當數據量大到一定程度，比如幾十上百G，哨兵模式不夠用了需要做水平拆分，早些年是使用codis，twemproxy這些第三方中間件來做分片的，即 客戶端 -> 中間件 -> Redis server 這樣的模式，中間件使用一致性Hash演算法來確定key在哪個分片上。後來Redis官方提供了方案，大家就都採用官方的Redis Cluster方案了。
Redis Cluster從邏輯上分16384個hash slot，分片演算法是 CRC16(key) mod 16384 得到key應該對應哪個slot，據此判斷這個slot屬於哪個節點。
每個節點可以設置1或多個從節點，常用的是3主節點3從節點的方案。
reshard，重新分片，可以指定從哪幾個節點移動一些hash槽到另一個節點去。重新分片的過程對客戶端透明，不影響線上業務。
搭建Redis cluster
redis.conf文件關鍵的幾個配置：
啟動6個集群節點
[root@VM_0_11_centos redis-6.0.3]# ps -ef|grep redis
root 5508 1 0 21:25 ? 00:00:00 /usr/redis-6.0.3/src/redis-server 0.0.0.0:7001 [cluster]
root 6903 1 0 21:32 ? 00:00:00 /usr/redis-6.0.3/src/redis-server 0.0.0.0:7002 [cluster]
root 6939 1 0 21:33 ? 00:00:00 /usr/redis-6.0.3/src/redis-server 0.0.0.0:7003 [cluster]
root 6966 1 0 21:33 ? 00:00:00 /usr/redis-6.0.3/src/redis-server 0.0.0.0:7004 [cluster]
root 6993 1 0 21:33 ? 00:00:00 /usr/redis-6.0.3/src/redis-server 0.0.0.0:7005 [cluster]
root 7015 1 0 21:33 ? 00:00:00 /usr/redis-6.0.3/src/redis-server 0.0.0.0:7006 [cluster]
這時候這6個節點還是獨立的，要把他們配置成集群：
說明： -a xxxx 是因為筆者在redis.conf中配置了requirepass xxxx密碼，然後 --cluster-replicas 1 中的1表示每個master節點有1個從節點。
上述命令執行完以後會有一個詢問： Can I set the above configuration? yes同意自動做好的分片即可。
最後 All 16384 slots covered. 表示集群中16384個slot中的每一個都有至少有1個master節點在處理，集群啟動成功。
查看集群狀態：
坑1：暴露給客戶端的節點地址不對
使用lettuce連接發現連不上，查看日誌 Connection refused: no further information: /127.0.0.1:7002 ，跟之前哨兵配置文件sentinel.conf里邊配置master地址犯的錯誤一樣，集群啟動的時候帶的地址應該是提供給客戶端訪問的地址。
我們要重建集群：先把6個redis進程停掉，然後刪除 nodes-7001.conf 這些節點配置文件，刪除持久化文件 mp.rdb 、 appendonly.aof ，重新啟動6個進程，在重新建立集群：
然後，還是連不上，這次報錯 connection timed out: /172.xx.0.xx:7004 ，發現連到企鵝雲伺服器的內網地址上了！
解決辦法，修改每個節點的redis.conf配置文件，找到如下說明：
所以增加配置：
然後再重新構建集群，停進程、改配置、刪除節點文件和持久化文件、啟動進程、配置集群。。。再來一套（累死了）
重新使用Lettuce測試，這次終於連上了！
坑2：Lettuce客戶端在master節點故障時沒有自動切換到從節點
name這個key在7002上，kill這個進程模擬master下線，然後Lettuce一直重連。我們期望的是應該能自動切換到其slave 7006上去，如下圖：
重新啟動7002進程，
7006已成為新master，7002成為它的slave，然後Lettuce也能連接上了。
解決辦法，修改Lettuce的配置：
筆者用的是springboot 2.1 spring-boot-starter-data-redis 默認的Lettuce客戶端，當使用Redis cluster集群模式時，需要配置一下 RedisConnectionFactory 開啟自適應刷新來做故障轉移時的自動切換從節點進行連接。
重新測試：停掉master 7006，這次Lettuce可以正常切換連到7002slave上去了。（仍然會不斷的在日誌里報連接錯誤，因為需要一直嘗試重連7006，但因為有7002從節點頂上了、所以應用是可以正常使用的）
Redis不保證數據的強一致性
Redis並不保證數據的強一致性，也就是取CAP定理中的AP
關於一致性Hash演算法，可以參考 一致性Hash演算法 - (jianshu.com)
Redis cluster使用的是hash slot演算法，跟一致性Hash演算法不太一樣，固定16384個hash槽，然後計算key落在哪個slot里邊（計算key的CRC16值再對16384取模），key找的是slot而不是節點，而slot與節點的對應關系可以通過reshard改變並通過gossip協議擴散到集群中的每一個節點、進而可以為客戶端獲知，這樣key的節點定址就跟具體的節點個數沒關系了。也同樣解決了普通hash取模演算法當節點個數發生變化時，大量key對應的定址都發生改動導致緩存失效的問題。
比如集群增加了1個節點，這時候如果不做任何操作，那麼新增加的這個節點上是沒有slot的，所有slot都在原來的節點上且對應關系不變、所以沒有因為節點個數變動而緩存失效，當reshard一部分slot到新節點後，客戶端獲取到新遷移的這部分slot與新節點的對應關系、定址到新節點，而沒遷移的slot仍然定址到原來的節點。
關於熱遷移，猜想，內部應該是先做復制遷移，等遷移完了，再切換slot與節點的對應關系，復制沒有完成之前仍按照原來的slot與節點對應關系去原節點訪問。復制結束之後，再刪除原節點上已經遷移的slot所對應的key。
與哨兵模式比較類似，當1個節點發現某個master節點故障了、會對這個故障節點進行pfail主觀宕機，然後會通過gossip協議通知到集群中的其他節點、其他節點也執行判斷pfail並gossip擴散廣播這一過程，當超過半數節點pfail時那麼故障節點就是fail客觀宕機。接下來所有的master節點會在故障節點的從節點中選出一個新的主節點，此時所有的master節點中超過半數的都投票選舉了故障節點的某個從節點，那麼這個從節點當選新的master節點。
所有節點都持有元數據，節點之間通過gossip這種二進制協議進行通信、發送自己的元數據信息給其他節點、故障檢測、集群配置更新、故障轉移授權等等。
這種去中心化的分布式節點之間內部協調，包括故障識別、故障轉移、選主等等，核心在於gossip擴散協議，能夠支撐這樣的廣播協議在於所有的節點都持有一份完整的集群元數據，即所有的節點都知悉當前集群全局的情況。
Redis高可用方案 - (jianshu.com)
面試題:Redis 集群模式的工作原理能說一下么 - 雲+社區 - 騰訊雲 (tencent.com)
深度圖解Redis Cluster原理 - detectiveHLH - 博客園 (cnblogs.com)
Redis學習筆記之集群重啟和遇到的坑-阿里雲開發者社區 (aliyun.com)
雲伺服器Redis集群部署及客戶端通過公網IP連接問題
❸ lru演算法是什麼呢
LRU演算法是最少使用頁面置換演算法（Least Recently Used），首先置換近期最長時間以來沒被訪問的頁面，是為虛擬頁式存儲管理服務的。
LRU演算法的設計原則是：如果一個數據在最近一段時間沒有被訪問到，那麼在將來它被訪問的可能性也很小。也就是說，當限定的空間已存滿數據時，應當把最久沒有被訪問到的數據淘汰。
LRU原理
該思想最初用於計算機操作系統中，內存中的容量較有限，為了能更加合理的利用內存中的性能，對用戶的使用作出假設，最近最少使用的越不重要，最近使用的越有可能使用到，使得該元素更容易獲取到。
如果元素當前容量超過了內存最大容量，則需要刪除掉最近最少使用的元素。在其之後，許多緩存及許多分布式系統都採用才思想。
❹ JAVA幾種緩存技術介紹說明
1、TreeCache / JBossCache
JBossCache是一個復制的事務處理緩存，它允許你緩存企業級應用數據來更好的改善性能。緩存數據被自動復制，讓你輕松進行JBoss伺服器之間 的集群工作。JBossCache能夠通過JBoss應用服務或其他J2EE容器來運行一個MBean服務，當然，它也能獨立運行。
2、WhirlyCache
Whirlycache是一個快速的、可配置的、存在於內存中的對象的緩存。它能夠通過緩存對象來加快網站或應用程序的速度，否則就必須通過查詢資料庫或其他代價較高的處理程序來建立。
3、SwarmCache
SwarmCache是一個簡單且有效的分布式緩存，它使用IP multicast與同一個區域網的其他主機進行通訊，是特別為集群和數據驅動web應用程序而設計的。SwarmCache能夠讓典型的讀操作大大超過寫操作的這類應用提供更好的性能支持。
4、JCache
JCache是個開源程序，正在努力成為JSR-107開源規范，JSR-107規范已經很多年沒改變了。這個版本仍然是構建在最初的功能定義上。
5、ShiftOne
ShiftOne Java Object Cache是一個執行一系列嚴格的對象緩存策略的Java lib，就像一個輕量級的配置緩存工作狀態的框架。
❺ 科普一下，什麼是網站系統的性能，可用性，可伸縮性
性能(Performance)
性能是一個網站能夠同時處理用戶請求的表現能力。不同的視覺，有不同的表現形式，性能的指標通常包括，響應時間，並發數，吞吐量，以及性能計數器等。
其中吞吐量和性能計數器比較難理解一些，
吞吐量其實指的就是單位時間內，系統處理的請求數量。TPS（每秒的事務數），HPS（每秒的HTTP請求數），QPS（每秒的查詢數）等等。性能一般通過緩存來解決。
性能計數器，它描述的是伺服器或者操作系統的一組指標，包括，對象與線程數，內存使用，CPU使用，磁碟和網路的I/O等等。
提高網站的性能，很多的手段，比如，瀏覽器訪問優化，CDN加速，反向代理，分布式緩存，使用集群，代碼和數據結構的優化，存儲性能的優化等。可用性(Availability)
可用性是在某個考察時間，系統能夠正常運行的概率或時間佔有率期望值。考察時間為指定瞬間，則稱瞬時可用性；考察時間為指定時段，則稱時段可用性；考察時間為連續使用期間的任一時刻，則稱固有可用性。它是衡量設備在投入使用後實際使用的效能，是設備或系統的可靠性、可維護性和維護支持性的綜合特性。在大型網站應用系統中，衡量的指標一般是服務的可用性用幾個9來表示。
高可用性一般通過負載均衡，數據備份，失效轉移，提高軟體質量，特別是發布時的質量來實現和保證的。
可伸縮性（Scalability）
可伸縮性，是一種對軟體系統計算處理能力的設計指標，高可伸縮性代表一種彈性，在系統擴展成長過程中，軟體能夠保證旺盛的生命力，行扮滾通過很少的改動甚至只是硬體設備的添置，就能實現整個系統處理能力的線性增缺梁長，實現高吞吐量和低延遲高性能。
縱向的可伸縮性——在同一個邏輯單元內增加資源來提高處理能力。這樣的例子包括在現有伺服器上增加CPU，或者在現有的RAID/SAN存儲中增加硬碟來提高存儲量。
可伸縮性，一般通過DNS域名解析負載均衡，反向代理負載均衡，IP負載均衡，數據鏈路層負載均衡，改進和提高分布式緩存的演算法，利用NOSQL資料庫的可伸縮性等等。
可擴展性（Extensibility）
可擴展性，通常和可伸縮性混為一談.在軟體范疇上，是軟體系統本身的屬性，或者進一步說是設計的屬性，代碼的屬性。因為我們經常說設計的可擴展性，代碼的可擴展性.也可以說是系檔余統設計的松耦合性。
實現方式：一般通過事件驅動架構和分布式架構來實現一個網站系統的可擴展性。
❻ 分布式緩存中，哈希取余分區和一致性哈希分區有什麼區別
環割法（一致性 hash）環割法的原理如下：
1. 初始化的時候生成分片數量 X × 環割數量 N 的固定方式編號的字元串，例如 SHARD-1-NODE-1，並計算所有 X×N 個字元串的所有 hash 值。
2. 將所有計算出來的 hash 值放到一個排序的 Map 中，並將其中的所有元素進行排序。
3. 輸入字元串的時候計算輸入字元串的 hash 值，查看 hash 值介於哪兩個元素之間，取小於 hash 值的那個元素對應的分片為數據的分片。
數據比較
下面將通過測試對環割法和跳躍法的性能及均衡性進行對比，說明 DBLE 為何使用跳躍法代替了環割法。
數據源：現場數據 350595 條
測試經過：
1. 通過各自的測試方法執行對於測試數據的分片任務。
2. 測試方法侍嫌豎：記錄老大分片結果的方差；記錄從開始分片至分片結束的時間；記錄分片結果與平均數的最大差值。
3. 由於在求模法 PartitionByString 的方法中要求分片的數量是 1024 的因數，所以測試過程只能使用 2 的指數形式進行測試，並在 PartitionByString 方法進行測試的時候不對於 MAC 地址進行截斷，取全量長度進行測試。
❼ 常用的緩存技術
第一章 常用的緩存技術
1、常見的兩種緩存
本地緩存：不需要序列化，速度快，緩存的數量與大小受限於本機內存
分布式緩存：需要序列化，速度相較於本地緩存較慢，但是理論上緩存的數量與大小無限（因為緩存機器可以不斷擴展）
2、本地緩存
Google guava cache：當下最好用的本地緩存
Ehcache：spring默認集成的一個緩存，以spring cache的底層緩存實現類形式去操作緩存的話，非常方便，但是欠缺靈活，如果想要靈活使用，還是要單獨使用Ehcache
Oscache：最經典簡單的頁面緩存
3、分布式緩存
memcached：分布式緩存的標配
Redis：新一代的分布式緩存，有替代memcached的趨勢
3.1、memcached
經典的一致性hash演算法
基於slab的內存模型有效防止內存碎片的產生（但同時也需要估計好啟動參數，否則會浪費很多的內存）
集群中機器之間互不通信（相較於Jboss cache等集群中機器之間的相互通信的緩存，速度更快<--因為少了同步更新緩存的開銷，且更適合於大型分布式系統中使用）
使用方便（這一點是相較於Redis在構建客戶端的時候而言的，盡管redis的使用也不困難）
很專一（專做緩存，這一點也是相較於Redis而言的）
3.2、Redis
可以存儲復雜的數據結構（5種）
strings-->即簡單的key-value，就是memcached可以存儲的唯一的一種形式，接下來的四種是memcached不能直接存儲的四種格式（當然理論上可以先將下面的一些數據結構中的東西封裝成對象，然後存入memcached，但是不推薦將大對象存入memcached，因為memcached的單一value的最大存儲為1M，可能即使採用了壓縮演算法也不夠，即使夠，可能存取的效率也不高，而redis的value最大為1G）
hashs-->看做hashTable
lists-->看做LinkedList
sets-->看做hashSet，事實上底層是一個hashTable
sorted sets-->底層是一個skipList
有兩種方式可以對緩存數據進行持久化
RDB
AOF
事件調度
發布訂閱等
4、集成緩存
專指spring cache，spring cache自己繼承了ehcache作為了緩存的實現類，我們也可以使用guava cache、memcached、redis自己來實現spring cache的底層。當然，spring cache可以根據實現類來將緩存存在本地還是存在遠程機器上。
5、頁面緩存
在使用jsp的時候，我們會將一些復雜的頁面使用Oscache進行頁面緩存，使用非常簡單，就是幾個標簽的事兒；但是，現在一般的企業，前台都會使用velocity、freemaker這兩種模板引擎，本身速度就已經很快了，頁面緩存使用的也就很少了。
總結：
在實際生產中，我們通常會使用guava cache做本地緩存+redis做分布式緩存+spring cache就集成緩存（底層使用redis來實現）的形式
guava cache使用在更快的獲取緩存數據，同時緩存的數據量並不大的情況
spring cache集成緩存是為了簡單便捷的去使用緩存（以註解的方式即可），使用redis做其實現類是為了可以存更多的數據在機器上
redis緩存單獨使用是為了彌補spring cache集成緩存的不靈活
就我個人而言，如果需要使用分布式緩存，那麼首先redis是必選的，因為在實際開發中，我們會緩存各種各樣的數據類型，在使用了redis的同時，memcached就完全可以舍棄了，但是現在還有很多公司在同時使用memcached和redis兩種緩存。
❽ 分布式緩存是什麼
分布式緩存主要用於在高並發環境下，減輕資料庫的壓力，提高系統的響應速度和並發吞吐。當大量的讀、寫請求湧向資料庫時，磁碟的處理速度與內存顯然不在一個量級，因此，在資料庫之前加一層緩存，能夠顯著提高系統的響應速度，並降低資料庫的壓力。作為傳統的關系型資料庫，MySQL提供完整的ACID操作，支持豐富的數據類型、強大的關聯查詢、where語句等，能夠非常客易地建立查詢索引，執行復雜的內連接、外連接、求和、排序、分組等操作，並且支持存儲過程、函數等功能，產品成熟度高，功能強大。但是，對於需要應對高並發訪問並且存儲海量數據的場景來說，出於對性能的考慮，不得不放棄很多傳統關系型資料庫原本強大的功能，犧牲了系統的易用性，並且使得系統的設計和管理變得更為復雜。這也使得在過去幾年中，流行著另一種新的存儲解決方案——NoSQL，它與傳統的關系型資料庫最大的差別在於，它不使用SQL作為查詢語言來查找數據，而採用key-value形式進行查找，提供了更高的查詢效率及吞吐，並且能夠更加方便地進行擴展，存儲海量數據，在數千個節點上進行分區，自動進行數據的復制和備份。在分布式系統中，消息作為應用間通信的一種方式，得到了十分廣泛的應用。消息可以被保存在隊列中，直到被接收者取出，由於消息發送者不需要同步等待消息接收者的響應，消息的非同步接收降低了系統集成的耦合度，提升了分布式系統協作的效率，使得系統能夠更快地響應用戶，提供更高的吞吐。
當系統處於峰值壓力時，分布式消息隊列還能夠作為緩沖，削峰填谷，緩解集群的壓力，避免整個系統被壓垮。垂直化的搜索引擎在分布式系統中是一個非常重要的角色，它既能夠滿足用戶對於全文檢索、模糊匹配的需求，解決資料庫like查詢效率低下的問題，又能夠解決分布式環境下，由於採用分庫分表，或者使用NoSQL資料庫，導致無法進行多表關聯或者進行復雜查詢的問題。
❾ 什麼是分布式緩存
分布式緩存能夠處理大量的動態數據，因此比較適合應用在Web 2.0時代中的社交網站等需要由用戶生成內容的場景。從本地緩存擴展到分布式緩存後，關注重點從CPU、內存、緩存之間的數據傳輸速度差異也擴展到了業務系統、資料庫、分布式緩存之間的數據傳輸速度差異。
常用的分布式緩存包括Redis和Memcached。
Memcached
Memcached是一個高性能的分布式內存對象緩存系統，用於動態Web應用以減輕資料庫負載。Memcached通過在內存中緩存數據和對象來減少讀取資料庫的次數，從而提高動態、資料庫驅動網站的速度。
特點：哈希方式存儲；全內存操作；簡單文本協議進行數據通信；只操作字元型數據；集群由應用進行控制，採用一致性哈希演算法。
限制性：數據保存在內存當中的，一旦機器重啟，數據會全部丟失；只能操作字元型數據，數據類型貧乏；以root許可權運行，而且Memcached本身沒有任何許可權管理和認證功能，安全性不足；能存儲的數據長度有限，最大鍵長250個字元，儲存數據不能超過1M。
Redis
Redis是一個開源的使用ANSI C語言編寫、支持網路、可基於內存亦可持久化的日誌型、Key-Value資料庫，並提供多種語言的API。
特點：
Redis支持的數據類型包括：字元串、string、hash、set、sortedset、list；Redis實現持久化的方式：定期將內存快照寫入磁碟；寫日誌；Redis支持主從同步。
限制性：單核運行，在存儲大數據的時候性能會有降低；不是全內存操作；主從復制是全量復制，對實際的系統運營造成了一定負擔。
❿ 哈希表、哈希演算法、一致性哈希表
散列表（Hash table，也叫哈希表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。它通過把關鍵碼映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數（哈希函數），存放記錄的數組叫做散列表。
優點：
哈希表可以提供快速的操作。
缺點：
哈希表通常是基於數組的，數組創建後難於擴展。
也沒有一種簡便的方法可以以任何一種順序〔例如從小到大）遍歷表中的數據項 。
綜上， 如果不需要有序遍歷數據，井且可以提前預測數據量的大小。那麼哈希表在速度和易用性方面是無與倫比的。
1. 使用哈希函數將被查找的鍵轉換為數組的索引。
2. 處理哈希碰撞沖突。
若關鍵字為 k ，則其值存放在 f(k) 的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關系 f 為散列函數，按這個思想建立的表為散列表。
若對於關鍵字集合中的任一個關鍵字，經散列函數映象到地址集合中任何一個地址的概率是相等的，則稱此類散列函數為 均勻散列函數 (Uniform Hash function)，這就是使關鍵字經過散列函數得到一個"隨機的地址"，從而減少碰撞。
散列函數能使對一個數據序列的訪問過程更加迅速有效，通過散列函數，數據元素將被更快地定位。
一個好的散列函數一般應該考慮下列因素 ：
1.計算簡單，以便提高轉換速度。
2.關鍵詞對應的地址空間分布均勻，以盡量減少沖突。
1. 直接定址法
取關鍵字或者關鍵字的某個線性函數值作為哈希地址,即H(Key)=Key或者H(Key)=a*Key+b(a,b為整數),這種散列函數也叫做自身函數.如果H(Key)的哈希地址上已經有值了,那麼就往下一個位置找,直到找到H(Key)的位置沒有值了就把元素放進去。
2. 數字分析法
數字分析法就是找出數字的規律，盡可能利用這些數據來構造沖突幾率較低的散列地址。
3. 平方取中法
取關鍵字平方後的中間幾位作為散列地址。這種方法的原理是通過取平方擴大差別，平方值的中間幾位和這個數的每一位都相關，則對不同的關鍵字得到的哈希函數值不易產生沖突，由此產生的哈希地址也較為均勻。該方法適用於關鍵字中的每一位都有某些數字重復出現頻度很高的現象。
4. 折疊法
折疊法是將關鍵字分割成位數相同的幾部分,最後一部分位數可以不同,然後取這幾部分的疊加和(注意:疊加和時去除進位)作為散列地址。
數位疊加可以有移位疊加和間界疊加兩種方法。移位疊加是將分割後的每一部分的最低位對齊,然後相加;間界疊加是從一端向另一端沿分割界來回折疊,然後對齊相加。
該方法適用於關鍵字特別多的情況。
5. 隨機數法
選擇一個隨機數,作為散列地址,通常用於關鍵字長度不同的場合。
6. 除留余數法
取關鍵字被某個不大於散列表表長m的數p除後所得的余數為散列地址.即H(Key)=Key MOD p,p<=m.不僅可以對關鍵字直接取模,也可在折疊、平方取中等運算之後取模。對p的選擇很重要，一般取素數或m，若p選得不好，則很容易產生沖突。
對不同的關鍵字可能得到同一散列地址，即 k1≠k2 ，而 f(k1)=f(k2) ，這種現象稱為碰撞(英語:Collision)。具有相同函數值的關鍵字對該散列函數來說稱做同義詞。
通過構造性能良好的散列函數，可以減少沖突，但一般不可能完全避免沖突，因此解決沖突是哈希法的另一個關鍵問題。 創建哈希表和查找哈希表都會遇到沖突，兩種情況下解決沖突的方法應該一致。
下面以創建哈希表為例，說明解決沖突的方法。
1.開放定址法
這種方法也稱再散列法，其基本思想是：當關鍵字key的哈希地址p=H(key)出現沖突時，以p為基礎，產生另一個哈希地址p1，如果p1仍然沖突，再以p為基礎，產生另一個哈希地址p2，…，直到找出一個不沖突的哈希地址pi ，將相應元素存入其中。這種方法有一個通用的再散列函數形式：Hi=(H(key)+di)%m i=1，2，…，m-1,其中H（key）為哈希函數，m 為表長，di稱為增量序列，i為碰撞次數。增量序列的取值方式不同，相應的再散列方式也不同。增量序列主要有以下幾種：
(1) 線性探測再散列
di=1，2，3，…，m-1
這種方法的特點是：沖突發生時，順序查看錶中下一單元，直到找出一個空單元或查遍全表。
(2)二次探測再散列
di=12，-12，22，-22，…，k2，-k2( k<=m/2 )
這種方法的特點是：沖突發生時，在表的左右進行跳躍式探測，比較靈活。
(3)偽隨機探測再散列
di=偽隨機數序列。
線性探測再散列的 優點 是：只要哈希表不滿，就一定能找到一個不沖突的哈希地址，而二次探測再散列和偽隨機探測再散列則不一定。線性探測再散列容易產生「二次聚集」，即在處理同義詞的沖突時又導致非同義詞的沖突。
其實除了上面的幾種方法，開放定址法還有很多變種，不過都是對di有不同的表示方法。（如雙散列探測法：di=i*h2(k)）
2.再哈希法
這種方法是同時構造多個不同的哈希函數：Hi=RHi（key），i=1，2,3，…,n。
當哈希地址H1=RH1（key）發生沖突時，再計算H2=RH2（key）……，直到沖突不再產生。這種方法不易產生聚集，但增加了計算時間。
3.鏈地址法(拉鏈法)
這種方法的基本思想是將所有哈希地址相同的元素構成一個稱為同義詞鏈的單鏈表，並將單鏈表的頭指針存在哈希表（數組）中，因而查找、插入和刪除主要在同義詞鏈中進行。若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針組成的指針數組T[0..m-1]。凡是散列地址為i的結點，均插入到以T[i]為頭指針的單鏈表中。T中各分量的初值均應為空指針。鏈地址法適用於經常進行插入和刪除的情況。
拉鏈法的優點
與開放定址法相比，拉鏈法有如下幾個優點：
(1)拉鏈法處理沖突簡單，且無堆積現象，即非同義詞決不會發生沖突，因此平均查找長度較短；
(2)由於拉鏈法中各鏈表上的結點空間是動態申請的，故它更適合於造表前無法確定表長的情況；
(3)開放定址法為減少沖突，要求裝填因子α較小，故當結點規模較大時會浪費很多空間。而拉鏈法中理論上可取α≥1，且結點較大時，拉鏈法中增加的指針域可忽略不計，因此節省空間；（散列表的裝填因子定義為：α= 填入表中的元素個數 / 散列表的長度）
註：HashMap默認裝填因子是0.75。
(4)在用拉鏈法構造的散列表中，刪除結點的操作易於實現。只要簡單地刪去鏈表上相應的結點即可。而對開放定址法構造的散列表，刪除結點不能簡單地將被刪結點的空間置為空，否則將截斷在它之後填入散列表的同義詞結點的查找路徑。這是因為各種開放定址法中，空地址單元都被理解沒有查找到元素。 因此在用開放定址法處理沖突的散列表上執行刪除操作，只能在被刪結點上做刪除標記，而不能真正刪除結點。
拉鏈法的缺點
拉鏈法的缺點是：指針需要額外的空間，故當結點規模較小時，開放定址法較為節省空間，此時將節省的指針空間用來擴大散列表的規模，可使裝填因子變小，這又減少了開放定址法中的沖突，從而提高平均查找速度。
4、建立公共溢出區
這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分，凡是和基本表發生沖突的元素，一律填入溢出表(在這個方法裡面是把元素分開兩個表來存儲)。
散列表的查找過程基本上和造表過程相同。一些關鍵碼可通過散列函數轉換的地址直接找到，另一些關鍵碼在散列函數得到的地址上產生了沖突，需要按處理沖突的方法進行查找。在介紹的三種處理沖突的方法中，產生沖突後的查找仍然是給定值與關鍵碼進行比較的過程。所以，對散列表查找效率的量度，依然用平均查找長度來衡量。
查找過程中，關鍵碼的比較次數，取決於產生沖突的多少，產生的沖突少，查找效率就高，產生的沖突多，查找效率就低。因此，影響產生沖突多少的因素，也就是影響查找效率的因素。
影響產生沖突多少有以下三個因素:
1. 散列函數是否均勻;
2. 處理沖突的方法;
3. 散列表的裝填因子。
散列表的裝填因子
定義為:α= 填入表中的元素個數 / 散列表的長度
α是散列表裝滿程度的標志因子。由於表長是定值，α與"填入表中的元素個數"成正比，所以，α越大，填入表中的元素較多，產生沖突的可能性就越大;α越小，填入表中的元素較少，產生沖突的可能性就越小。
實際上，散列表的平均查找長度是裝填因子α的函數，只是不同處理沖突的方法有不同的函數。
這個HASH演算法不是大學里數據結構課里那個HASH表的演算法。這里的HASH演算法是密碼學的基礎，了解了hash基本定義，就不能不提到一些著名的hash演算法，MD5 和 SHA-1 可以說是目前應用最廣泛的Hash演算法，而它們都是以 MD4 為基礎設計的。
Hash演算法在信息安全方面的應用主要體現在以下的3個方面:
⑴ 文件校驗
我們比較熟悉的校驗演算法有奇偶校驗和CRC校驗，這2種校驗並沒有抗 數據篡改 的能力，它們一定程度上能檢測出數據傳輸中的信道誤碼，但卻不能防止對數據的惡意破壞。
MD5 Hash演算法的"數字指紋"特性，使它成為目前應用最廣泛的一種文件完整性 校驗和 (Checksum)演算法，不少Unix系統有提供計算md5 checksum的命令。
⑵ 數字簽名
Hash 演算法也是現代密碼體系中的一個重要組成部分。由於非對稱演算法的運算速度較慢，所以在 數字簽名 協議中，單向散列函數扮演了一個重要的角色。對 Hash 值，又稱"數字摘要"進行數字簽名，在統計上可以認為與對文件本身進行數字簽名是等效的。而且這樣的協議還有其他的優點。
⑶ 鑒權協議
如下的鑒權協議又被稱作挑戰--認證模式:在傳輸信道是可被偵聽，但不可被篡改的情況下，這是一種簡單而安全的方法。
一致性哈希表簡稱DHT，主要應用於分布式緩存中，可以用來解決分布式存儲結構下動態增加和刪除節點所帶來的問題。比如，一個分布式的存儲系統，要將數據存儲到具體的節點上，如果採用普通的hash方法，將數據映射到具體的節點上，如key%N（key是數據的key，N是機器節點數），如果有一個機器加入或退出這個集群，則所有的數據映射都無效了，如果是持久化存儲則要做數據遷移，如果是分布式緩存，則其他緩存就失效了。
判定哈希演算法好壞的四個定義 ：
1、平衡性(Balance)：平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。
2、單調性(Monotonicity)：單調性是指如果已經有一些內容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統中。哈希的結果應能夠保證原有已分配的內容可以被映射到原有的或者新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區。
3、分散性(Spread)：在分布式環境中，終端有可能看不到所有的緩沖，而是只能看到其中的一部分。當終端希望通過哈希過程將內容映射到緩沖上時，由於不同終端所見的緩沖范圍有可能不同，從而導致哈希的結果不一致，最終的結果是相同的內容被不同的終端映射到不同的緩沖區中。這種情況顯然是應該避免的，因為它導致相同內容被存儲到不同緩沖中去，降低了系統存儲的效率。 分散性的定義就是上述情況發生的嚴重程度。好的哈希演算法應能夠盡量避免不一致的情況發生，也就是盡量降低分散性。
4、負載(Load)：負載問題實際上是從另一個角度看待分散性問題。既然不同的終端可能將相同的內容映射到不同的緩沖區中，那麼對於一個特定的緩沖區而言，也可能被不同的用戶映射為不同的內容。與分散性一樣，這種情況也是應當避免的， 因此好的哈希演算法應能夠盡量降低緩沖的負荷。
在分布式集群中，對機器的添加刪除，或者機器故障後自動脫離集群這些操作是分布式集群管理最基本的功能。如果採用常用的hash取模演算法，那麼在有機器添加或者刪除後，很多原有的數據就無法找到了，這樣嚴重的違反了單調性原則。接下來主要說明一下一致性哈希演算法是如何設計的。
以SpyMemcached的ketama演算法來說，思路是這樣的：
把數據用hash函數，映射到一個很大的空間里，如圖所示。數據的存儲時，先得到一個hash值，對應到這個環中的每個位置，如k1對應到了圖中所示的位置，然後沿順時針找到一個機器節點B，將k1存儲到B這個節點中。
如果B節點宕機了，則B上的數據就會落到C節點上，如下圖所示：
這樣，只會影響C節點，對其他的節點A，D的數據不會造成影響。然而，這又會造成一個「雪崩」的情況，即C節點由於承擔了B節點的數據，所以C節點的負載會變高，C節點很容易也宕機，這樣依次下去，這樣造成整個集群都掛了。
為此，引入了「虛擬節點」的概念：即把想像在這個環上有很多「虛擬節點」，數據的存儲是沿著環的順時針方向找一個虛擬節點，每個虛擬節點都會關聯到一個真實節點，如下圖所使用：
圖中的A1、A2、B1、B2、C1、C2、D1、D2都是虛擬節點，機器A負載存儲A1、A2的數據，機器B負載存儲B1、B2的數據，機器C負載存儲C1、C2的數據。由於這些虛擬節點數量很多，均勻分布，因此不會造成「雪崩」現象。