精华内容
下载资源
问答
  • memcached 内存模型memcached 的缓存算法(简单列举多集中缓存算法/调度算法)分布式算法/一致性Hash虚拟节点技术memcached 的优缺点/简单的跟redis对比 2.memcached 工作原理 首先 memcached 是以...

    1.总览

    • memcached 工作原理
    • memcached 内存模型
    • memcached 的缓存算法(简单列举多集中缓存算法/调度算法)
    • 分布式算法/一致性Hash
    • 虚拟节点技术
    • memcached 的优缺点/简单的跟redis对比

    2.memcached 工作原理


    首先 memcached 是以守护程序方式运行于一个或多个服务器中,随时接受客户端的连接操作,客户端可以由各种语言编写,目前已知的客户端 API 包括 Perl/PHP/Python/Ruby/Java/C#/C 等等。客户端在与 memcached 服务建立连接之后,接下来的事情就是存取对象了,每个被存取的对象都有一个唯一的标识符 key,存取操作均通过这个 key 进行,保存到memcached 中的对象实际上是放置内存中的,并不是保存在 cache 文件中的,这也是为什么 memcached 能够如此高效快速的原因。注意,这些对象并不是持久的,服务停止之后,里边的数据就会丢失。

    与许多 cache 工具类似,Memcached 的原理并不复杂。它采用了C/S的模式,在 server 端启动服务进程,在启动时可以指定监听的 ip,自己的端口号,所使用的内存大小等几个关键参数。一旦启动,服务就一直处于可用状态。Memcached 的目前版本是通过C实现,采用了单进程,单线程,异步I/O,基于事件 (event_based) 的服务方式.使用libevent 作为事件通知实现。多个 Server 可以协同工作,但这些 Server 之间是没有任何通讯联系的,每个 Server 只是对自己的数据进行管理。Client 端通过指定 Server 端的 ip 地址(通过域名应该也可以)。需要缓存的对象或数据是以 key->value对的形式保存在Server端。key 的值通过 hash 进行转换,根据 hash 值把 value 传递到对应的具体的某个 Server 上。当需要获取对象数据时,也根据 key 进行。首先对 key 进行 hash,通过获得的值可以确定它被保存在了哪台 Server 上,然后再向该 Server 发出请求。Client 端只需要知道保存 hash(key) 的值在哪台服务器上就可以了。
            其实说到底,memcache 的工作就是在专门的机器的内存里维护一张巨大的 hash 表,来存储经常被读写的一些数组与文件,从而极大的提高网站的运行效率。


    3.memcached 内存模型

    为了减少内存的碎片,memcached 是用了一种预处理内存大小的方式来存储我们的缓存,减少内存的碎片,但是这样会直接导致浪费好多内存空间。

     基本概念:slab,page,chunk。 
        slab,是一个逻辑概念。它是在启动memcached实例的时候预处理好的,每个slab对应一个chunk size,也就是说不同slab有不同的chunk size。具体分配多少个slab由参数 -f (增长因子)和 -n (chunk最小尺寸)决定的。 
        page,可以理解为内存页。大小固定为1m。slab会在存储请求时向系统申请page,并将page按chunk size进行切割。 
        chunk,是保存用户数据的最小单位。用户数据item(包括key,value)最终会保存到chunk内。chunk规格是固定的,如果用户数据放进来后还有剩余则这剩余部分不能做其他用途。 



         工作流程:memcahed实例启动,根据 -f 和 -n 进行预分配slab。以 -n 为最小值开始,以 -f 为比值生成等比数列,直到1m为止(每个slab的chunk size都要按8的倍数进行补全,比如:如果按比值算是556的话,会再加4到560成为8的整倍数)。然后每个slab分配一个page。当用户发来存储请求时(key,value),memcached会计算key+value的大小,看看属于哪个slab。确定slab后看里面的是否有空闲chunk放key+value,如果不够就再向系统申请一个page(如果此时已经达到 -m 参数设置的内存使用上限,则看是否设置了 -M 。如果设置了 -M 则返回错误提示,否则按LRU算法删除数据)。申请后将该page按本slab的chunk size 进行切割,然后分配一个来存放用户数据。 
        注意: 
        1,chunk是在page里面划分的,而page固定为1m,所以chunk最大不能超过1m。 
        2,chunk实际占用内存要加48B,因为chunk数据结构本身需要占用48B。 
        3,如果用户数据大于1m,则memcached会将其切割,放到多个chunk内。 
        4,已分配出去的page不能回收。 
    优化建议 
    1. -n 参数的设置,注意将此参数设置为1024可以整除的数(还要考虑48B的差值),否则余下来的部分就浪费了。 
    2. 不要存储超过1m的数据。因为要拆成多个chunk,计算和时间成本都成倍增加。 
    3. 善用stats命令查看memcached状态。 
    4. 消灭eviction(被删除的数据)。造成eviction是因为内存不够,有三个思路:一是在CPU有余力的情况下开启压缩(PHP扩展);二是增加内存;三是调整 -f 参数,减少内存浪费。 
    5. 调整业务代码,提高命中率。 
    6. 缓存小数据。省带宽,省网络I/O时间,省内存。 
    7. 根据业务特点,为数据尺寸区间小的业务分配专用的memcached实例。这样可以调小 -f 参数,使数据集中存在少数几个slab上,内存浪费较少。



    4.memcached 的缓存算法


    4.1 memcached 删除机制

    memcached 是缓存,不需要永久的保存到服务器上,本章介绍memcache 的删除机制

    4.2 memcached 在数据删除方面有效的利用资源

    Memcached 不会释放已经分配的内存,记录过期之后,客户端无法再看到这一条记录,其存储空间就可以利用。

    4.3 Lazy Expiration

    memcached 内部不会监视记录是否过期,而是在get 时查看记录的时间戳,检查记录是否过期。这种技术被称为lazy(惰性)expiration。因此,memcached不会在过期监视上耗费CPU 时间


    4.4 LRU:从缓存中有效删除数据的原理

    memcached 会优先使用已超时的记录的空间,但即使如此,也会发生追加新记录时空间不足的情况,此时就要使用名为Least Recently Used(LRU)机制来分配空间。顾名思义,这是删除“最近最少使用”的记录的机制。因此,当memcached 的内存空间不足时(无法从slab class 获取到新的空间时),就从最近未被使用的记录中搜索,并将其空间分配给新的记录。从缓存的实用角度来看,该模型十分理想。不过,有些情况下LRU 机制反倒会造成麻烦。memcached 启动时通过“M”参数可以禁止LRU,如下所示:
    $ memcached -M –m 1024
    启动时必须注意的是,小写的“m”选项是用来指定最大内存大小的。不指定具体数值则使用默认值64MB。
    指定“M”参数启动后,内存用尽时memcached 会返回错误。话说回来,memcached 毕竟不是存储器,而是缓存,所以推荐使用LRU



    4.5 其他的缓存算法

    Least Frequently Used(LFU):
    大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率。我会把最不常用的缓存对象踢走。

    Least Recently User(LRU):
    我是 LRU 缓存算法,我把最近最少使用的缓存对象给踢走。
    我总是需要去了解在什么时候,用了哪个缓存对象。如果有人想要了解我为什么总能把最近最少使用的对象踢掉,是非常困难的。
    浏览器就是使用了我(LRU)作为缓存算法。新的对象会被放在缓存的顶部,当缓存达到了容量极限,我会把底部的对象踢走,而技巧就是:我会把最新被访问的缓存对象,放到缓存池的顶部。
    所以,经常被读取的缓存对象就会一直呆在缓存池中。有两种方法可以实现我,array 或者是 linked list。
    我的速度很快,我也可以被数据访问模式适配。我有一个大家庭,他们都可以完善我,甚至做的比我更好(我确实有时会嫉妒,但是没关系)。我家庭的一些成员包括 LRU2 和 2Q,他们就是为了完善 LRU 而存在的。


    Least Recently Used 2(LRU2):
    我是 Least Recently Used 2,有人叫我最近最少使用 twice,我更喜欢这个叫法。我会把被两次访问过的对象放入缓存池,当缓存池满了之后,我会把有两次最少使用的缓存对象踢走。因为需要跟踪对象2次,访问负载就会随着缓存池的增加而增加。如果把我用在大容量的缓存池中,就会有问题。另外,我还需要跟踪那么不在缓存的对象,因为他们还没有被第二次读取。我比LRU好,而且是 adoptive to access 模式 。

    Two Queues(2Q):
    我是 Two Queues;我把被访问的数据放到 LRU 的缓存中,如果这个对象再一次被访问,我就把他转移到第二个、更大的 LRU 缓存。
    我踢走缓存对象是为了保持第一个缓存池是第二个缓存池的1/3。当缓存的访问负载是固定的时候,把 LRU 换成 LRU2,就比增加缓存的容量更好。这种机制使得我比 LRU2 更好,我也是 LRU 家族中的一员,而且是 adoptive to access 模式 。


    Adaptive Replacement Cache(ARC):
    我是 ARC,有人说我是介于 LRU 和 LFU 之间,为了提高效果,我是由2个 LRU 组成,第一个,也就是 L1,包含的条目是最近只被使用过一次的,而第二个 LRU,也就是 L2,包含的是最近被使用过两次的条目。因此, L1 放的是新的对象,而 L2 放的是常用的对象。所以,别人才会认为我是介于 LRU 和 LFU 之间的,不过没关系,我不介意。
    我被认为是性能最好的缓存算法之一,能够自调,并且是低负载的。我也保存着历史对象,这样,我就可以记住那些被移除的对象,同时,也让我可以看到被移除的对象是否可以留下,取而代之的是踢走别的对象。我的记忆力很差,但是我很快,适用性也强。


    Most Recently Used(MRU):
    我是 MRU,和 LRU 是对应的。我会移除最近最多被使用的对象,你一定会问我为什么。好吧,让我告诉你,当一次访问过来的时候,有些事情是无法预测的,并且在缓存系统中找出最少最近使用的对象是一项时间复杂度非常高的运算,这就是为什么我是最好的选择。
    我是数据库内存缓存中是多么的常见!每当一次缓存记录的使用,我会把它放到栈的顶端。当栈满了的时候,你猜怎么着?我会把栈顶的对象给换成新进来的对象!


    First in First out(FIFO):
    我是先进先出,我是一个低负载的算法,并且对缓存对象的管理要求不高。我通过一个队列去跟踪所有的缓存对象,最近最常用的缓存对象放在后面,而更早的缓存对象放在前面,当缓存容量满时,排在前面的缓存对象会被踢走,然后把新的缓存对象加进去。我很快,但是我并不适用。


    Second Chance:
    大家好,我是 second chance,我是通过 FIFO 修改而来的,被大家叫做 second chance 缓存算法,我比 FIFO 好的地方是我改善了 FIFO 的成本。我是 FIFO 一样也是在观察队列的前端,但是很FIFO的立刻踢出不同,我会检查即将要被踢出的对象有没有之前被使用过的标志(1一个 bit 表示),没有没有被使用过,我就把他踢出;否则,我会把这个标志位清除,然后把这个缓存对象当做新增缓存对象加入队列。你可以想象就这就像一个环队列。当我再一次在队头碰到这个对象时,由于他已经没有这个标志位了,所以我立刻就把他踢开了。我在速度上比 FIFO 快。

    CLock:
    我是 Clock,一个更好的 FIFO,也比 second chance 更好。因为我不会像 second chance 那样把有标志的缓存对象放到队列的尾部,但是也可以达到 second chance 的效果。
    我持有一个装有缓存对象的环形列表,头指针指向列表中最老的缓存对象。当缓存 miss 发生并且没有新的缓存空间时,我会问问指针指向的缓存对象的标志位去决定我应该怎么做。如果标志是0,我会直接用新的缓存对象替代这个缓存对象;如果标志位是1,我会把头指针递增,然后重复这个过程,知道新的缓存对象能够被放入。我比 second chance 更快。


    Simple time-based:
    我是 simple time-based 缓存算法,我通过绝对的时间周期去失效那些缓存对象。对于新增的对象,我会保存特定的时间。我很快,但是我并不适用。


    Extended time-based expiration:
    我是 extended time-based expiration 缓存算法,我是通过相对时间去失效缓存对象的;对于新增的缓存对象,我会保存特定的时间,比如是每5分钟,每天的12点。


    Sliding time-based expiration:
    我是 sliding time-based expiration,与前面不同的是,被我管理的缓存对象的生命起点是在这个缓存的最后被访问时间算起的。我很快,但是我也不太适用。

    其他的缓存算法还考虑到了下面几点:
    • 成本:如果缓存对象有不同的成本,应该把那些难以获得的对象保存下来。
    • 容量:如果缓存对象有不同的大小,应该把那些大的缓存对象清除,这样就可以让更多的小缓存对象进来了。
    • 时间:一些缓存还保存着缓存的过期时间。电脑会失效他们,因为他们已经过期了。
      根据缓存对象的大小而不管其他的缓存算法可能是有必要的。

    Random Cache
    我是随机缓存,我随意的替换缓存实体,没人敢抱怨。你可以说那个被替换的实体很倒霉。通过这些行为,我随意的去处缓存实体。我比 FIFO 机制好,在某些情况下,我甚至比 LRU 好,但是,通常LRU都会比我好


    5.分布式算法/一致性hash


    5.1 基本场景

    比如你有 N 个 cache 服务器(后面简称 cache ),那么如何将一个对象 object 映射到 N 个 cache 上呢,你很可能会采用类似下面的通用方法计算 object 的 hash 值,然后均匀的映射到到 N 个 cache ;
    hash(object)%N

    一切都运行正常,再考虑如下的两种情况;
    1. 一个 cache 服务器 m down 掉了(在实际应用中必须要考虑这种情况),这样所有映射到 cache m 的对象都会失效,怎么办,需要把 cache m 从 cache 中移除,这时候 cache 是 N-1 台,映射公式变成了 hash(object)%(N-1) ;
    2. 由于访问加重,需要添加 cache ,这时候 cache 是 N+1 台,映射公式变成了 hash(object)%(N+1) ;
    1 和 2 意味着什么?这意味着突然之间几乎所有的 cache 都失效了。对于服务器而言,这是一场灾难,洪水般的访问都会直接冲向后台服务器;
    再来考虑第三个问题,由于硬件能力越来越强,你可能想让后面添加的节点多做点活,显然上面的 hash 算法也做不到。
    有什么方法可以改变这个状况呢,这就是 consistent hashing...


    5.2 hash 算法和单调性

    Hash 算法的一个衡量指标是单调性( Monotonicity ),定义如下:
      单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中,又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去,而不会被映射到旧的缓冲集合中的其他缓冲区。
    容易看到,上面的简单 hash 算法 hash(object)%N 难以满足单调性要求。


    5.3 consistent hashing 算法的原理

    consistent hashing 是一种 hash 算法,简单的说,在移除 / 添加一个 cache 时,它能够尽可能小的改变已存在 key映射关系,尽可能的满足单调性的要求。
    下面就来按照 5 个步骤简单讲讲 consistent hashing 算法的基本原理。


    5.4  环形hash 空间

    考虑通常的 hash 算法都是将 value 映射到一个 32 为的 key 值,也即是 0~2^32-1 次方的数值空间;我们可以将这个空间想象成一个首( 0 )尾( 2^32-1 )相接的圆环,如下面图 1 所示的那样。
    circle space
    图 1 环形 hash 空间


    5.5 把对象映射到hash 空间

    接下来考虑 4 个对象 object1~object4 ,通过 hash 函数计算出的 hash 值 key 在环上的分布如图 2 所示。
    hash(object1) = key1;
    … …
    hash(object4) = key4;
    object
    图 2   4个对象的 key 值分布


    5.6 把cache 映射到hash 空间

    Consistent hashing 的基本思想就是将对象和 cache 都映射到同一个 hash 数值空间中,并且使用相同的 hash 算法。
    假设当前有 A,B 和 C 共 3 台 cache ,那么其映射结果将如图 3 所示,他们在 hash 空间中,以对应的 hash 值排列。
    hash(cache A) = key A;
    … …
    hash(cache C) = key C;
    cache
    图 3  cache和对象的 key 值分布
     
    说到这里,顺便提一下 cache 的 hash 计算,一般的方法可以使用 cache 机器的 IP 地址或者机器名作为 hash 输入。


    5.7 把对象映射到cache

    现在 cache 和对象都已经通过同一个 hash 算法映射到 hash 数值空间中了,接下来要考虑的就是如何将对象映射到 cache 上面了。
    在这个环形空间中,如果沿着顺时针方向从对象的 key 值出发,直到遇见一个 cache ,那么就将该对象存储在这个 cache 上,因为对象和 cache 的 hash 值是固定的,因此这个 cache 必然是唯一和确定的。这样不就找到了对象和cache 的映射方法了吗?!
    依然继续上面的例子(参见图 3 ),那么根据上面的方法,对象 object1 将被存储到 cache A 上; object2 和object3 对应到 cache C ; object4 对应到 cache B ;


    5.8 考察cache 的变动

    前面讲过,通过 hash 然后求余的方法带来的最大问题就在于不能满足单调性,当 cache 有所变动时, cache 会失效,进而对后台服务器造成巨大的冲击,现在就来分析分析 consistent hashing 算法。


    5.8.1 移除 cache

    考虑假设 cache B 挂掉了,根据上面讲到的映射方法,这时受影响的将仅是那些沿 cache B 逆时针遍历直到下一个 cache ( cache C )之间的对象,也即是本来映射到 cache B 上的那些对象。
    因此这里仅需要变动对象 object4 ,将其重新映射到 cache C 上即可;参见图 4 。
    remove
    图 4 Cache B 被移除后的 cache 映射

    5.8.2 添加 cache

    再考虑添加一台新的 cache D 的情况,假设在这个环形 hash 空间中, cache D 被映射在对象 object2 和 object3之间。这时受影响的将仅是那些沿 cache D 逆时针遍历直到下一个 cache ( cache B )之间的对象(它们是也本来映射到 cache C 上对象的一部分),将这些对象重新映射到 cache D 上即可。
     
    因此这里仅需要变动对象 object2 ,将其重新映射到 cache D 上;参见图 5 。
    add
    图 5 添加 cache D 后的映射关系



    6.虚拟节点技术


    考量 Hash 算法的另一个指标是平衡性 (Balance) ,定义如下:
    平衡性
      平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。
    hash 算法并不是保证绝对的平衡,如果 cache 较少的话,对象并不能被均匀的映射到 cache 上,比如在上面的例子中,仅部署 cache A 和 cache C 的情况下,在 4 个对象中, cache A 仅存储了 object1 ,而 cache C 则存储了 object2、 object3 和 object4 ;分布是很不均衡的。
    为了解决这种情况, consistent hashing 引入了“虚拟节点”的概念,它可以如下定义:


    “虚拟节点”( virtual node )是实际节点在 hash 空间的复制品( replica ),一实际个节点对应了若干个“虚拟节点”,这个对应个数也成为“复制个数”,“虚拟节点”在 hash 空间中以 hash 值排列。

    仍以仅部署 cache A 和 cache C 的情况为例,在图 4 中我们已经看到, cache 分布并不均匀。现在我们引入虚拟节点,并设置“复制个数”为 2 ,这就意味着一共会存在 4 个“虚拟节点”, cache A1, cache A2 代表了 cache A ;cache C1, cache C2 代表了 cache C ;假设一种比较理想的情况,参见图 6 。
    virtual nodes
    图 6 引入“虚拟节点”后的映射关系
     
    此时,对象到“虚拟节点”的映射关系为:
    objec1->cache A2 ; objec2->cache A1 ; objec3->cache C1 ; objec4->cache C2 ;
    因此对象 object1 和 object2 都被映射到了 cache A 上,而 object3 和 object4 映射到了 cache C 上;平衡性有了很大提高。
    引入“虚拟节点”后,映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } 。查询物体所在 cache 时的映射关系如图 7 所示。
    map
    图 7 查询对象所在 cache
     
    “虚拟节点”的 hash 计算可以采用对应节点的 IP 地址加数字后缀的方式。例如假设 cache A 的 IP 地址为202.168.14.241 。
    引入“虚拟节点”前,计算 cache A 的 hash 值:
    Hash(“202.168.14.241”);
    引入“虚拟节点”后,计算“虚拟节”点 cache A1 和 cache A2 的 hash 值:
    Hash(“202.168.14.241#1”);  // cache A1
    Hash(“202.168.14.241#2”);  // cache A2
          


    7.memcached 与redis 的对比




    参考:




    展开全文
  • 图文并茂,一篇文章吃透《一致性 Hash 算法与虚拟节点》。

    缘起

    今天我们来说说“一致性Hash”算法,以及虚拟节点。

    这并不是一个难理解的概念,希望一篇文章下来,你能完全吃透。

    在网站系统发展初期,前辈工程师探索出了数据库这一系统核心组件,

    数据的持久化被与系统本身解耦开,独立发展且愈加可靠。

    时间往后推移,随着互联网的普及,一个系统需要承载的用户数量指数级增长,

    开发者不得不横向扩展服务器,通过负载均衡技术,使用户分散到各个服务器上。

    随着服务器的增多,可靠的数据库系统也不堪重负,

    开发者不得不将数据库中的数据通过“分库分表”技术,切分到不同的数据库中,

    减轻单一数据库系统的压力。

    那么问题来了,如何知道我们需要的数据在哪个数据库中?

    没错。hash!

    正如我们在 HashMap 中做的一样,对参数取 hash 值,再对 hash 值取模,

    就可以既均匀切分存储数据,又知道数据在哪个库中。

    简单hash

    举个例子,现在有A,B,C,D共4个库,和参数为1,2,3……9,10共10个数据。

    插图1

    我们简化hash算法为乘以1,

    即 (1*1)%4=1,参数为1的数据落在A库中。

    即 (2*1)%4=2,参数为2的数据落在B库中。

    即 (3*1)%4=3,参数为3的数据落在C库中。

    即 (4*1)%4=0,参数为4的数据落在D库中。

    ……

    插图2

    嗯!我很满意,一切井然有序。

    当系统需要参数为2的数据时,只需要通过定位算法 (2*1)%4=2 便知道数据存在B库中。

    当系统需要参数为9的数据时,只需要通过定位算法 (9*1)%4=1 便知道数据存在A库中。

    可好景不长,正当系统稳定健康运行的时候,

    B库不知道出现什么问题,失去了连接,系统中只剩下A,C,D共3个库。

    这可真糟糕,但是我们还不知道会发生什么事情,对系统的影响有多大。

    让我们先把目光聚集到局部上面来分析一下,

    参数为2,6和10的数据存在B库上,影响应该是最大的,

    如果现在系统需要参数为2的数据,那么它会通过定位算法 (2*1)%3=2 找到C库上。

    插图3

    但很遗憾,C上并没有存储参数为2的数据。

    值得庆幸的是,原来数据是有副本的,失去连接的B库数据并没有丢失,而是在一个更大的主库中,

    只要给系统一些时间,主库中对应B库的数据,就会根据定位算法被重新分配到A,C,D库中。

    分配如下,

    即 (2*1)%3=2,参数为2的数据落在C库中。

    即 (6*1)%3=0,参数为6的数据落在D库中。

    即 (10*1)%3=1,参数为10的数据落在A库中。

    插图4

    好了,现在原来B库中的数据被重新分配到A,C,D库。

    当系统需要取数据的时候,只需要通过参数根据定位算法,

    到对应的库中读取即可。

    如果现在你以为万事大吉,那可就太早了。

    别忘了我们刚刚是聚焦到局部来分析状况的。

    当我们目光拉远时,我们发现,

    不止是参数为2,6,10的数据被重新分配,

    几乎所有的数据都被重新分配了!

    因为,

    (1*1)%3=1,参数为1的数据落在A库中。

    (2*1)%3=2,参数为2的数据落在C库中。

    (3*1)%3=0,参数为3的数据落在D库中。

    ……

    插图5

    真是糟糕透顶!

    原本是想节约提高性能,结果凭空需要浪费这么多计算资源在重新分配数据上。

    该怎么办呢?

    诶,对,一致性Hash算法要大显身手了!

    一致性Hash算法

    一致性Hash算法通过一个 Hash 环,巧妙的让影响降到很低。

    假设存在一个 Hash 环,它一圈的范围是 0 到 2^32-1,

    先对数据库A,B,C和D的标识做 hash 运算,即上面的定位算法,

    确定4个库在 Hash 环上的位置,

    再通过定位算法将得出参数为1,2,3……9,10共10个数据在 Hash环上的位置,

    这边我们不展示过程,只展示结果。

    插图7

    一致性Hash算法规定我们将数据存在定位到的 Hash 环上位置顺时针遇到的第一个节点(数据库)。

    即,

    参数为1,4和8的数据存在数据库A中,

    参数为5的数据存在数据库B中,

    参数为3和7的数据存在数据库C中,

    参数为2,6,9和10的数据存在数据库D中。

    此时,其实我们已经不惧怕数据库宕机的情况了,

    假设我们的数据库B又一次失去连接。

    会发生什么情况呢?

    插图8

    影响十分有限,只有数据库A和B在 Hash 环上的位置之间的数据,才受到了影响。

    如图,参数为5的数据,需要重新从主库中复制到数据库C中,以保证系统需要参数为5的数据时可以顺利读取到。

    而对于其他参数值的数据,并没有受到影响。

    以上描述的是节点减少的情况,实际上在节点增加的时候,

    一致性Hash算法依然可以保持大部分节点的稳定,不需要改变。

    在这里我不做赘述,但你参考上面,独立思考一下。

    一致性 Hash 算法如果只是到这里,实际上还引入了一个新的问题——数据倾斜。

    即我们假设数据落在 Hash 环上每个位置的概率是一致的,

    但实际上,每个节点覆盖的 Hash 环上的大小并不相等,

    甚至可能有几倍的差距。

    例如,在上面A,C,D库的基础上,我们添加了一个节点——数据库E。

    它的位置如图所示。

    插图10

    因为它(数据库E)与上一个节点(数据库D)距离太近,导致没有任何一个数据落到它上面,

    而正是与他相近特别近的上一个节点(数据库D),却存储了4个数据,

    这就是数据倾斜,有些节点承载了很重的任务,有些节点却悠闲悠闲。

    虚拟节点

    为了解决数据倾斜的问题,我们还需要加入虚拟节点这一策略。

    即,将每个数据库都通过定位算法生成几个在 Hash 环上的位置,

    每个位置都承担上面节点的功能,

    区别在于原来每个数据库对应一个节点,

    现在每个数据库会对应若干个节点,

    这就是虚拟节点。

    插图11

    为了避免图过于混乱,这边我标出 E 数据库的 3 个虚拟节点,

    可以从图中看出,现在

    E#1有 0 个数据,

    E#2有 1 个数据(参数为5的数据),

    E#3有 2 个数据(参数为6和9的数据)。

    而实际上,不管数据定位后归属与E#1、E#2还是E#3,

    在实际的数据存储和读取时,都是在数据库 E。

    不难发现,在添加了虚拟节点的策略之后,

    数据倾斜的情况得到了改善。

    这就是完整的一致性Hash算法与虚拟节点啦!

    记住,在实际应用中,3个虚拟节点是不够的,你需要更多的虚拟节点,以保证节点的负载更加均衡。

    展开全文
  • 一致性hash虚拟节点

    千次阅读 2019-04-20 16:32:00
    虚拟节点”( virtual node )是实际节点在 hash 空间的复制品( replica ),一实际个节点对应了若干个“虚拟节点”,这个对应个数也成为“复制个数”,“虚拟节点”在 hash 空间中以 hash 值排列。...

     consistent hashing 算法的原理

    consistent hashing 是一种 hash 算法,简单的说,在移除 / 添加一个 cache 时,它能够尽可能小的改变已存在key 映射关系,尽可能的满足单调性的要求。

    下面就来按照 5 个步骤简单讲讲 consistent hashing 算法的基本原理。

    1 环形hash 空间

    考虑通常的 hash 算法都是将 value 映射到一个 32 为的 key 值,也即是 0~2^32-1 次方的数值空间;我们可以将这个空间想象成一个首( 0 )尾( 2^32-1 )相接的圆环,如下面图 1 所示的那样。

     

    图 1 环形 hash 空间

    2 把对象映射到hash 空间

    接下来考虑 4 个对象 object1~object4 ,通过 hash 函数计算出的 hash 值 key 在环上的分布如图 2 所示。

    hash(object1) = key1;

    … …

    hash(object4) = key4;

     

    图 2 4 个对象的 key 值分布

    3 把cache 映射到hash 空间

    Consistent hashing 的基本思想就是将对象和 cache 都映射到同一个 hash 数值空间中,并且使用相同的 hash算法。

    假设当前有 A,B 和 C 共 3 台 cache ,那么其映射结果将如图 3 所示,他们在 hash 空间中,以对应的 hash 值排列。

    hash(cache A) = key A;

    … …

    hash(cache C) = key C;

     

    图 3 cache 和对象的 key 值分布

     

    说到这里,顺便提一下 cache 的 hash 计算,一般的方法可以使用 cache 机器的 IP 地址或者机器名作为 hash输入。

    4 把对象映射到cache

    现在 cache 和对象都已经通过同一个 hash 算法映射到 hash 数值空间中了,接下来要考虑的就是如何将对象映射到 cache 上面了。

    在这个环形空间中,如果沿着顺时针方向从对象的 key 值出发,直到遇见一个 cache ,那么就将该对象存储在这个 cache 上,因为对象和 cache 的 hash 值是固定的,因此这个 cache 必然是唯一和确定的。这样不就找到了对象和 cache 的映射方法了吗?!

    依然继续上面的例子(参见图 3 ),那么根据上面的方法,对象 object1 将被存储到 cache A 上; object2 和object3 对应到 cache C ; object4 对应到 cache B ;

    5 考察cache 的变动

    前面讲过,通过 hash 然后求余的方法带来的最大问题就在于不能满足单调性,当 cache 有所变动时, cache会失效,进而对后台服务器造成巨大的冲击,现在就来分析分析 consistent hashing 算法。

    5.1 移除 cache

    考虑假设 cache B 挂掉了,根据上面讲到的映射方法,这时受影响的将仅是那些沿 cache B 逆时针遍历直到下一个 cache ( cache C )之间的对象,也即是本来映射到 cache B 上的那些对象。

    因此这里仅需要变动对象 object4 ,将其重新映射到 cache C 上即可;参见图 4 。

     

    图 4 Cache B 被移除后的 cache 映射

    5.2 添加 cache

    再考虑添加一台新的 cache D 的情况,假设在这个环形 hash 空间中, cache D 被映射在对象 object2 和object3 之间。这时受影响的将仅是那些沿 cache D 逆时针遍历直到下一个 cache ( cache B )之间的对象(它们是也本来映射到 cache C 上对象的一部分),将这些对象重新映射到 cache D 上即可。

     

    因此这里仅需要变动对象 object2 ,将其重新映射到 cache D 上;参见图 5 。

     

    图 5 添加 cache D 后的映射关系

    虚拟节点

    考量 Hash 算法的另一个指标是平衡性 (Balance) ,定义如下:

    平衡性

      平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去,这样可以使得所有的缓冲空间都得到利用。

    hash 算法并不是保证绝对的平衡,如果 cache 较少的话,对象并不能被均匀的映射到 cache 上,比如在上面的例子中,仅部署 cache A 和 cache C 的情况下,在 4 个对象中, cache A 仅存储了 object1 ,而 cache C 则存储了object2 、 object3 和 object4 ;分布是很不均衡的。

    为了解决这种情况, consistent hashing 引入了“虚拟节点”的概念,它可以如下定义:

    “虚拟节点”( virtual node )是实际节点在 hash 空间的复制品( replica ),一实际个节点对应了若干个“虚拟节点”,这个对应个数也成为“复制个数”,“虚拟节点”在 hash 空间中以 hash 值排列。

    仍以仅部署 cache A 和 cache C 的情况为例,在图 4 中我们已经看到, cache 分布并不均匀。现在我们引入虚拟节点,并设置“复制个数”为 2 ,这就意味着一共会存在 4 个“虚拟节点”, cache A1, cache A2 代表了 cache A ; cache C1, cache C2 代表了 cache C ;假设一种比较理想的情况,参见图 6 。

     

    图 6 引入“虚拟节点”后的映射关系

     

    此时,对象到“虚拟节点”的映射关系为:

    objec1->cache A2 ; objec2->cache A1 ; objec3->cache C1 ; objec4->cache C2 ;

    因此对象 object1 和 object2 都被映射到了 cache A 上,而 object3 和 object4 映射到了 cache C 上;平衡性有了很大提高。

    引入“虚拟节点”后,映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } 。查询物体所在 cache 时的映射关系如图 7 所示。

     

    图 7 查询对象所在 cache

     

    “虚拟节点”的 hash 计算可以采用对应节点的 IP 地址加数字后缀的方式。例如假设 cache A 的 IP 地址为202.168.14.241 。

    引入“虚拟节点”前,计算 cache A 的 hash 值:

    Hash(“202.168.14.241”);

    引入“虚拟节点”后,计算“虚拟节”点 cache A1 和 cache A2 的 hash 值:

    Hash(“202.168.14.241#1”);  // cache A1

    Hash(“202.168.14.241#2”);  // cache A2

    转载于:https://my.oschina.net/u/2935389/blog/3039730

    展开全文
  • 一致性hash的原理介绍,前人已经做的很清楚了,可以参看下面链接: 一致性HASH算法详解 上文美中不足的是,数据结构的设计较复杂,hash环的实现,属性用简单的列表和字典实现即可。 一致性哈希(不设置虚拟节点)...

    一致性hash的原理介绍,前人已经做的很清楚了,可以参看下面链接:

    一致性HASH算法详解

    上文美中不足的是,数据结构的设计较复杂,hash环的实现,属性用简单的列表和字典实现即可。

    一致性哈希(不设置虚拟节点)

    首先放不设置虚拟节点的代码,可以看见删除掉某个节点时很容易引起雪崩效应,代码如下。

    """对一致性hash进行学习,构造没有vnode的hash,增加和删除节点以进行观察,会产生对应的雪崩效应"""
    from zlib import crc32
    import memcache
    
    class conhashnorep(object):
        def __init__(self,nodes=None):
            """此处nodes代表需要初始化的node列表,为进行对比先提供虚拟节点副本数,ring是存储hash-node的字典,key是存储所有hash值的列表"""
            self.nodes=nodes
            self.ring={}
            self._sorted_keys=[]
            self.add_nodes(nodes)
    
        def _add_node(self,node):
            bnode=bytes(node,encoding="utf8")
            nodehash=abs(crc32(bnode))
            self.ring[nodehash]=node
            self._sorted_keys.append(nodehash)
            self._sorted_keys.sort()
    
        def add_nodes(self,nodes):
            if nodes:
                for node in nodes:
                    self._add_node(node)
    
        def remove_nodes(self,nodes):
            """对于remove的操作,如果直接操作已经产生的ring字典,会比较麻烦,因为ring是{hashnode:node}的键值对形式,
            直接处理涉及到字典直接查找值ring.values()/ring.keys(),以及通过值来remove(key)的操作,太麻烦"""
            if nodes:
                for node in nodes:
                    bnode = bytes(node, encoding="utf8")
                    nodehash = abs(crc32(bnode))
                    del self.ring[nodehash]
                    self._sorted_keys.remove(nodehash)
    
        def get_node(self,key):
            bkey=bytes(key,encoding="utf8")
            keyhash=abs(crc32(bkey))
            i=0
            for nodehash in self._sorted_keys:
                i += 1
                if keyhash < nodehash:
                    #print("%d Keyhash:%s Nodehash:%s" % (i,keyhash,nodehash))
                    return self.ring[nodehash]
                else:
                    continue
            if i==len(self._sorted_keys):
                #print("None Keyhash:%s Nodehash:%s" % (keyhash,self._sorted_keys[0]))
                return  self.ring[self._sorted_keys[0]]
    
        def count_server(self,number):
            '''server_list用于存放重复出现的server,server_counnt用于统计出现频数'''
            server_list = []
            server_count = {}
            for i in range(number):
                kei = "key_%s" % i
                server = self.get_node(kei)
                server_list.append(server)
            for m in set(server_list):
                server_count[m] = server_list.count(m)
            '''根据字典的键进行排序,如果需要逆序则添加 reverse=True'''
            server_count=dict(sorted(server_count.items(), key=lambda e: e[0]))
            print("ServerCount:", server_count)
    
    
    ini_servers = [
        '127.0.0.1:1',
        '127.0.0.1:2',
        '127.0.0.1:3',
        '127.0.0.1:4',
        #'127.0.0.1:7005',
    ]
    h=conhashnorep(ini_servers)
    print(h.ring)
    
    """构建一些object来观察会分配到哪一个节点"""
    #for i in range(20):
    part_servers=['127.0.0.2:1','127.0.0.2:2']
    h.count_server(200)
    h.add_nodes(part_servers)
    h.count_server(200)
    h.remove_nodes(['127.0.0.1:1','127.0.0.1:2'])
    h.count_server(200)

    执行程序,得到如下结果

    查看可知,在直接删除‘127.0.0.1:1’,‘127.0.0.1:2’两个节点后,原本属于这两个节点的key并没有较均匀的分散到其他节点,而是直接积压在‘127.0.0.2:1’,‘127.0.0.2:2’这两个新节点上。

    一致性哈希(设置虚拟节点)

    """对一致性hash进行学习,构造没有vnode的hash,增加和删除节点以进行观察,会产生对应的雪崩效应"""
    from zlib import crc32
    
    class conhashnorep(object):
        def __init__(self,nodes=None,replicas=5):
            """此处nodes代表需要初始化的node列表,为进行对比先提供虚拟节点副本数,ring是存储hash-node的字典,key是存储所有hash值的列表"""
            self.nodes=nodes
            self.replicas=replicas
            self.ring={}
            self._sorted_keys=[]
            self.add_nodes(nodes)
    
        def _add_node(self,node):
            for i in range(self.replicas):
                bnode="%s_vnode%s" % (node,i)
                bnode = bytes(bnode, encoding="utf8")
                nodehash = abs(crc32(bnode))
                self.ring[nodehash] = node
                self._sorted_keys.append(nodehash)
            self._sorted_keys.sort()
    
        def add_nodes(self,nodes):
            if nodes:
                for node in nodes:
                    self._add_node(node)
    
        def remove_nodes(self,nodes):
            """对于remove的操作,如果直接操作已经产生的ring字典,会比较麻烦,因为ring是{hashnode:node}的键值对形式,
            直接处理涉及到字典直接查找值ring.values()/ring.keys(),以及通过值来remove(key)的操作,太麻烦"""
            if nodes:
                for node in nodes:
                    for i in range(self.replicas):
                        bnode = "%s_vnode%s" % (node, i)
                        bnode = bytes(bnode, encoding="utf8")
                        nodehash = abs(crc32(bnode))
                        del self.ring[nodehash]
                        self._sorted_keys.remove(nodehash)
    
        def get_node(self,key):
            bkey=bytes(key,encoding="utf8")
            keyhash=abs(crc32(bkey))
            i=0
            for nodehash in self._sorted_keys:
                i += 1
                if keyhash < nodehash:
                    #print("%d Keyhash:%s Nodehash:%s" % (i,keyhash,nodehash))
                    return self.ring[nodehash]
                else:
                    continue
            if i==len(self._sorted_keys):
                #print("None Keyhash:%s Nodehash:%s" % (keyhash,self._sorted_keys[0]))
                return  self.ring[self._sorted_keys[0]]
    
        def count_server(self,number):
            '''server_list用于存放重复出现的server,server_counnt用于统计出现频数'''
            server_list = []
            server_count = {}
            for i in range(number):
                kei = "key_%s" % i
                server = self.get_node(kei)
                server_list.append(server)
            for m in set(server_list):
                server_count[m] = server_list.count(m)
            '''根据字典的键进行排序,如果需要逆序则添加 reverse=True'''
            server_count=dict(sorted(server_count.items(), key=lambda e: e[1],reverse=True))
            print("ServerCount:", server_count)
    
    
    ini_servers = [
        '127.0.0.1:1',
        '127.0.0.1:2',
        '127.0.0.1:3',
        '127.0.0.1:4',
        #'127.0.0.1:7005',
    ]
    h=conhashnorep(ini_servers)
    print(h.ring)
    
    """构建一些object来观察会分配到哪一个节点"""
    #for i in range(20):
    part_servers=['127.0.0.2:1','127.0.0.2:2']
    h.count_server(200)
    h.add_nodes(part_servers)
    h.count_server(200)
    h.remove_nodes(['127.0.0.1:1','127.0.0.1:2'])
    h.count_server(200)

    运行结果如下:

    可见,去掉‘127.0.0.1:1’和‘127.0.0.1:2’两个节点,并没有完全积压到某一个节点,相比较而言做了一定的分散。

    后续

    一致性hash的使用在分布式系统的实现应该比较常见,比如分布式存储,分布式计算(多队列多任务),在实际的使用中那种数据结构会取得比较好的效率还未实践,本文代码参考了python官方的hash ring的实现,也可以考虑使用一些别的东西,比如memcache(这个我个人感觉类似于一个代码加速器或者数据库中间件,但是可能这样的理解有问题)。也可以考虑用别的方式来实现一致性hash(存储量或者任务量达到一定程度,且是交互式查询时需要提升性能),例如map,例如红黑树,以前学艺不精,现在慢慢捡以前丢的东西,后续有时间有机会再来补充。

    展开全文
  • 文章目录一致性哈希一致性 hash —— 基础类型一致性 hash —— 虚拟节点Golang 实现结构定义hash 环的初始化hash 环添加节点一致性 hash 请求 一致性哈希 简单哈希 hash(object)%N 是最常用的算法,这种均衡性可能...
  • import java.util.LinkedList; import java.util.List; import java.util.SortedMap; import java.util.TreeMap;...分布式缓存一致性hash算法,带虚拟节点 @author lisl */ public class HashCacheT...
  • public class ConsistentHashingWithVirtualNode { ... //待添加入Hash环的服务器列表 private static String[] servers = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111", "192.168.0.3:11...
  • 一致性hash增加节点问题

    千次阅读 2011-10-25 21:48:58
    最近在看关于一致性hash,其原理就是不仅对数据的key进行hash,同时对节点也进行hash,比如使用节点的ip值来进行hash,然后看key的hash值落在节点的hash值的区间来确定这个key在哪个节点上(我们的应该是数据会发到...
  • 考虑到以往的技术应用,准备参考Mycat的一致性hash算法,实现此功能。查阅网上资料和Mycat一致性hash算法的源码后,编写了一个简单的实现算法。 具体实现如下: 缓存实现参考:...
  • 一致性HASH算法(虚拟节点)

    千次阅读 2016-07-15 14:00:35
    真实的环境是删除了s2后,所有他的虚拟节点都会马上被删除,虚拟节点上的连接也会重新连接到另一个主机的虚拟节点,不会存在这种中间情况。 以下给出所有的实现代码,大家共同学习: [java]   ...
  • 一致性哈希 虚拟节点

    2019-02-15 18:09:53
    https://www.cnblogs.com/haippy/archive/2011/12/10/2282943.html
  • 一致性hash,讲的不错 https://www.cnblogs.com/yixiwenwen/p/3580646.html https://www.cnblogs.com/xhj123/p/9087532.html
  • 一致性hash 虚拟

    2016-05-12 10:02:20
    比如在Redis分布式缓存设计中,使用一致性Hash进行key分片存储,通过虚拟节点最大化降低添加或删除节点带来的影响。这里强调降低二字,即是它还是有影响的,在一般情况下我们还可以接受。但是某些场景下要求动态扩容...
  • 小白一只,, 最近在看哈希算法,中有提到hash算法的虚拟节点···请大佬···告知。。。一致性hash算法中的虚拟节点是根据什么加的,是如何加的,位置怎么选,加在哪里?···感谢···
  • 一致性哈希+虚拟节点

    2020-10-21 19:07:25
    五、虚拟节点解决数据倾斜问题 原文链接:https://www.jianshu.com/p/735a3d4789fc 一、为什么要使用多个服务器 随着系统流量的增大,出现了应用集群。在 Mysql数据库要存储的量达到一个很高的地步的时候,我们会对...
  • srv1转变成srv1-0 和srv1-1 两种地址(也就是两个虚拟节点), 这样srv1 就能得到两个hash值,然后在圆环中占据两个位置,这样就变成了圆环C的情况,这样针对每个service 增加更多的虚拟节点就能实现按照权重的分配...
  • 一致性哈希算法——虚拟节点 一致性哈希算法是分布式系统中常用的算法。比如,一个分布式的存储系统,要将数据存储到具体的节点上,如果采用普通的hash方法,将数据映射到具体的节点上,如key%N,key是数据的key,N...
  • 采用固定哈希算法平衡负载 在大规模的缓存应用中,应运而生了分布式缓存系统。...比如集群中可用机器适量为N,那么key值为K的的数据请求很简单的应该路由到hash(K) mod N对应的机器。但是在一些高速
  • /// 一致性HASH,解决传统HASH的扩容难的问题 /// 注:常用与分布式缓存与分表 /// </summary> /// <typeparam name="T">泛型</typeparam> public class ConsistentHash<T> ...
  • 一致性hash算法

    千次阅读 2019-04-27 22:47:14
    一致性hash算法Hash算法的作用Hash算法的冲突一致性hash算法一致性hash算法的原理容错性虚拟节点 Hash 算法也叫做散列算法,他可以让任意长度的数据M映射成为长度固定的值H。 Hash算法的作用 Hash算法的第一个作用...
  • 一致性Hash简单实现

    2011-07-08 13:13:50
    简单模拟实现一致性Hash,透过虚拟节点映射至实际结点,解决一致性Hash的单调性和平衡性问题。
  • 一致性hash

    2019-02-20 22:36:21
    先构造一个长度为2^32的整数环(这个环被称为一致性Hash环),根据节点名称的Hash值(其分布为[0, 232-1])将服务器节点放置在这个Hash环上,然后根据数据的Key值计算得到其Hash值(其分布也为[0, 232-1]),接着在...
  • Cassandra的一致性哈希(Consistent Hashing)和虚拟节点(Virtual Nodes)的关系一致性哈希所要解决的问题一般的哈希算法存在的问题是:当“模”发生变化时,所有的值都需要重新哈希,而一致性哈希算法的特别之处就是...
  • 图解一致性hash算法和实现

    千次阅读 2019-05-18 18:35:13
    一致性hash算法可以有效地解决分布式存储结构下动态增加和删除节点所带来的问题。 在Memcached、Key-Value Store、Bittorrent DHT、LVS中都采用了一致性hash算法,可以说一致性hash算法是分布式系统负载均衡的首选...
  • 一致性Hash算法相关

    2019-08-13 15:08:25
    参考: ... ... 1.一致性Hash解决的核心问题是:当某个集群中的server发生局部改变时,尽量少的移动请求与服务器的映射关系...2.图解一致性Hash环对理解很重要,尤其是当加入虚拟节点后的映射关系对应。 3.虚拟节点的出...
  • 先构造一个长度为2^32的整数环(这个环被称为一致性Hash环),根据节点名称的Hash值(其分布为[0, 2^32-1])将缓存服务器节点放置在这个Hash环上,然后根据需要缓存的数据的Key值计算得到其Hash值(其分布也为[0, 2^...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,681
精华内容 12,272
关键字:

一致性hash虚拟节点