限流系统如何发现系统的热点

标签: Uncategorized | 发表时间:2016-02-01 05:42 | 作者:jm
分享到:
出处:http://jm-blog.aliapp.com

限流系统是对资源调用的控制组件,主要涵盖授权、限流、降级、调用统计等功能模块。限流系统有两个基础概念:资源和策略,对特定的资源采取不同的控制策略,起到保障应用稳定性的作用。限流系统提供了多个默认切入点覆盖了大部分使用场景,保证对应用的低侵入性;同时也支持硬编码或者自定义aop的方式来支持特定的使用需求。限流系统提供了全面的运行状态监控,实时监控资源的调用情况(qps、rt、限流降级等信息)。

如何利用限流系统的特性,来统计热点呢?在这里,我们主要介绍一下,限流系统是如何来判断热点的,它的工作原理是什么,它的性能如何;它目前已经在哪些场景里面使用。

1. 热点的特性

a) 海量的统计基数

可能的热点分为两种,一种是事前已知的(例如营销人员的已经整理出秒杀商品的列表),另外一种是突发的,不可以预计的(例如被刷单的商品,或者是黑马产品)。对于前面一种,只需要计算这些已知的列表即可,但是对于后者,由于基数是海量的,举个例子,如果有一个方法,它传入的参数是商品id, 这个商品的id以淘宝的规模来说,是上亿的。如果把所有的商品id都记录统计起来,再进行排序,统计出热点,这对于实时的工具来说,是不可行的。所以为了解决热点统计,我们必须找到一个好的数据结构,这个结构能够仅保存最常常被访问的一定数量商品id,并且可以控制结构的大小,统计量。这是非常重要的一个步骤。

b) 统计热点的单位时间的维度

这里有一个必须强调的概念: 单位时间而不是总访问量。 打个比方,一个商品,在一小时以内被访问了3600次,但是它很均匀的每秒被访问一次,那么这个商品可能在系统的承受范围之内,并会对系统带来损伤;而另外一个商品,它一小时被访问了60次,但都落在同一秒,那么这个商品可能就是一个热点商品。对于”单位时间”的定义,是决策一个参数是否成为热点的一个重要的因素;如果太粗,必然会带来毛刺,导致系统性能不平滑;如果太细,会给性能带来挑战。

c) 在分布式系统给统计带来的挑战

热点的统计范围可能是单机,也可能是集群。如何能快速的在集群中统计,并且让限流规则在单机上生效,是非常重要的。

2. 如何解决上述问题

2.1 首先,找到一个可行的数据结构

这个结构必须满足访问修改快速,并发性好,占用内存空间少,存储的个数大小可控制,并且可以驱逐访问量少的entry,从而可以达到实时统计热点的查询数字。

其实,业界有一个现成的好结构。它就是google团队用于guava里的ConcurrentLinkedHashMap (http://code.google.com/p/concurrentlinkedhashmap)。

它有下面几个特点:

2.1.a 支持并发。它是实现了ConcurrentMap接口的。基本上它的实现是遵循concurrentMap的思想的。这里就不多赘述。

2.1.b 它把我们普通concurrenthashmap的segments用一个额外的双链表维护起来,通过操作这个链表,里面的entry可以在O(1)的时间之类删除或者重新排序。当一个entry被访问,则被移动到表头;当这个map的容量超过预设,则移除位于链表尾的entry。这样就可以保证表头是最新被使用的entry,表尾是最近最少被使用的entry

94cd7120395086cf4803992008b7f17bda28e7c2

2.1.c 从另外一个角度来说,可以把ConcurrentLinkedHashMap 分成两个view. 一个是同步的,一个是异步的。Hashtable对于调用方来说是同步的,链表对于调用方式不透明的,异步的。

9d67db20c4f8d60978ef73f762bdcafc25835e1c

 

2.1.d 性能和concurrenthashmap的比较, 肯定比concurrenthashmap差,但是属于可以忍受的范围。下面是官方给出的数据

539d274b766dbfacb97cfc66f24e9658bef7081f

综上所述,我们可以利用这个LRU concurrent map link,保证我们在单位时间内,仅保存有限数量访问量较高的key, 最近比较少访问的key,我们则可以认为它不是热点,当map的Size达到上限之后,清除这个key

2.2 统计单位时间的维度

现在我们来看第二个问题,如何统计单位时间的key的qps. 其实这个正是限流系统的拿手好戏,用动态滑动窗口平滑的统计qps.

简单的说,限流系统为每个簇点(可以简单的理解为需要统计的方法),做了一个滑动窗口。更具体的说,即限流系统把采样窗口长度设为2秒,这个采样窗口又被分割为20个格子。通过用一定的算法来统计这20个格子的平均滑动窗口累积平均值来进行决策。
为什么采用平均滑动窗口累计平均值是为了削平毛刺qps(在某个点突发的qps)对整体的影响。该公式如下:
e013a13198b40fee7e1e6930140eb2dd615d7e6b
更具体的说明在:  http://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average 可以查到。

说到这里,聪明的读者应该早就猜到了,限流系统通过把两个利器结合起来,即滑动窗口和google concurrent link hashmap,可以统计在固定的时间,最常常使用的参数的值。
限流系统数据结构如下所示:

f23bcb04935c288c72e159bc5d9ee820713dccbb

具体的代码在:  http://gitlab.alibaba-inc.com/middleware-asp/限流系统 欢迎大家来指正

2.3 如何解决集群的挑战

2.3.1 幸运的是,限流系统天生自带获取簇点qps的功能

使用过限流系统的人都会发现,8719这个端口是被限流系统占用了的。通过这个端口,我们可以用获取到簇点的qps统计信息。有了这个“后门”,我们就可以轻松快速的获取到qps的信息了

2.3.2 如何在大集群里汇总这些qps的信息

接下来要解决的问题就是,如何在上千台机器里面快速汇总这些信息。还好之前我们在做2.0.7的集群统计的时候,有了一定的经验。 这个算法后来也用在了预案分配巨大的url task中。简单的说,就是用一个队列来放任务,多个线程来执行任务,一个线程来merge取回的结果。通过使用这个方法,一个比较大的集群,例如buy等,2秒可以返回统计结果。

b7969b7cd134ab8ede52777876d7e595471d4999

有了集群的总体汇总信息之后,我们再将这个信息利用diamond来推广到具体的机器上去。这样的延迟大概是2-3s左右。

3 总结以及限流系统性能报告:

简单的说,存放一个这样的结构,大概大小是8k. 它的默认参数是每个簇点的存放2s的滑动窗口,20个格子,每个格子最多可以保存200个参数,那么在最坏的情况下,这个结构的大小将会是8k+4000个参数大小。

吞吐量在我的日常机器上是29W,在生产机上应该会更好。

相关 [系统 发现 系统] 推荐:

限流系统如何发现系统的热点

- - 阿里中间件团队博客
限流系统是对资源调用的控制组件,主要涵盖授权、限流、降级、调用统计等功能模块. 限流系统有两个基础概念:资源和策略,对特定的资源采取不同的控制策略,起到保障应用稳定性的作用. 限流系统提供了多个默认切入点覆盖了大部分使用场景,保证对应用的低侵入性;同时也支持硬编码或者自定义aop的方式来支持特定的使用需求.

西门子工业控制系统发现更多漏洞

- 龙 - Solidot
在赌城举行的年度Black Hat会议上,安全研究人员Dillon Beresford报告在西门子的工业控制系统中发现了更多漏洞,包括可被用于远程拒绝服务的漏洞、硬编码管理密码、甚至是复活节彩蛋程序. 此前,著名的Stuxnet就是以西门子系统中的PLC为目标. 研究人员表示已经向西门子计算机紧急反应小组报告了他的发现,而西门子表示正准备发布补丁修复部分漏洞.

NASA发现众多适宜生命的行星系统

- Icat - Solidot
NASA专门寻找类地行星的太空望远镜开普勒发现了可信证据,证明太空中有无数适宜生命居住的行星. 开普勒望远镜发现了第一颗大小与地球相近的候选行星,以及位于适宜生命居住区域的行星. 开普勒望远镜至今发现了1,235颗候选行星,其中68颗大小类似地球,288颗超级地球大小,662颗海王星大小,165颗木星大小,19颗大于木星.

壳系统

- Vernsu - It Talks-魏武挥的blog
经常有人被我问到“你用什么浏览器”时的答案是:傲游啦360啦,但事实上,这些都不是真正的浏览器,从技术角度讲,充其量只是在IE浏览器上加一个壳罢了. 在国外,壳浏览器是以“皮肤”的形式存在,纯属为了美化浏览器而用. 但在中国,壳浏览器成了一门生意. 奇虎的主要收入来源并非来自那个由于一场商战而赫赫有名的安全卫士,而是来自于360浏览器(它有两个版本,分别以IE和Chrome为内核).

秒杀系统

- - 开源软件 - ITeye博客
秒杀系统架构分析与实战. (反馈非常好的文章,推荐). (1)查询商品;(2)创建订单;(3)扣减库存;(4)更新订单;(5)付款;(6)卖家发货. (1)低廉价格;(2)大幅推广;(3)瞬时售空;(4)一般是定时上架;(5)时间短、瞬时并发量高;. 假设某网站秒杀活动只推出一件商品,预计会吸引1万人参加活动,也就说最大并发请求数是10000,秒杀系统需要面对的技术挑战有:.

研究人员发现无法躲避的在线跟踪系统

- Gnauk - Solidot
加州伯克利大学的研究人员曝光了一种用户无法避开的在线跟踪系统,即使他们屏蔽了cookies,或者是使用浏览器的隐身模式. KISSmetrics是被用于跟踪用户访问数量,所访问网页,从何处点击进入网站的路径等的在线服务,该公司声称它的功能比Google Analytics更全面. 但研究人员发现,用户无法选择退出KISSmetrics的跟踪系统.

Ext文件系统

- Haides - 博客园-首页原创精华区
  虽然从Ext2到Ext4,找数据的方式发生了变化,但是,磁盘的布局还是非常相似的. 其实这个东西也不需要变化,因为现在也没什么特别巧妙的方式,而且磁盘的吞吐量、效率的瓶颈也不在这里. 当然,这里排除那些根据自身文件特点设计的数据库,毕竟还是为了支持通用文件.   Boot在第一个块,放的应该是引导程序,超级块就放在了第二个块上,如果不是可以在mount的时候通过参数sb来设置.

HBase 系统架构

- - 博客园_首页
HBase是Apache Hadoop的数据库,能够对大型数据提供随机、实时的读写访问. HBase的目标是存储并处理大型的数据. HBase是一个开源的,分布式的,多版本的,面向列的存储模型. 5 可在廉价PC Server搭建大规模结构化存储集群. HBase是Google BigTable的开源实现,其相互对应如下:.

Linux系统监控

- - CSDN博客系统运维推荐文章
查看所有的进程和端口使用情况:. 查看nginx并发(连接数)进程数:. 查看当网络连接状态中,已建立连接的数量:. 查看系统tcp连接中各个状态的连接数. 输出每个ip的连接数,以及总的各个状态的连接数. df -hl 查看磁盘使用情况 . df -hl 查看磁盘剩余空间. df -h 查看每个根路径的分区大小.

mysql 权限系统

- - 数据库 - ITeye博客
mysql 权限系统控制一个用户是否能进行连接,以及连接后能够针对那些对象进行什么操作. mysql权限控制包含两个阶段. 2:检查用户是否具有所执行动作的权限. 本文实例,运行于 MySQL 5.0 及以上版本. MySQL 赋予用户权限命令的简单格式可概括为:. 一、grant 普通数据用户,查询、插入、更新、删除 数据库中所有表数据的权利.