system

场景描述 假设，我们有三台缓存服务器，用于缓存图片，我们为这三台缓存服务器编号为0号、1号、2号，现在，有3万张图片需要缓存，我们希望这些图片被均匀的缓存到这3台服务器上，以便它们能够分摊缓存的压力。也就是说，我们希望每台服务器能够缓存1万张左右的图片，那么，我们应该怎样做呢？如果我们没有任何规律的将3万张图片平均的缓存在3台服务器上，可以满足我们的要求吗？可以！但是如果这样做，当我们需要访问某个缓存项时，则需要遍历3台缓存服务器，从3万个缓存项中找到我们需要访问的缓存，遍历的过程效率太低，时间太长，当我们找到需要访问的缓存项时，时长可能是不能被接收的，也就失去了缓存的意义，缓存的目的就是提高速度，改善用户体验，减轻后端服务器压力，如果每次访问一个缓存项都需要遍历所有缓存服务器的所有缓存项，想想就觉得很累，那么，我们该怎么办呢？原始的做法是对缓存项的键进行哈希，将hash后的结果对缓存服务器的数量进行取模操作，通过取模后的结果，决定缓存项将会缓存在哪一台服务器上. 那么，当我们访问任意一个图片的时候，只要再次对图片名称进行上述运算，即可得出对应的图片应该存放在哪一台缓存服务器上，我们只要在这一台服务器上查找图片即可，如果图片在对应的服务器上不存在，则证明对应的图片没有被缓存，也不用再去遍历其他缓存服务器了，通过这样的方法，即可将3万张图片随机的分布到3台缓存服务器上了，而且下次访问某张图片时，直接能够判断出该图片应该存在于哪台缓存服务器上. but… 如果3台缓存服务器已经不能满足我们的缓存需求，那么我们应该怎么做呢？没错，很简单，多增加两台缓存服务器不就行了，假设，我们增加了一台缓存服务器，那么缓存服务器的数量就由3台变成了4台，此时，如果仍然使用上述方法对同一张图片进行缓存，那么这张图片所在的服务器编号必定与原来3台服务器时所在的服务器编号不同，因为除数由3变为了4，被除数不变的情况下，余数肯定不同，这种情况带来的结果就是当服务器数量变动时，所有缓存的位置都要发生改变，换句话说，当服务器数量发生改变时，所有缓存在一定时间内是失效的，当应用无法从缓存中获取数据时，则会向后端服务器请求数据，同理，假设3台缓存中突然有一台缓存服务器出现了故障，无法进行缓存，那么我们则需要将故障机器移除，但是如果移除了一台缓存服务器，那么缓存服务器数量从3台变为2台，如果想要访问一张图片，这张图片的缓存位置必定会发生改变，以前缓存的图片也会失去缓存的作用与意义，由于大量缓存在同一时间失效，造成了缓存的雪崩，此时前端缓存已经无法起到承担部分压力的作用，后端服务器将会承受巨大的压力，整个系统很有可能被压垮，所以，我们应该想办法不让这种情况发生，但是由于上述HASH算法本身的缘故，使用取模法进行缓存时，这种情况是无法避免的，为了解决这些问题，一致性哈希算法诞生了 一致性哈希算法 Consistent hashing 算法早在1997年就在论文《Consistent hashing and random trees》中提出 这个算法有一个环形hash空间的概念，我们先来了解一下环形hash空间： 通常hash算法都是将value映射在一个32位的key值当中，那么把数轴首尾相接就会形成一个圆形，取值范围为0 ~ 2^32-1，这个圆形就是环形hash空间。如下图: 只考虑4个对象Object1 ~ Object4 首先通过hash函数计算出这四个对象的hash值key，这些对象的hash值肯定是会落在上述中的环形hash空间范围上的，对象的hash对应到环形hash空间上的哪一个key值那么该对象就映射到那个位置上，这样对象就映射到环形hash空间上了。 然后就是把cache映射到环形hash空间，cache就是我们的redis服务器： 计算出cache的hash值之后，就和对象一样映射到hash环形空间中对应的key上 可以看到，Cache和Obejct都映射到这个环形hash空间中了，那么接下来要考虑的就是如何将object映射到cache中。其实在这个环形hash空间进行一个顺时针的计算即可，例如key1顺时针遇到的第一个cache是cacheA，所以就将key1映射到cacheA中，key2顺时针遇到的第一个cache是cacheC，那么就将key2映射到cacheC中，以此类推。 如果某一个cache被移除之后，那么object会继续顺时针寻找下一个cache进行映射。例如，cacheB被移除了，映射在cacheB中的object4就会顺时针往下找到cacheC，然后映射到cacheC上。 所以当移除一个cacheB时所影响的object范围就是cacheB与cacheA之间的那一段范围，这个范围是比较小的。如下图所标出的范围： 而当增加一个cache节点时也是同理，例如，在acheC和cacheB之间增加了一个cacheD节点，那么object2在顺时针遇到的第一个cache就是cacheD，此时就会将obejct2映射到cacheD中。如下图： 同样的，增加cache节点所影响的范围也就是cacheD和cacheB之间的那一段范围。如下图所标出的范围： 我们假设了所有的cache节点都是在环形hash空间上分布均匀的, but… 现实中，就有可能会出现cache节点无法均匀的分部在环形hash空间上 可以看到，A、B、C节点都挤在了一块，按顺时针来计算，就会有大量的数据（object）映射到A节点上，从上图中来看就会有一大半的数据都映射到A节点上，那么A节点所承载的数据压力会十分大，B、C节点则无法得到很好的利用，几乎等同闲着没事干。这就是Hash倾斜性所导致的现象，无法保证在环形hash空间上绝对的分布均匀。 为了解决Hash倾斜性的问题，redis引入了虚拟节点的概念，虚拟节点相当于是实际节点的一个影子或者说分身，而且虚拟节点一般都比实际节点的数量要多。引入虚拟节点后，object不再直接映射到实际的cache节点中，而是先映射到虚拟节点中。然后虚拟节点会再进行一个hash计算，最后才映射到实际的cache节点中。所以虚拟节点就是对我们的实际节点进行一个放大，如下图： 放到环形hash空间上进行表示，就是这样的，浅色为虚拟节点，深色为实际节点： 如上可以看到，这下分布就均匀了。这里只是作为演示，实际情况中的节点会更多，虚拟节点和实际节点是存在一定比例的。而且随着实际节点的增加，环形hash空间上的分布就会越来越均匀，当移除或增加cache时所受到的影响就会越小。 Consistent hashing 命中率计算公式： (1 - n / (n + m)) * 100% n = 现有的节点数量 m = 新增的节点数量 Ref http://blog.51cto.com/zero01/2115528

Rate limit 限流技术 在高并发系统中经常使用三种技术保护系统：缓存，降级和限流。缓存的目的是提升系统访问速度和增大系统能处理的容量，降级是当服务出问题是暂时屏蔽掉，等高峰期后或问题解决后在重启，然而针对有些场景并不能用缓存和降级来解决，比如稀缺资源（秒杀，抢购），写服务（评论，下单），频繁的复杂查询（评论的最后几页），这时候 需要限流这项技术来限制这些场景的并发/请求量。限流的目的是通过对并发访问/请求进行限速或者一个时间窗口内的的请求进行限速来保护系统，一旦达到限制速率则可以拒绝服务（定向到错误页或告知资源没有了）、排队或等待（比如秒杀、评论、下单）、降级（返回兜底数据或默认数据，如商品详情页库存默认有货） 常见限流算法 （算法层面限流） 计数器， 令牌桶， 漏桶 计数器 主要用来限制总并发数，比如数据库连接池，线程池，秒杀的并发数；超过了瞬时请求数或者在一定时间段内的请求数设定的阈值，则进行简单粗暴的限流，主要针对的还是总体的请求数量，而不是考虑的平均速率的限流。 令牌桶 Token Bucket 随着时间流逝,系统会按恒定1/QPS时间间隔(如果QPS=100,则间隔是10ms)往桶里加入Token(想象和漏洞漏水相反,有个水龙头在不断的加水),如果桶已经满了就不再加了.新请求来临时,会各自拿走一个Token,如果没有Token可拿了就阻塞或者拒绝服务.令牌桶的另外一个好处是可以方便的改变速度. 一旦需要提高速率,则按需提高放入桶中的令牌的速率. 一般会定时(比如100毫秒)往桶中增加一定数量的令牌, 有些变种算法则实时的计算应该增加的令牌的数量 长期来看，符合流量的速率是受到令牌添加速率的影响，被稳定为：r 因为令牌桶有一定的存储量，可以抵挡一定的流量突发情况 M是以字节/秒为单位的最大可能传输速率。 M>r T max = b/(M-r) 承受最大传输速率的时间 B max = T max * M 承受最大传输速率的时间内传输的流量 Guava RateLimiter提供了令牌桶算法实现：平滑突发限流(SmoothBursty)和平滑预热限流(SmoothWarmingUp)实现。 漏桶 Leaky Bucket 漏桶(Leaky Bucket)算法思路很简单,水(请求)先进入到漏桶里,漏桶以一定的速度出水(接口有响应速率),当水流入速度过大会直接溢出(访问频率超过接口响应速率),然后就拒绝请求,可以看出漏桶算法能强行限制数据的传输速率. 两桶对比 令牌桶是按照固定速率往桶中添加令牌，请求是否被处理需要看桶中令牌是否足够，当令牌数减为零时则拒绝新的请求； 漏桶则是按照常量固定速率流出请求，流入请求速率任意，当流入的请求数累积到漏桶容量时，则新流入的请求被拒绝； 令牌桶限制的是平均流入速率（允许突发请求，只要有令牌就可以处理，支持一次拿3个令牌，4个令牌），并允许一定程度突发流量； 漏桶限制的是常量流出速率（即流出速率是一个固定常量值，比如都是1的速率流出，而不能一次是1，下次又是2），从而平滑突发流入速率； 令牌桶允许一定程度的突发，而漏桶主要目的是平滑流入速率； 两个算法实现可以一样，但是方向是相反的，对于相同的参数得到的限流效果是一样的。 应用级限流 一般来说，对于一个应用系统都会有极限并发数和请求数，TPS和QPS。如果超过了阈值则系统会无法响应或者崩溃，所以一般在进行开发大规模系统的时候，要设置过载保护，以免大量请求使系统瘫痪。 限流总资源数。 有的资源是稀缺资源（如数据库连接、线程）， 可以使用池化技术来限制总资源数：连接池、线程池。比如分配给每个应用的数据库连接是100，那么本应用最多可以使用100个资源，超出了可以等待或者抛异常。 如果接口可能会有突发访问情况，但又担心访问量太大造成崩溃，如抢购业务；这个时候就需要限制这个接口的总并发/请求数总请求数了；因为粒度比较细，可以为每个接口都设置相应的阀值。可以使用Java中的AtomicLong进行限流： try { if(atomic.incrementAndGet() > 限流数) { //拒绝请求 } //处理请求 } finally { atomic.decrementAndGet(); } 适合对业务无损的服务或者需要过载保护的服务进行限流，如抢购业务，超出了大小要么让用户排队，要么告诉用户没货了，对用户来说是可以接受的。而一些开放平台也会限制用户调用某个接口的试用请求量，也可以用这种计数器方式实现。这种方式也是简单粗暴的限流，没有平滑处理，需要根据实际情况选择使用； 2....