Introduction Nowadays, the on-demand virtualized resources are offered without any delay, according to actual requirements in real-time. To make the cloud platform more flexible and cost efficient. A few management frameworks are proposed to enable cluster resource sharing across workloads. Most are suitable in building Infrastructure-as-a-servcie(Iaas) cloud service model. To make the cloud platform more flexible and cost efficent, virtual resources may be added or removed from the cloud platform at any time....

场景描述 假设，我们有三台缓存服务器，用于缓存图片，我们为这三台缓存服务器编号为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....

流数据处理对于现今的大数据来说是一件大事，并且有充分的理由。其中： 企业渴望获得更及时的数据，切换到流处理是实现更低延迟的好方法。 现代业务中越来越常见的大量无限数据集使用专为这种永无止境的数据量而设计的系统更容易被驯服。 在数据到达时处理数据，随着时间的推移将工作负载分布得更均匀，从而产生更一致且可预测的资源消耗。 Background 首先，我将介绍一些重要的背景信息，这些信息将有助于构思我想讨论的其他主题。我们将在三个特定的部分完成此操作： Terminology: 精确地谈论复杂的话题需要对术语进行精确的定义。对于一些在当前使用中已经超负荷解释的术语，我会尽力确定我说的时候的意思。 Capabilities: 我会谈谈流媒体系统的常识缺点。我还会提出我认为数据处理系统制造商需要采用的思维框架，以满足现代数据用户的需求。 Time domains: 我将介绍与数据处理相关的两个主要时间领域，展示它们之间的关系，并指出这两个领域带来的一些困难。 Terminology: What is streaming? 问题的症结在于许多应该由它们所描述的东西（例如，无限数据处理，近似结果等）已经通过它们历史上已经完成的方式来口头描述（即，通过流式传输执行引擎）。术语精确度的缺乏决定了流传输的真正含义，并且在某些情况下，流传输系统本身的负担会加重，这意味着它们的能力限于经常被描述为 “流” 的特性，如近似或推测性结果。鉴于精心设计的流媒体系统与任何现有的批量引擎一样能够（技术上更加如此）产生正确，一致，可重复的结果，因此我更愿意将术语 “流” 分离为一个非常具体的含义：一种数据处理引擎设计时考虑了无限的数据集。而已。 （为了完整性，或许值得一提的是，这个定义包括真正的流媒体和微批量实现。） 这里有几个我经常听到的，每个都有更精确的描述性术语: Unbounded data: 一种不断增长的，实质上无限的数据集。这些通常被称为 “流数据”。然而，流应用或批处理术语在应用于数据集时存在问题，因为如上所述，它们意味着使用某种类型的执行引擎来处理这些数据集。所讨论的两类数据集之间的关键区别实际上是它们的有限性，因此最好用描述它们的术语来描述它们。因此，我将把无限的 “流式” 数据集称为无界数据，将有限的 “批处理” 数据集称为有界数据。 Unbounded data processing: 一种持续的数据处理模式，适用于上述类型的无界数据。尽管我个人喜欢使用术语流来描述这种类型的数据处理，但在这种情况下它的使用又意味着使用流式执行引擎，这充其量是误导性的; 由于批量系统首先被构想出来（相反，设计良好的流式系统不仅能够处理超过有界数据的 “批量” 工作负载），所以批处理引擎的重复运行已用于处理无界数据。因此，为了清楚起见，我将简单地称之为无限数据处理。 Low-latency, approximate, and/or speculative results: 这些类型的结果通常与流引擎相关联。事实上，批处理系统传统上没有考虑到低延迟或推测性结果，这是一个历史人为因素，仅此而已。当然，批量发动机如果有指导，完全可以产生近似的结果。因此，与上述条款一样，将这些结果描述为它们（低延迟，近似和 / 或推测）比通过历史流式（通过流式引擎）如何表现要好得多。 从这里开始，任何时候我使用术语 “streaming”，你都可以安全地假设我的意思是一个为无界数据集设计的执行引擎，仅此而已。当我指上述任何其他术语时，我将明确地说出无限数据，无限数据处理或低延迟 / 近似 / 推测结果。这些是我们在 Cloud Dataflow 中采用的术语，我鼓励其他人采取类似的立场。 On the greatly exaggerated limitations of streaming: 接下来，让我们谈一谈流式系统可以做什么和不可以做什么，重点放在能做的上; 我想在这些帖子中看到的最重要的事情之一就是设计良好的流式传输系统的性能如何。流式传输系统长期以来一直处于一个提供低延迟，不准确 / 推测结果的利基市场，通常与更强大的批处理系统相结合以提供最终的正确结果，即 Lambda 架构。 对于那些还不熟悉 Lambda Architecture 的人来说，其基本思想是，您可以在批处理系统旁边运行流式处理系统，两者执行基本相同的计算。流式传输系统为您提供低延迟，不准确的结果（或者因为使用近似算法，或者因为流式传输系统本身不能提供正确性），并且一段时间后，批处理系统会一路滚动并为您提供正确的输出。最初由 Twitter 的 Nathan Marz（Storm 的创始人）提出，它最终取得了相当的成功，因为它实际上是一个很棒的想法。流媒体引擎在正确性部门中有点令人失望，批量引擎如你所期望的那样固有地笨重，所以 Lambda 给了你一种方法来让你的谚语蛋糕也吃掉。不幸的是，维护 Lambda 系统非常麻烦：您需要构建，配置和维护两个独立版本的管道，然后以某种方式合并最后两条管道的结果。...

introduction As we all know, python is a dynamic language and dynamic typing can be flexible, powerful, convenient and easy. But with your project growing, dynamic typing is not always the best approach. As an opposite, static typing can make programs easier to understand and maintain. Type declarations can serve as machine-checked documentation. This is important as code is typically read much more often than modified, and this is especially important for large and complex programs....