文档章节

电商课题I:集群环境下业务限流

旁观者-郑昀
 旁观者-郑昀
发布于 2012/11/24 13:59
字数 1757
阅读 113
收藏 7

@郑昀汇总 

创建日期:20120925

关键词索引:
令牌桶算法,漏桶算法

背景:
防注册机、秒杀器或扫号等常见电商流量过滤技术,一般具有如下要求:
1) 高性能。算法简单高效,能对HTTP Requests进行实时在线处理。
2) 分类错误率低。尤其是尽量保证不误杀正常顾客访问。
3) 鲁棒性强。由于双方攻防的对抗性很强,所以算法必须适应各种类型的攻击情形(包括DDoS攻击)。
 
课题1:
对网站某一个URL/表单提交/Ajax请求的访问进行实时检测,找出过于频繁请求的ip,对这些ip的访问频率进行限制。
 
课题2:
对网站开放平台访问,对某一个开放接口的调用,有频次约束,即针对单一App Key不得超过每小时150次调用。
 
翻译一下:
郑昀认为,我们希望限制住的是,在用M度量的任何时间周期内,某一个动作(action)的发生次数N。
 
英文关键词:
rate limiter
rate limiting
throttle limiter
 
要控制的是 Average Rate :
   http://images.cnblogs.com/cnblogs_com/zhengyun_ustc/255879/o_clipboard1211.png
 
推荐采用令牌桶算法的简易实现。
 
参考资料:
一)
Leaky Bucket,漏桶算法。
http://images.cnblogs.com/cnblogs_com/zhengyun_ustc/255879/o_clipboard.png
     图1.1 漏桶算法示意图
如图1所示,桶本身具有一个恒定的速率往下漏水,而上方时快时慢地会有水进入桶中。当桶还未满时,上方的水可以加入。一旦水满,上方的水就无法加入了。桶满正是算法中的一个的关键触发条件(即流量异常判断成立的条件)。
在桶满水之后,常见的两种处理方式为:
1)暂时拦截住上方水的向下流动,等待桶中的一部分水漏走后,再放行上方水。
2)溢出的上方水直接抛弃。
将水看作网络通信中数据包的抽象,则
方式1起到的效果称为Traffic Shaping,
方式2起到的效果称为Traffic Policing(流量策略)。
由此可见,Traffic Shaping 的核心理念是“等待”,Traffic Policing 的核心理念是“丢弃”。它们是两种常见的流速控制方法。
 
再回顾一下上面的图,可以看出算法只需要两个参数:
1)桶漏水的速率
2)桶的大小
 
算法核心:
利用桶模型判断何时的流量达到异常了
 
外延:
1)流量异常时的处理方法:traffic policing v.s. traffic shaping
2)处理的数据包是否定长:定长 v.s. 变长
3)桶的大小是否等同于每个tick放行的水量:as a queue v.s. as a meter
 
二)
Token Bucket,令牌桶算法是网络流量整形(Traffic Shaping)和速率限制(Rate Limiting)中最常使用的一种算法。
漏桶算法不够灵活,因此加入令牌机制。 
基本思想:
令牌桶在 traffic shaping 中的应用思想如下图2.1所示。
http://images.cnblogs.com/cnblogs_com/zhengyun_ustc/255879/o_clipboard121112.png
http://images.cnblogs.com/cnblogs_com/zhengyun_ustc/255879/o_clipboard32.png
    图2.1 CAR和CTS进行流量控制示意图

我们主要关注约定访问速率(CAR)模式,即:

a. 按特定的速率向令牌桶投放令牌;

b.根据预设的匹配规则先对报文进行分类,不符合匹配规则的报文不需要经过令牌桶的处理,直接发送

c.符合匹配规则的报文,则需要令牌桶进行处理。当桶中有足够的令牌则报文可以被继续发送下去,同时令牌桶中的令牌量按报文的长度做相应的减少;

d.当令牌桶中的令牌不足时,报文将不能被发送(即丢弃),只有等到桶中生成了新的令牌,报文才可以发送。这就可以限制报文的流量只能是小于等于令牌生成的速度,达到限制流量的目的。

 
实现:
在数据结构上,没有必要真的实现一个令牌桶。
基于时间的流逝生成受控制数量的令牌即可——以时间的流逝来洗涤旧迹,也就是将两次发包或者收包的间隔和令牌数量联系起来。
 
辅助理解的图形:
http://images.cnblogs.com/cnblogs_com/zhengyun_ustc/255879/o_clipboard33.png
http://images.cnblogs.com/cnblogs_com/zhengyun_ustc/255879/o_clipboard34.png
 
令牌桶和漏桶算法最主要的差别在于: 漏桶算法能够强行限制数据的传输速率,而令牌桶算法能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。  
在令牌桶算法中,只要令牌桶中存在令牌,那么就允许突发地传输数据直到达到用户配置的门限,因此它适合于具有突发特性的流量。 
 
三) http://developer.linkedin.com/documents/throttle-limits  这是常见的开放平台限制请求速率的方式。
LinkedIn 比较好的一点就是把 Application throttlesDeveloper throttles分开了。后者是方便联调测试的。
 
 
 
六)Token Bucket 算法的 Python 实现一:kombu.utils.limits.py
代码:https://github.com/celery/kombu/blob/master/kombu/utils/limits.py
对此实现一个较为早期的解释: http://code.activestate.com/recipes/511490/
即,每次外界调用 _get_tokens 方法时,才会查一下需要追加多少token。
class  TokenBucket ( object ):
     def _get_tokens ( self ):
         if self . _tokens < self . capacity :
             now = time . time ()
             delta = self . fill_rate * ( now - self . timestamp )
             self . _tokens = min ( self . capacity , self . _tokens + delta )
             self . timestamp = now
         return self . _tokens
消耗令牌则是通过 consume 函数,指明本次消耗多少张令牌:
def consume(self, tokens): """Consume tokens from the bucket. Returns True if there were  sufficient tokens otherwise False.""" if tokens <= self.tokens: self._tokens -= tokens else: return False return True
 
七)Rate Limiting 的 memcache-based django  decorator 实现: Rate limiting with memcached
代码实现:https://github.com/simonw/ratelimitcache/blob/master/ratelimitcache.py
 
它明确提出了防字典攻击防扫号的目的。
既可限制住ip,也可限制住其他字段如 username 。
 
八)Token Bucket 算法的node.js实现
jhurliman/node-rate-limiter 给出了一个非常便于理解的 Token 消耗方式:
下面是 150次请求/次 范例,每1次请求消耗1个token:
var RateLimiter = require('limiter').RateLimiter;
// Allow 150 requests per hour (the Twitter search limit). Also understands
// 'second', 'minute', 'day', or a number of milliseconds
var limiter = new RateLimiter(150, 'hour');

// Throttle requests
limiter.removeTokens(1, function(err, remainingRequests) {
  // err will only be set if we request more than the maximum number of
  // requests we set in the constructor

  // remainingRequests tells us how many additional requests could be sent
  // right this moment
  callMyRequestSendingFunction(...);
});
下面是150KB/sec 范例 ,每1个字节的传输就消耗1个token
var BURST_RATE = 1024 * 1024 * 150; // 150KB/sec burst rate
var FILL_RATE = 1024 * 1024 * 50; // 50KB/sec sustained rate
var TokenBucket = require('limiter').TokenBucket;
// We could also pass a parent token bucket in as the last parameter to
// create a hierarchical token bucket
var bucket = new TokenBucket(BURST_RATE, FILL_RATE, 'second', null);

bucket.removeTokens(myData.byteLength, function() {
  sendMyData(myData);
});
 
九)StackOverflow 上的相关讨论:

© 著作权归作者所有

旁观者-郑昀
粉丝 100
博文 77
码字总数 162700
作品 0
朝阳
私信 提问
加载中

评论(1)

dukope
dukope
79
亿级流量电商详情页系统的大型高并发与高可用缓存架构实战

对于高并发的场景来说,比如电商类,o2o,门户,等等互联网类的项目,缓存技术是Java项目中最常见的一种应用技术。然而,行业里很多朋友对缓存技术的了解与掌握,仅仅停留在掌握redis/memca...

登录404
2017/06/05
1K
0
阿里中间件招聘

我们有世界上最牛的交易场景,但还缺少最牛的你! 招聘岗位: 资深Java开发工程师、技术专家 岗位描述: 中间件技术部是阿里巴巴集团生态系统的技术基石,为淘宝、天猫、聚划算、1688、B2B、A...

robin-yao
2016/05/31
687
0
阿里招聘JAVA工程师

我不是HR,只是一名做分布式服务的研发人员,最近我们部门正在招聘一批JAVA工程师。希望有兴趣的朋友可以来试试,一起共事。以下是是要求: 失效时间: 长期招聘 工作地点: 杭州市,北京市 工作...

ifree613
2016/09/16
323
0
spymemcached 的 useNagle 问题与 TCP/IP延迟发送数据

先说一下结论。 如果你没有特意在 spymemcached 的 client bean definition 里配置 useNagleAlgorithm 属性为 True, 那么默认 spymemcached 是不启用 Nagle 算法的。 所以默认情况下不会引发...

旁观者-郑昀
2013/02/08
167
0
中国电子商务区块链规范发展中心将成立。

中国电子商务区块链规范发展中心隶属于工信部主管中国电子商务协会中国电子商务应用推广中心,是"中国电子商务新经济产业发展课题组"的重要职能机构,致力于规范区块链市场环境、开展区块链技...

二进制财经
2018/07/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

技术分享 | MySQL 8.0:字符集从 utf8 转换成 utf8mb4

作者:胡呈清 整理 MySQL 8.0 文档时发现一个变更:默认字符集由 latin1 变为 utf8mb4。想起以前整理过字符集转换文档,升级到 MySQL 8.0 后大概率会有字符集转换的需求,在此正好分享一下。...

爱可生
27分钟前
4
0
不管单机还是集群的限流实现已经给你准备好了

限流算法 计数器算法 维护一个counter,规定在单位时间内counter的大小不能超过最大值,每隔固定时间就将counter的值置零。如果这个counter大于设定的阈值,那么系统就拒绝请求 漏桶算法 维护...

阿提说说
38分钟前
4
0
文件管理

通过CLI登录进行文件管理 .表示当前目录,..表示父目录,具有隐藏文件。支持缩写与TAB键补全 1、目录操作 pwd#打印工作目录 cd <directory>#改变工作目录 dir [/all][<directory>]#查看目录内...

悠悠子佩
40分钟前
4
0
Netty学习笔记(10)——Netty中的Channel组件

1. Channel的功能 1. 与NIO中的Channel一样,它实现了网络操作的抽象类,聚合了一系列的网络IO功能,包括读写数据、建立连接、关闭连接等功能。通过外观模式,将数据读写、连接建立与断开等操...

江左煤郎
44分钟前
3
0
二叉树的深度

从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。 public int TreeDepth(TreeNode root) { return root == null ? 0 : 1 + Math.max(Tree...

Garphy
52分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部