分布式缓存的算法

❶ 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的数据。由于这些虚拟节点数量很多，均匀分布，因此不会造成“雪崩”现象。