⑴ 分布式系统常用的一致性算法有哪些
在做服务器负载均衡时候可供选择的负载均衡的算法有很多，包括： 轮循算法（Round Robin）、哈希算法（HASH）、最少连接算法（Least Connection）、响应速度算法（Response Time）、加权法（Weighted ）等。其中哈希算法是最为常用的算法. 典型的应用场景是： 有N台服务器提供缓存服务，需要对服务器进行负载均衡，将请求平均分发到每台服务器上，每台机器负责1/N的服务。 常用的算法是对hash结果取余数 (hash() mod N)：对机器编号从0到N-1，按照自定义的hash()算法，对每个请求的hash()值按N取模，得到余数i，然后将请求分发到编号为i的机器。但这样的算法方法存在致命问题，如果某一台机器宕机，那么应该落在该机器的请求就无法得到正确的处理，这时需要将当掉的服务器从算法从去除，此时候会有(N-1)/N的服务器的缓存数据需要重新进行计算；如果新增一台机器，会有N /(N+1)的服务器的缓存数据需要进行重新计算。对于系统而言，这通常是不可接受的颠簸（因为这意味着大量缓存的失效或者数据需要转移）。那么，如何设计一个负载均衡策略，使得受到影响的请求尽可能的少呢？ 在Memcached、Key-Value Store、Bittorrent DHT、LVS中都采用了Consistent Hashing算法，可以说Consistent Hashing 是分布式系统负载均衡的首选算法。 1、Consistent Hashing算法描述 下面以Memcached中的Consisten Hashing算法为例说明。 由于hash算法结果一般为unsigned int型，因此对于hash函数的结果应该均匀分布在[0,232-1]间，如果我们把一个圆环用232 个点来进行均匀切割，首先按照hash(key)函数算出服务器（节点）的哈希值， 并将其分布到0～232的圆上。 用同样的hash(key)函数求出需要存储数据的键的哈希值，并映射到圆上。然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器（节点）上。 Consistent Hashing原理示意图 新增一个节点的时候，只有在圆环上新增节点逆时针方向的第一个节点的数据会受到影响。删除一个节点的时候，只有在圆环上原来删除节点顺时针方向的第一个节点的数据会受到影响，因此通过Consistent Hashing很好地解决了负载均衡中由于新增节点、删除节点引起的hash值颠簸问题。 Consistent Hashing添加服务器示意图 虚拟节点（virtual nodes）：之所以要引进虚拟节点是因为在服务器（节点）数较少的情况下（例如只有3台服务器），通过hash(key)算出节点的哈希值在圆环上并不是均匀分布的（稀疏的），仍然会出现各节点负载不均衡的问题。虚拟节点可以认为是实际节点的复制品（replicas），本质上与实际节点实际上是一样的（key并不相同）。引入虚拟节点后，通过将每个实际的服务器（节点）数按照一定的比例(例如200倍)扩大后并计算其hash(key)值以均匀分布到圆环上。在进行负载均衡时候，落到虚拟节点的哈希值实际就落到了实际的节点上。由于所有的实际节点是按照相同的比例复制成虚拟节点的，因此解决了节点数较少的情况下哈希值在圆环上均匀分布的问题。 虚拟节点对Consistent Hashing结果的影响 从上图可以看出，在节点数为10个的情况下，每个实际节点的虚拟节点数为实际节点的100-200倍的时候，结果还是很均衡的。 第3段中有这些文字：“但这样的算法方法存在致命问题，如果某一台机器宕机，那么应该落在该机器的请求就无法得到正确的处理，这时需要将当掉的服务器从算法从去除，此时候会有(N-1)/N的服务器的缓存数据需要重新进行计算；” 为何是 (N-1)/N 呢？解释如下： 比如有 3 台机器，hash值 1-6 在这3台上的分布就是： host 1: 1 4 host 2: 2 5 host 3: 3 6 如果挂掉一台，只剩两台，模数取 2 ，那么分布情况就变成： host 1: 1 3 5 host 2: 2 4 6 可以看到，还在数据位置不变的只有2个： 1，2，位置发生改变的有4个，占共6个数据的比率是 4/6 = 2/3这样的话，受影响的数据太多了，势必太多的数据需要重新从 DB 加载到 cache 中，严重影响性能 【consistent hashing 的办法】 上面提到的 hash 取模，模数取的比较小，一般是负载的数量，而 consistent hashing 的本质是将模数取的比较大，为 2的32次方减1，即一个最大的 32 位整数。然后，就可以从容的安排数据导向了，那个图还是挺直观的。 以下部分为一致性哈希算法的一种PHP实现。点击下载
⑵ 常用的缓存技术
第一章 常用的缓存技术
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两种缓存。
⑶ memcached 一致性hash 用的多吗
memcache 是一个分布式的缓存系统，但是本身没有提供集群功能，在大型应用的情况下容易成为瓶颈。但是客户端这个时候可以自由扩展，分两阶段实现。第一阶段：key 要先根据一定的算法映射到一台memcache服务器。第二阶段从服务器中取出缓存的值。...
⑷ 一致性hash算法是什么
一致性哈希算法是在1997年由麻省理工学院提出的一种分布式哈希（DHT）算法。其设计目标是为了解决因特网中的热点（Hot spot)问题，初衷和CARP十分类似。
一致性Hash是一种特殊的Hash算法，由于其均衡性、持久性的映射特点，被广泛的应用于负载均衡领域，如nginx和memcached都采用了一致性Hash来作为集群负载均衡的方案。
一致性哈希算法的目标是，当K个请求key发起请求时。后台增减节点，只会引起K/N的key发生重新映射。即一致性哈希算法，在后台节点稳定时，同一key的每次请求映射到的节点是一样的。而当后台节点增减时，该算法尽量将K个key映射到与之前相同的节点上。
优点
可扩展性。一致性哈希算法保证了增加或减少服务器时，数据存储的改变最少，相比传统哈希算法大大节省了数据移动的开销。
更好地适应数据的快速增长。采用一致性哈希算法分布数据，当数据不断增长时，部分虚拟节点中可能包含很多数据、造成数据在虚拟节点上分布不均衡，此时可以将包含数据多的虚拟节点分裂，这种分裂仅仅是将原有的虚拟节点一分为二、不需要对全部的数据进行重新哈希和划分。
虚拟节点分裂后，如果物理服务器的负载仍然不均衡，只需在服务器之间调整部分虚拟节点的存储分布。这样可以随数据的增长而动态的扩展物理服务器的数量，且代价远比传统哈希算法重新分布所有数据要小很多。
以上内容参考：网络-一致性哈希
⑸ 分布式缓存中，哈希取余分区和一致性哈希分区有什么区别
环割法（一致性 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 地址进行截断，取全量长度进行测试。
⑹ memcache 一致性hash 为什么 2的32
因为一致性hash算法是来做服务器的负载均衡，而服务器的IP地址是32位，所以是2^32-1次方的数值空间
⑺ 用一致性hash做分布式，如果其中一台缓存down了，怎么办
环割法（一致性 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 地址进行截断，取全量长度进行测试。
⑻ chcahe 如何保证分布式缓存数据一致性
VPLEX的技术核心是“分布式缓存一致性”，下图则是“分布式缓存一致性”技术的工作机制示意：正是因为这项核心技术优势，使得VPLEX方案和目前所有厂商的虚拟化方案截然不同，并能够实现异地的数据中心整合。对跨数据中心的所有负载实现跨引擎的平摊或者实时迁移，来自任何一个主机的I/O请求可以通过任何一个引擎得到响应。
缓存一致性的记录目录使用少量的元数据，记录下哪个数据块属于哪个引擎更新的，以及在何时更新过，并通过4K大小的数据块告诉在集群中的所有其他的引擎。在整个过程中实际发生的沟通过程，远远比实际上正在更新数据块少很多。
分布式缓存一致性数据流示意图：上方是一个目录，记录下左侧的主机读取缓存A的操作，并分发给所有引擎，右侧主机需要读取该数据块时，会先通过目录查询，确定该数据块所属的引擎位置，读取请求会直接发送给引擎，并直接从数据块所在的缓存上读取。
当一个读请求进入时，VPLEX会自动检查目录，查找该数据块所属的引擎，一旦确定该数据块所属的引擎位置，读的请求会直接发送给该引擎。一旦一个写入动作完成，并且目录表被修改，这时另一个读请求从另一个引擎过来，VPLEX会检查目录，并且直接从该引擎的缓存上读取。如果该数据仍然在缓存上，则完全没必要去磁盘上读取。
如上图，来自图中左侧主机的操作，由Cache A服务，会记录一个更新状态，并分发给所有所有引擎知道。如果读取的需求来自最右侧的服务器，首先通过目录查询。通过这种技术可以实现所有引擎一致性工作，而且这个技术不仅可以跨引擎还可以跨VPLEX集群，而VPLEX集群可以跨区域，因此缓存一致性也可以跨区域部署。
分布式缓存一致性技术使VPLEX相比传统的虚拟化方案拥有更高的性能和可靠性，并实现异地数据中心的虚拟化整合
对传统的虚拟化架构来说，如果虚拟化的I/O集群中有一个节点坏了，那么性能就会降低一半，而且实际情况降低不止一半。因为坏了一个节点，这个节点缓存一般会被写进去。因为没有缓存，操作会直接写到硬盘里。如果图中中心这个节点坏掉，那主机所有的可用性都没有了。而VPLEX如果有一个引擎或者一个控制器坏掉了，那这个引擎的负载会均摊到其他活动引擎上。这样总体来讲用户可以维持可预知性能，性能降低也不那么明显。