谈谈服务端缓存的几种用法

技术相关 2 Comments »

缓存是一个常谈常新的话题,作为一名服务端的技术,如果你入行一年都还没用过memcached类产品,那只能说你的公司实在太小了,或者你干的活实在太边缘了。

说起缓存,可能大家最直接想到的就是:“在数据库前面挡一层”。这是缓存最原始的意义,同时也引申出了缓存最普遍的用法。

原始模式

代码示例1(原始模式):

1
2
3
4
5
6
7
8
9
10
11
//从缓存中获取数据[较快的方式]
data = getfromcache(id)
if data == null then
    //从数据库中获取数据[较慢的方式]
    data = getfromdb(id)
    //缓存1天
    setintocache(id, data, 86400)
    return data
end
 
return data

缓存加锁

上面这种情况下,当同时有N个请求到达,都同时执行getfromcache,那么都会发现data在缓存中不存在,然后都会去调用getfromdb,以及setintocache。这是不必要的,那么我们有没有办法减少这些并发呢。

最直接的想法是加锁,当进入if条件中时,加一把锁,让其他进程不再执行下面的逻辑,而是等第一个进程的setintocache执行完成后,再重新执行一次getfromcache。

那这个锁如何加呢?这里推荐一种省时省力的方法。通过直接在缓存value中设置过期时间来实现。

比如缓存的value值为data,那我们修改一下,把它放到一个json中,改成

1
{data:data,atime:1429618765}

我们增加了一个atime来记录缓存生成的时间。而逻辑就变成下面这样。

代码示例2(缓存加锁):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//从缓存中获取数据[较快的方式]
data = getfromcache(id)
data = json.decode(data)
//如果通过检查缓存生成时间,发现缓存已经过于陈旧,那么就将缓存过期时间设置为现在开始的5分钟以后(这样其他并发进程就会以为此缓存还未过期,还会继续使用5分钟,只让当前这一个请求去重建缓存)
if data != null && data.atime+86400 < now then
    data.atime = now+300-86400
    data = json.encode(data)
    //对真正的cache来说,缓存10天或者更长时间
    setintocache(id, data, 864000)
    //这里把data设置成null是为了走到下面的if中去重建缓存
    data = null
end
 
if data == null then
    //从数据库中获取数据[较慢的方式]
    data = getfromdb(id)
    data = {data:data, atime:now}
    data = json.encode(data)
    //对真正的cache来说,缓存10天或者更长时间
    setintocache(id, data, 864000)
    return data
end
 
return data

你可以会发现,这里也会存在并发啊,和上面例1一样,第一个getfromcache到setintocache之间,如果同时有N个请求到来,不还是都会执行这段操作,都会去查库吗。

没错,是这样的。但是我们仔细看一下,例1中,从getfromcache到setintocache之间,经历了一次漫长的getfromdb操作,这个时间耗费可能是上百毫秒的。而我们例2中,并没有进行什么操作,这个时间耗费只在毫秒甚至微秒级的。

所以例1中getfromcache到setintocache之间的并发是远大于例2中的。例2中通过减小时间窗口,有效的模拟了锁机制。同时还没有增强额外的存储复杂度。所以是推荐的一种方式。

可以说,我们所有的缓存都应该是例2的方式,他在各方面都优于例1(多保存的一个atime字段耗费的内存基本可以忽略不计。且atime很多时候对于调试程序还很有用)。

主动更新缓存

那这样就够了吗?对于被动过期型的缓存,这样基本就可以了。但是现实中还有一种缓存,是主动更新的。试想有一种缓存,我们要求必须和数据库中的数据一致,不能出现陈旧数据。那么上面的缓存方式就不合适了。

我们必然会添加一个流程:即当数据库有更新时,同时更新缓存,因为缓存会自己重建,也可以修改为当数据库有更新时,同时删除缓存。

这里提到删除或者更新缓存,就有点意思了。我们上面讲到的都是非常简单的缓存,即一个id对应一个key。那么试想,如果我们有一个分页缓存,缓存了某一个文章最新的前10页数据。分别的key是page_1,page_2…page10。

那么当我们有一条新数据产生,这10页就都失效了,需要更新或者删除10次。这显然是不太科学的做法。

那么我们应该怎么做呢。我们可以借用上面例2中的方法,例2中,我们在缓存中增加了一个atime字段,标识为缓存的生成时间。我们既然知道缓存什么时候生成的,那问题就好解决了。我们在每次有新数据产生时,都去更新一个updatetime字段。然后获取分页缓存的时候,看一下这个updatetime字段是不是在atime之后,如果是,那么说明这份缓存太旧了,需要走更新流程。

代码示例3(避免批量更新):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//从缓存中获取数据[较快的方式][这里的两次get普通的缓存系统都支持一个请求完成]
data = getfromcache(id)
updatetime = getupdatetime(id)
data = json.decode(data)
//如果通过检查缓存生成时间,发现缓存已经过于陈旧,那么就将缓存过期时间设置为现在开始的5分钟以后(这样其他并发进程就会以为此缓存还未过期,还会继续使用5分钟,只让当前这一个请求去重建缓存)
if data != null && (data.atime+86400 < now || date.atime < updatetime) then
    data.atime = now+300-86400
    data = json.encode(data)
    //对真正的cache来说,缓存10天或者更长时间
    setintocache(id, data, 864000)
    //这里把data设置成null是为了走到下面的if中去重建缓存
    data = null
end
 
if data == null then
    //从数据库中获取数据[较慢的方式]
    data = getfromdb(id)
    data = {data:data, atime:now}
    data = json.encode(data)
    //对真正的cache来说,缓存10天或者更长时间
    setintocache(id, data, 864000)
    return data
end
 
return data

这仅仅是在代码示例2的基础上增加了下面这一个条件判断而已

1
date.atime < updatetime

这样,无论是缓存保存时间过期了,还是缓存本身有更新,都会触发带锁机制的缓存更新。

好了,先说到这里,回头有想起来的再做更新。

标签:

谈谈反垃圾

技术相关 7 Comments »

由于常年从事用户产品的开发工作,工作中难免遇到过各种各样反垃圾的事,一回生二回熟,在摸爬滚打的对抗中,也摸出了一些门道,此文算是对个人经验的总结,非专业视角的分享。

这里说的垃圾主要针对诸如垃圾评论,机器注册,机器刷接口等等。

反垃圾很重要的两步是:垃圾识别,垃圾处理。

垃圾识别

对于判别垃圾,通常有下面一些方法。

基于内容的识别

在基于内容的判别上,最直接的是关键词过滤,比如包含“开发票”、“激情视频”这类词的极有可能是垃圾内容,我们通过字符串匹配来判断是否有这类关键词。这里有一个难题,如果是检索一段内容是否包含某一个词还算简单,有很多算法可以实现,比如经典的KMP算法,很多语言内置的字符串查找方法效率也很高。但是,要判断一段内容是否包含一堆关键词中的某一个或某几个,那就有一些难度了,总不能循环一遍所有关键词挨个做匹配吧,所以此法必不可取。

这里推荐两个方法,一个是基于trie树的关键词树,具体有没有开源实现的不清楚,我们使用中是自己基于Memcached改了一个,保留Memcached的简单协议,修改内部逻辑为trie树的查找,简单来说就是将关键词做字节切分,建立一棵trie树,判断一段话中是否包含这些关键词,只需要从根节点向下检索即可。

另外一个方法,是利用贝叶斯算法来进行垃圾概率计算。贝叶斯算法这里就不多展开说了,其原理简单来说就是,收集一组正常内容和一组垃圾内容,用此内容对系统进行训练,让系统能够知道每个词在正常内容中和是在垃圾内容中的概率。做完训练后,再有一段新内容过来,可以直接对其中的词进行综合加权计算,得出整段内容是正常或垃圾的概率。

基于特殊内容的识别

上面是纯粹基于随机内容的识别,而实际上我们可能还有一些省力的方法,比如一般的垃圾内容经常会有下面一些特征:带链接(因为要把用户引导到自己的垃圾网站),带图片(为了更醒目),带数字串(比如QQ号,电话号等等),通过这些特征做字符串匹配也是一个好方法,而且就个人经验来看,还比较奏效。其中需要注意的一点就是,上面的链接、数字串这些,通常攻击者都会搞一些变体,不会直接写链接和数字让你判断。比如换成中文数字和字母,你知道,UTF8是很博大精深的。比如:1҉2҉3҉4҉5҉6҉7҉8҉9҉0҉ 这种。所以判断规则上需要多做一些兼容,比如把这种东西先全转成数字来判断。

基于请求方式的识别

另外,垃圾毕竟是通过我们暴露给用户的各种接口进来的,而攻击者请求我们接口的方法难免与真实用户有差距。比如说,正常用户会先进入注册页面,再填表单,再提交注册按钮。但是恶意注册程序,很可能是不会先访问你的注册页面的,而是直接请求注册接口(利用这一点我们就可以作文章,比如对用户访问路径进行记录,如果未访问页面就直接请求接口的,判为恶意请求)。另外就是攻击者的http头信息,比如最常见的,UA字段是否是cUrl或者其它非正常浏览器。或者像很多前端团队都有在请求url上添加随机数的习惯,这样本来是为了避免后端缓存,但有些低水平的垃圾请求会原样的每次都用同一个随机数,这就很容易识别他们了。总之,从http请求的层面可识别的东西很多,只要攻击者伪装有一点纰漏,咱们就可以抓到他的尾巴。

基于请求主体的识别

如果我们遇到UGC内容的垃圾攻击,那么发起请求的肯定得是一个正常用户(如果是匿名社区请忽略此条)。这时候,内容发送主体的信用级别,就可以转移为对信息质量的判别上来。就像我们都懂的,某些大的平台也会对不同用户执行不同的审核策略(比如都知道的先审后放,还是先放后审),这也需要我们对内容发布主体有充分的信用分级。比如,一个注册24小时内的用户相对一个注册三年发帖无数的用户来说,信用等级就低得多。

基于内容载体的识别

垃圾内容之所以能形成黑色产业链,通常绝不会是恶作剧玩玩而已,所以跟互联网最传统的广告模式一样,垃圾也希望能够多曝光,多赚点击。那怎么做呢,通常就是选择在用户扎堆的地方去发。比如时下热门的电视剧,热点的新闻事件下面就是垃圾流量的公共厕所了。另外,在一些政治军事内容版块发反动言论,在一些娱乐美女内容版块发成人网站,这些也都是常用的路数。总的来说就是,同样一条内容,在热门版块发布,更有可能会是垃圾内容,需要我们更多的关注。

垃圾处理

好吧,上面说了一大堆的方法去给内容和用户评级,以便我们能够对一个用户或者一段发布的内容进行预估,那么,在我们了解了一个用户或者一段内容是否可能是垃圾后,我们脑子里首先蹦出来的可能就是:封杀!但实际处理方法可能不仅封杀一种,下面我们就来探讨一下对垃圾攻击的几种处理方法。

制定封杀方法

如果我们已经确切掌握了垃圾流量的规律,比如某一个IP或一组IP,比如同一组参数,比如内容总是包含某网址的变体,那么我们就可以直接大开杀戒,用这些特征直接进行封杀操作。

制定审核级别

顺着上面的思路,我们可以对不同的用户和内容施加不同的审核策略,比如是直接放行、先审后放、先放后审还是直接毙掉。我们还可以对用户施加不同的限制策略,比如新注册用户每天只能发3条内容(在审核通过一条后又可以再发)。

工作量证明

工作量证明是一个在反垃圾邮件中的方法,最近火得不得了的比特币,工作量证明也是其核心理论支柱之一。通过引入工作量证明方法,我们甚至可以不用对垃圾流量进行判别。只要加一道隐形的门槛,就足以让很多攻击者却步。

举个例子,如果攻击者原来只需要请求一次接口就能够发布一条信息,现在我们需要他在接口请求之前先填一个验证码,他就没那么容易自动狂发内容了。上面这个逻辑大家都能理解,也确实能奏效,但是很抱歉,这样做很伤用户体验,产品经理说不行。

那我们换一种做法,我们让用户在请求前先做大约10w次的md5运算,普通用户的机器偶尔进行一次这样的计算不算什么,但是对攻击者来说,它需要单机发布大量内容,如果我们要求每条内容都需要做10w次md5的话,对的硬件资源是很大的挑战,也是让他放弃对你网站进行攻击的一个方法。

当然,如果我们直接用上面的10w次md5的方法,我们在服务端也需要做同样多的工作才能对传入的接口进行验证,对我们服务器本身也是很大的挑战。所以上面只是一个为了让我们理解的例子,通常的做法是,服务端给定一个随机字符串 s1,客户端需要找到一个数 d,这个数要满足下面条件:这个数破加在这个随机串后同组成一个新串 s2,这个新串进行md5后,前5位都要是0。大家可以想一下,要达到这样的标准,客户端需要不断循环来寻找这个合适的d,而服务端验证却是只需要进行一次md5就可以了。这就是所谓的工作量证明。

请求签名

请求签名也是一个省时省力的好方法,前后端约定一种hash算法(最好是自创的),前端对请求内容进行签名,后端验证签名。通过对前端代码进行混淆,让攻击者很难实现你的hash算法。增加他的攻击成本。

查出源头

发垃圾内容的攻击者通常都不会用自己机器或服务器IP(要不你就赚到了,直接封IP就行了),而是用手里控制的肉鸡或者扫描来的http代理来做,其实识别肉鸡和代理也比较简单,最直接的方法就是看看开没开着80、8080、3128等端口。这是一般代理的常用接口,另外一般情况下被拿下的肉鸡也都是web接口防范不严造成的。如果是普通http代理,很可能会很有良心的通过x-forward-for,或者x-real-ip等http头信息把源ip传给你,而对于肉鸡找到肉鸡,如果你的黑客水平够,你可以直接也黑上去,看看是哪个IP在控制它,从而查到真实IP。查到攻击者的真实IP后如何处理就看你的了,是联系攻击方和平解决,直接报案还是把攻击者给黑了。那就看个人想法和水平了。

策略与战略

上面说了一堆战术层面的东西,下面聊一点战略上的原则。

1.反垃圾是一场成本的较量

反垃圾,其实不是一项技术竞赛,更不像是个人恩怨,更多的是成本较量。 如果你的网站流量大,但防护措施做得不够,那垃圾流量过来是必然的。我们所有的反垃圾策略只有一个目的,就是增加攻击者的成本,当成本上升到某一阀值时,攻击者会发现在你的网站玩太费劲,投入产出比太低,于是会去找同类型的其它网站。所以就像狮子和羊群一样,只要不是跑得最慢的那一只,就能逃过狮子的爪牙。

2.多数攻击者痛点在IP

无论是用代理,还是肉鸡,攻击者的IP资源总是比较有限的,所以收集到足够多的IP进行封杀,通常能够解决大问题。

3.实而示之虚

上面说反垃圾是一场成本较量,但在我们实际操作中,却要尽量避免真正的较上劲。比如当你发现了恶意请求的规律,如果你选择直接对此规则的请求返回404,那么攻击者也会马上知道它的攻击特征被你发现了,从而迅速进行升级对抗。但是如果你只是让他的操作无实际效果,但还照样返回“注册成功”、“发布成功”,那么攻击者可能会麻痹大意很长时间才会发现。正如《孙子兵法》中说的:“实而示之虚”。实际上在垃圾与反垃圾的较量中,最忌讳的就是无止境的军备竞赛。

4.发现特征之钓鱼策略

有的攻击者很高明,能够将自己的请求伪装得得正常用户一模一样,所有的http头信息,请求参数,都完全仿真。对于这样的攻击者,我们有什么办法抓到他的尾巴呢。这里给大家介绍一种钓鱼策略。首先你修改一下你的网站的前后端逻辑,比如前端增加某一个参数,后端判断没有这个参数请求就会失败,这时候攻击者马上就会发现自己请求失败了,通过对正常请求的抓包,他很快发现你增加了一个参数,那他会跟着进行修改。这时我们让他爽几天。然后偷偷地把这个无关紧要的参数撤掉。这时候,所有正常用户请求中都不会有这个参数了,但是,攻击者不会时时关注我们的请求参数,所以还会在一段时间内,继续加上这个参数请求。这时钓鱼成功,正是我们的好机会,在这段时间内,我们可以尽量收集垃圾的IP,发布账号等信息。等收集到一定程度一起封掉(当然,这里的封掉也不要暴力封掉,而是让看起来没有被封掉)。

总的来说,反垃圾工作其实不是一个技术活,要求更多的是细致、谨慎与耐心,希望上面东西对你有用。

标签:,

【诗】我丢了我抽屉的钥匙

舞文弄墨 1 Comment »

早上醒来
发现我丢了我抽屉的钥匙

我在记忆里寻找
发现记忆也在抽屉里

晚上再也睡不着
因为我丢了我抽屉的钥匙

我怕我一觉醒来
会把自己的名字也忘记

NoSQL生态系统翻译完稿

NoSQL, 技术相关 3 Comments »

好久不更新博客了,一方面因为工作比较忙,另外很多东西发到了NoSQLFan上,由于精力有限,个人博客这边就荒于维护了。前段时间在网上看到大作 The Architecture of Open Source Applications ,感觉其13章对NoSQL原理的介绍非常不错,于是萌生翻译的念头,花了半个多月业余时间,昨天终于完稿。现已发布到NoSQLFan上,关注NoSQL技术的同学可以看一下,其内容绝不输Bigtable论文和Dynamo论文。

翻译过程还是比较有意思,虽然其中一些已经烂熟的东西会比较枯燥,但还是常常碰到原来理解不正确或者不清楚的地方,很庆幸在此次翻译中能够得到纠正。

当然,最后还是要说,由于水平有限,错误之处难免,请各位发现错误多多指正。比如其原文中其实有一些不清楚或者不太正确的地方,我在翻译中也加了注释指出。

好了,闲话扯到此,下面请各位移步了:

HTML版][PDF版][NoSQLFan版

下面是目录

13.1 NoSQL其名    13.1.1 SQL及其关联型结构
    13.1.2 NoSQL的启示
    13.1.3 特性概述
13.2 NoSQL数据模型及操作模型
    13.2.1 基于key值存储的NoSQL数据模型
        Key-Value 存储
        Key – 结构化数据 存储
        Key – 文档 存储
        BigTable 的列簇式存储
    13.2.2 图结构存储
    13.2.3 复杂查询
    13.2.4 事务机制
    13.2.5 Schema-free的存储
13.3 数据可靠性
    13.3.1 单机可靠性
        控制fsync的调用频率
        使用日志型的数据结构
        通过合并写操作提高吞吐性能
    13.3.2 多机可靠性
13.4 横向扩展带来性能提升
    13.4.1 如非必要,请勿分片
        读写分离
        使用缓存
    13.4.2 通过协调器进行数据分片
    13.4.3 一致性hash环算法
        Hash环图*
        备份数据
        优化的数据分配策略
    13.4.4 连续范围分区
        BigTable的处理方式
        故障处理
        基于范围分区的NoSQL项目
    13.4.5 选择哪种分区策略
13.5 一致性
    13.5.1 关于CAP理论
    13.5.2 强一致性
    13.5.3 最终一致性
        版本控制与冲突
        冲突解决
        读时修复
        Hinted Handoff
        Anti-Entropy
        Gossip
13.6 写在最后的话
13.7 致谢
相关信息

标签:,

优雅的Bitcask

NoSQL, 技术相关 19 Comments »

Bitcask是一个日志型的基于hash表结构和key-value存储模型,我了解到他也就几天时间,但是其简洁有效的设计思路,让我的某种技术癖好得到了极大满足,于是酝酿出这篇东西。

Bitcask模型指导下的存储系统有Riak和豆瓣的beansdb新版本(beansdb新版本信息,参见这里),下面就简单的介绍一下Bitcask模型:

1.日志型的数据文件

何谓日志型?就是append only,所有写操作只追加而不修改老的数据,就像我们的各种服务器日志一样。在Bitcask模型中,数据文件以日志型只增不减的写入文件,而文件有一定的大小限制,当文件大小增加到相应的限制时,就会产生一个新的文件,老的文件将只读不写。在任意时间点,只有一个文件是可写的,在Bitcask模型中称其为active data file,而其他的已经达到限制大小的文件,称为older data file,如下图:

文件中的数据结构非常简单,是一条一条的数据写入操作,每一条数据的结构如下:

上面数据项分别为key,value,key的大小,value的大小,时间戳(应该是),以及对前面几项做的crc校验值。(数据删除操作也不会删除旧的条目,而是将value设定为一个特殊的值以作标示)

数据文件中就是连续一条条上面格式的数据,如下图:

好了,上面是日志型的数据文件,如果数据文件这样持续的存下去,肯定是会无限膨胀的,为了解决个问题,和其他日志型存储系统一样Bitcask也有一个定期的merge操作。

merge操作,即定期将所有older data file中的数据扫描一遍并生成新的data file(没有包括active data file 是因为它还在不停写入),这里的merge其实就是将对同一个key的多个操作以只保留最新一个的原则进行删除。每次merge后,新生成的数据文件就不再有冗余数据了。

2.基于hash表的索引数据

上面讲到的是数据文件,日志类型的数据文件会让我们的写入操作非常快(日志型的优势之一是将磁盘当作磁带,进行顺序读写的效率非常高,可以参见这里),而如果在这样的日志型数据上进行key值查找,那将是一件非常低效的事情。于是我们需要使用一些方法来提高查找效率。

例如在Bigtable中,使用bloom-filter算法为每一个数据文件维护一个bloom-filter 的数据块,以此来判定一个值是否在某一个数据文件中。

而在Bitcask模型中,我们使用了另一种方法,使用了一个基于hash表的索引数据结构。

在Bitcask模型中,除了存储在磁盘上的数据文件,还有另外一块数据,那就是存储在内存中的hash表,hash表的作用是通过key值快速的定位到value的位置。hash表的结构大致如下图所示:

hash表对应的这个结构中包括了三个用于定位数据value的信息,分别是文件id号(file_id),value值在文件中的位置(value_pos),value值的大小(value_sz),于是我们通过读取file_id对应文件的value_pos开始的value_sz个字节,就得到了我们需要的value值。整个过程如下图所示:

由于多了一个hash表的存在,我们的写操作就需要多更新一块内容,即这个hash表的对应关系。于是一个写操作就需要进行一次顺序的磁盘写入和一次内存操作。

3.有用的hint file

至此,Bitcask模型基本上已经讲述完成,而这一节讲到的hint file,则是一个有用的技巧,本人认为并不一定是Bitcask模型的必须特性。

从上面我们可以知道,我们称其为索引的hash表,是存储在内存中的,虽然在各自的实现中可以做一些持久化的保证,但是Bitcask模型中并不对在断电或重启后的hash表数据不丢失做出保证。

因此,如果我们不做额外的工作,那么我们启动时重建hash表时,就需要整个扫描一遍我们的数据文件,如果数据文件很大,这将是一个非常耗时的过程。因此Bitcask模型中包含了一个称作hint file的部分,目的在于提高重建hash表的速度。

我们上面讲到在old data file进行merge操作时,会产生新的data file,而Bitcask模型实际还鼓励生成一个hint file,这个hint file中每一项的数据结构,与data file中的数据结构非常相似,不同的是他并不存储具体的value值,而是存储value的位置(像在hash表中的一样),其结构如下图:

这样,在重建hash表时,就不需要再扫描所有data file文件,而仅仅需要将hint file中的数据一行行读取并重建即可。大大提高了利用数据文件重启数据库的速度。

结语:

以上就是Bitcask数据模型的所有内容,非常之精简易懂,但是记住,他只是一个模型,如果我们要实现一个基于Bitcask的存储系统的话,相信还有很多工作要做,还有很多细节可以优化。有兴趣的同学可以看一看Riak或豆瓣beansdb 0.5.2 版本的源码。

参考文献:http://downloads.basho.com/papers/bitcask-intro.pdf

更多资料:http://goo.gl/b7Bqg

标签:, ,