@郑昀汇总
创建日期: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 :
解决思路:
推荐采用令牌桶算法的简易实现。
参考资料:
一)
Leaky Bucket,漏桶算法。
图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所示。
图2.1 CAR和CTS进行流量控制示意图
我们主要关注约定访问速率(CAR)模式,即:
a. 按特定的速率向令牌桶投放令牌;
b.根据预设的匹配规则先对报文进行分类,不符合匹配规则的报文不需要经过令牌桶的处理,直接发送;
c.符合匹配规则的报文,则需要令牌桶进行处理。当桶中有足够的令牌则报文可以被继续发送下去,同时令牌桶中的令牌量按报文的长度做相应的减少;
d.当令牌桶中的令牌不足时,报文将不能被发送(即丢弃),只有等到桶中生成了新的令牌,报文才可以发送。这就可以限制报文的流量只能是小于等于令牌生成的速度,达到限制流量的目的。
实现:
在数据结构上,没有必要真的实现一个令牌桶。
基于时间的流逝生成受控制数量的令牌即可——以时间的流逝来洗涤旧迹,也就是将两次发包或者收包的间隔和令牌数量联系起来。
辅助理解的图形:
令牌桶和漏桶算法最主要的差别在于:漏桶算法能够强行限制数据的传输速率,而令牌桶算法能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。
在令牌桶算法中,只要令牌桶中存在令牌,那么就允许突发地传输数据直到达到用户配置的门限,因此它适合于具有突发特性的流量。
三)http://developer.linkedin.com/documents/throttle-limits 这是常见的开放平台限制请求速率的方式。
LinkedIn 比较好的一点就是把Application throttles和Developer 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
代码实现: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 上的相关讨论:
相关推荐
标题中的“乡村治理背景下的电商发展分析:条件与意义——以贵州省息烽县‘第一淘宝村’为例”揭示了本文的核心主题,它涉及到以下几个重要的IT知识点: 1. 电子商务(E-commerce):电子商务是利用互联网技术和...
标题中的“基于CAS的跨境电商与制造业集群协同演化的机制研究”揭示了该研究的核心主题,它涉及到了两个关键领域:跨境电商(Cross-border E-commerce)和制造业集群(Manufacturing Clusters),并通过复杂适应系统...
3. 跨境电商推动下的传统产业集群转型:传统产业集群在跨境电商的影响下,通过渗透型、交叉型和重组型三种产业融合模式,实现了与跨境电商业务的结合。这些模式有助于传统企业突破传统的外贸模式,改善出口营销,...
本篇实战将介绍如何在 C# 环境下搭建 Sentinel 的集群限流环境。 首先,为了使用集群流控,我们需要配置一个动态规则源,以便通过 Sentinel 控制台实时推送规则。在这个例子中,我们将使用 Nacos 作为规则源的配置...
我国产业集群与跨境电商融合发展是当前电商行业和产业链发展的一个重要趋势,这一趋势的影响因素和实现路径涉及到多个方面,包括政策环境、市场环境、技术条件、产业组织特征等。 首先,政府政策是推动产业集群与跨...
文章以建德电器工具产业集群为例,分析了在当前全球价值链背景下,通过跨境电商推动产业集群升级的路径和制约因素,内容丰富,见解深刻。 首先,文章指出了建德电器工具产业集群在发展过程中的现状和面临的问题。...
【Java企业级电商项目架构演进之路 Tomcat集群与Redis分布式】 这门课程是针对Java开发者设计的,旨在提升他们的企业级项目架构能力,特别是聚焦于Tomcat集群和Redis分布式缓存的应用。课程内容丰富,适合希望晋升...
全书分为两个部分,共14章,第1部分是集群理论篇,这部分从集群基础知识入手,通过分析集群环境和单机环境的不同,介绍了集群环境的各个组件及其作用,以及集群环境的一些专有技术,包括Oracle Clusterware、Oracle ...
全书分为两个部分,共14章,第1部分是集群理论篇,这部分从集群基础知识入手,通过分析集群环境和单机环境的不同,介绍了集群环境的各个组件及其作用,以及集群环境的一些专有技术,包括Oracle Clusterware、Oracle ...
在这样的背景下,研究跨境电商与制造业集群之间的协同演化机制,对促进两者之间的良性互动,实现共同发展具有重要的理论与现实意义。 本文所指的CAS(Complex Adaptive Systems,复杂适应系统)理论,是一种用于...
### 电商技术架构及其环境搭建 #### 一、电商行业背景与发展趋势 随着中国经济的快速发展,电子商务已成为推动经济增长的重要力量之一。据统计,截至2012年底,中国电子商务市场的交易规模达到了7.85万亿元人民币...
基于上述分析,沧州市的特色产业集群要想在全球化的市场环境中取得成功,就需要结合跨境电商的特性,发挥其地理和文化优势,推动产业集群的转型升级。本文提出,可以基于沧州特色产业集群的发展特点,构建一个具有...
在“互联网+”的时代背景下,电子商务作为信息技术与传统经济深度融合的产物,正在全球范围内...在“互联网+”的浪潮下,电商产业集群的外部性评价不仅有助于优化集群内部结构,也有助于推动整个电商行业的健康发展。
### 电商集群架构设计方案 #### 一、方案背景与意义 随着互联网的飞速发展,电子商务已成为推动全球经济的重要力量之一。对于许多企业而言,构建一套高效、稳定的电商集群架构不仅能够提升服务质量,还能够增强...
在本项目中,我们关注的是大数据环境下的电商数仓建设和集群监控,具体是利用Zabbix V4.2进行监控。Zabbix是一款开源的企业级监控解决方案,它可以用来监控各种网络参数,确保系统的稳定运行。在电商领域,大数据...
在政府的资金和技术支持下,形成了一个健康的农村电商发展环境,促进农村经济的繁荣。 3. “生产方+电商公司”模式 这一模式也被称为“吉林通榆模式”,电商公司借助政府的资金支持和社会力量,有效整合生产方的...
这样不仅能够推动农村电商产业集群的发展,还能促进农村电商服务体系的精准化和电商服务业水平的提升。 总的来说,发展农村电商产业集群是一个系统工程,需要在产品、企业、个人等多方面共同努力。通过上述路径,...
大话Oracle RAC:集群、高可用性、备份与恢复。 此书被认为不可多得的好资料之一:大话Oracle RAC(PDF经典),看完之后深有感触,发出来共享一下。