Redis 与网络流量整形

标签: python | 发表时间:2015-07-17 02:33 | 作者:
出处:http://my.oschina.net/leejun2005

1、需求背景

我们希望服务器能在请求流量的控制上有一定的自动控制能力;本文通过简介令牌桶算法和讨论算法的 redis 实现给出流量整形(traffic shaping)的示例,来介绍网络流量整形。

2、具体原理与实现

2.1 令牌桶算法

令牌桶算法(token bucket) 并不是网络流量整形中的奇技淫巧,而是非常常用的算法,从百度百科上已经可以对它有一个概括的了解。对此算法的深入读者可自行查阅研究,这里我通俗化的来解释一下这个算法。

在令牌桶算法中,每一个访客都拥有一个独立的“令牌桶”,在这个“令牌桶”里放了一些“令牌”,访客每次来访都会消耗“令牌桶”中的“令牌”,如果“令牌桶”空了,将会对访客做特殊处理(如拒绝其继续访问以达到限流的目的)。

问题一:访客来访是一个持续的过程,如果最初的“令牌”数目固定,“令牌桶”中的令牌会慢慢被消耗殆尽,这样正常的访客也将无法访问—-所以我们需要以一个恒定的速率来向“令牌桶”中添加一定数量的“令牌”, 这样就可以让访客持续的访问。

问题二:我们以一个恒定速率向“令牌桶”中添加“令牌”, 那么如果访客一直没来访他的“令牌桶”岂不会累积大量“令牌”么?—-所以,我们设定“令牌桶”中“令牌”的最大数量,“令牌桶”满了就不需要再去添加了。这解决了“令牌”累积的问题,也使它更像一个“桶”。

如此,“令牌桶算法”中的重要的参数有:1. 给“令牌桶”添加“令牌”的速率(如果访客以这个速率消耗令牌,将一直不会被限流); 2. “令牌桶”的容量(如果消耗令牌的速率大于添加令牌的速率,将消耗桶中的存货,如果消耗速率过大,令牌会被消耗殆尽,访客将被限流)。注意:一般情况下“令牌桶”最初的状态是满的。

2.2 Redis

作为优秀的内存数据库,redis 可以帮助我们在应用层次快速响应。本文不过多赘述 redis 的优劣,你可以用 redis 做很多事情,在网络流量整形方面,它是很好的实现方案, 下面我们来解析这样一个方案。

2.3 Show you the  code

说明:这是一段 Python 代码,这段代码来自 GitHub 用户  justinfay。为了使逻辑更清楚,我修改了代码的部分内容和注释,以下是修改后的代码,我们用这段代码来看令牌桶算法的 redis 实现。

import redis
from redis import WatchError
import time
 
# 向令牌桶中添加令牌的速率
RATE = 0.1 
# 令牌桶的最大容量       
DEFAULT = 100
# redis key 的过期时间
TIMEOUT = 60 * 60
 
r = redis.Redis()
 
def token_bucket(tokens, key):
 
    pipe = r.pipeline()
    while 1:
        try:
            pipe.watch('%s:available' % key) 
            pipe.watch('%s:ts' % key)    
 
            current_ts = time.time()
 
            
            # 获取令牌桶中剩余令牌
            old_tokens = pipe.get('%s:available' % key)
            if old_tokens is None:
                current_tokens = DEFAULT
            else:
                old_ts = pipe.get('%s:ts' % key)
                
                # 通过时间戳计算这段时间内应该添加多少令牌,如果桶满,令牌数取桶满数。
                current_tokens = float(old_tokens) + 
                min(
                    (current_ts - float(old_ts)) * RATE,
                    DEFAULT - float(old_tokens)  
                )
            
            # 判断剩余令牌是否足够
            if 0 <= tokens <= current_tokens: 
                current_tokens -= tokens 
                consumes = True
            else: 
                consumes = False
 
            
            # 以下动作为更新 redis 中key的值,并跳出循环返回结果。
            pipe.multi() 
            pipe.set('%s:available' % key, current_tokens) 
            pipe.expire('%s:available' % key, TIMEOUT) 
            pipe.set('%s:ts' % key, current_ts) 
            pipe.expire('%s:ts' % key, TIMEOUT) 
            pipe.execute() 
            break
        except WatchError: 
            continue
        finally: 
            pipe.reset() 
    return consumes 
 
if __name__ == "__main__": 
    tokens = 5
    key = '192.168.1.1'
    if token_bucket(tokens, key): 
        print 'haz tokens'
    else: 
        print 'cant haz tokens'

3、几点需要说明的

3.1 这段代码在网络流量整形策略中起到什么作用?

对访客的一次访问,我们通过以上代码可以来判断此次访问是否超过了我们的限制,通过返回的判断结果,我们将对此次访问选择正确的处理策略,比如你可以拒绝消耗完令牌的访客进行访问,从而控制他的访问速率,从而达到网络流量整形的目的。

3.2 redis 在其中如何工作?

对于每个独立的访客,redis 会为他建立两个 key,一个 key 保存了剩余令牌的数量,另外一个 key 保存了最近一次访问的时间戳。其中,最近一次访问时间戳在新访问到来时候用于计算时间间隔,从而计算在此时间间隔内应该向令牌桶中添加多少令牌,进而获得当前令牌桶的剩余令牌数。

3.3 redis pipe 起到什么作用?

我们看到代码中 while 循环,执行了 redis pipe 中的 watch 动作,这是对  redis 事务 的使用。 这使这里的算法能处理并发的来访。在 redis 中,事务执行是对 redis key 的一个加锁的操作,一个事务没有执行完,别的动作将无法操作这个 key ,代码中循环执行 watch 动作,就是去检查当前 key 是否有未执行完毕的事务,只有所有事务都执行的时候才可能进入执行体,完成令牌判断或者消耗。 —— 这样避免了并发的访问在 set redis key 时候的混乱。

3.4 如何调参

代码中 RATE 和 DEFAULT 为主要参数,分别代表每秒钟消耗令牌的速率,和令牌桶的容量。通过调整这两个参数来控制你想要的访问速率。

3.5 总结

这是一个实用的方式来完成网络流量整形,可以有效控制一些爆发式的流量访问,使访问更加平滑容易控制。

4、流量整形?没那么容易!

4.1 上述 redis 令牌桶算法的缺陷

令牌桶算法不能与另外一种常见算法“漏桶算法(Leaky Bucket)”相混淆。这两种算法的主要区别在于“漏桶算法”能够强行限制数据的传输速率,而“令牌桶算法”在能够限制数据的平均传输速率外,还允许某种程度的突发传输。在“令牌桶算法”中,只要令牌桶中存在令牌,那么就允许突发地传输数据直到达到用户配置的门限,因此它适合于具有突发特性的流量。

比如频率限制是 100次/分,前60秒第1-59秒访问了1次,第60秒访问了98次, 前面60秒访问了99次, 符合。

然而当访问第61秒访问了50次, 其实60-61秒就已经超过了,这里就需要注意不均匀的流量控制策略。

如果读者朋友们仔细思考下,文中前面提到的方案会面临如下的问题:

假如频率限制是 100次/60s。令牌桶原来的令牌数为100 ,按照(100/60)个/秒往令牌桶里面加令牌。有一段时间1-60s,其中第一秒就消费了100个,那么按照加令牌的速率,在第二秒就会又产生一个令牌。这就会造成,1-60秒这一分钟内请求的次数已经大于100了。

4.2 另外的思路:

分别把当前秒调用的次数存入缓存。比如说,当前调用者调用次数为3,那么我就往缓存中加入KEY=SECRET_1,VALUE=3;然后调用者在第二秒调用的次数为4,那么就往缓存中加入KEY=SECRET_2,VALUE=3;如此循环,当循环到61秒的时候替换KEY=SECRET_1中得VAALUE,每次调用的时候计算SECRET_1~SECRET_60的值来判断调用次数,是否超过100次。(这里具体一秒钟调用几次,需要通过时间戳来算出是第几秒。这里以60秒为时间周期,并且以秒为一个时间单位,当然如果要求不是很准确的话,时间单位可以调大一点)

或者我们不固定时间,来固定次数:对每个用户,我们使用一个列表类型的键来记录他最近100次访问博客的时间。一旦列表中的元素超过 100 个,就判断时间最早的元素距现在的时间是否小于1分钟。如果是则表示用户最近1分钟的访问次数超过了100次;如果不是就将现在的时间加入到列表中,同时把最早的元素删除。

不过这里的思路也有不少性能问题和缺陷,如果想要设计实现一个非常完美的频率限制功能,看来没那么容易,读者朋友们也可以自行思考下 :)

5、Refer:

[1] Redis 与网络流量整形

http://blog.jobbole.com/88064/

[2] 怎么保证对外暴露接口的安全性(调用频率限制)

http://segmentfault.com/q/1010000002938194?_ea=252390

[3] 开放平台API接口调用频率控制系统设计浅谈

http://my.oschina.net/feichexia/blog/312591

[4] 4.2.3 实现访问频率限制之二

http://book.51cto.com/art/201305/395450.htm

[5] redis token bucket

https://gist.github.com/justinfay/3403846

[6] redis 事务

http://redisbook.readthedocs.org/en/latest/feature/transaction.html

相关 [redis 网络流量 整形] 推荐:

Redis 与网络流量整形

- - leejun_2005的个人页面
我们希望服务器能在请求流量的控制上有一定的自动控制能力;本文通过简介令牌桶算法和讨论算法的 redis 实现给出流量整形(traffic shaping)的示例,来介绍网络流量整形. 令牌桶算法(token bucket) 并不是网络流量整形中的奇技淫巧,而是非常常用的算法,从百度百科上已经可以对它有一个概括的了解.

nicstat 网络流量统计利器

- - 系统技术非业余研究
原创文章,转载请注明: 转载自 系统技术非业余研究. nicstat 网络流量统计利器. 前段时间看到brendangregg的 Linux Performance Analysis and Tools PPT里面提到的nicstat,研究了下是个不错的东西,分享给大家. nicstat原本是Solaris平台下显示网卡流量的工具,Tim Cook将它移植到linux平台,官方网站见 这里.

用iftop监控网络流量

- - CSDN博客推荐文章
iftop是很有用的工具,下面的命令监控了我的笔记本的无线网卡. 比如我现在播放乐视一个视频,iftop显示的信息:. 屏幕主要部分都是表示两个机器之间的数据传送,有箭头表示方向,右边三个数值分别是过去2秒,10秒和40秒的平均流量. 2  左下角的TX 表示发出的数据,RX表示收到的数据,.  cum表示总流量, peak表示对应的峰值, Total就不用解释了.

Redis 负载监控——redis-monitor

- - ITeye资讯频道
redis-monitor是一个Web可视化的 redis 监控程序. 使用 Flask 来开发的,代码结构非常简单,适合移植到公司内网使用. redis 服务器信息,包括 redis 版本、上线时间、 os 系统信息等等. 实时的消息处理信息,例如处理 command 数量、连接总数量等. 内存占用、 cpu 消耗实时动态图表.

Redis 起步

- - 博客园_首页
Rdis和JQuery一样是纯粹为应用而产生的,这里记录的是在CentOS 5.7上学习入门文章:. Redis是一个key-value存储系统. 和Memcached类似,但是解决了断电后数据完全丢失的情况,而且她支持更多无化的value类型,除了和string外,还支持lists(链表)、sets(集合)和zsets(有序集合)几种数据类型.

redis 配置

- - 谁主沉浮
# 当配置中需要配置内存大小时,可以使用 1k, 5GB, 4M 等类似的格式,其转换方式如下(不区分大小写). # 内存配置大小写是一样的.比如 1gb 1Gb 1GB 1gB. # daemonize no 默认情况下,redis不是在后台运行的,如果需要在后台运行,把该项的值更改为yes. # 当redis在后台运行的时候,Redis默认会把pid文件放在/var/run/redis.pid,你可以配置到其他地址.

Cassandra代替Redis?

- - Tim[后端技术]
最近用Cassandra的又逐渐多了,除了之前的360案例,在月初的QCon Shanghai 2013 篱笆网也介绍了其使用案例. 而这篇 百万用户时尚分享网站feed系统扩展实践文章则提到了Fashiolista和Instagram从Redis迁移到Cassandra的案例. 考虑到到目前仍然有不少网友在讨论Redis的用法问题,Redis是一个数据库、内存、还是Key value store?以及Redis和memcache在实际场景的抉择问题,因此简单谈下相关区别.

redis 部署

- - CSDN博客云计算推荐文章
一、单机部署 tar xvf redis-2.6.16.tar.gz cd redis-2.6.16 make make PREFIX=/usr/local/redis install  #指定安装目录为/usr/local/redis,默认安装安装到/usr/local/bin. # chkconfig: 2345 80 10       #添加redhat系列操作系统平台,开机启动需求项(运行级别,开机时服务启动顺序、关机时服务关闭顺序) # description:  Starts, stops redis server.

nagios 监控redis

- - C1G军火库
下载check_redis.pl. OK: REDIS 2.6.12 on 192.168.0.130:6379 has 1 databases (db0) with 49801 keys, up 3 days 14 hours - connected_clients is 1, blocked_clients is 0 | connected_clients=1 blocked_clients=0.

转 redis vs memcached

- - 数据库 - ITeye博客
传统MySQL+ Memcached架构遇到的问题.   实际MySQL是适合进行海量数据存储的,通过Memcached将热点数据加载到cache,加速访问,很多公司都曾经使用过这样的架构,但随着业务数据量的不断增加,和访问量的持续增长,我们遇到了很多问题:.   1.MySQL需要不断进行拆库拆表,Memcached也需不断跟着扩容,扩容和维护工作占据大量开发时间.