搭建海量数据采集爬虫框架教程

海量数据采集爬虫，相当于大的搜索引擎爬虫了，现在我们来看看如何搭建海量数据采集爬虫框架，相关的朋友可以参考一下。

随着BIG DATA大数据概念逐渐升温，如何搭建一个能够采集海量数据的架构体系摆在大家眼前。如何能够做到所见即所得的无阻拦式采集、如何快速把不规则页面结构化并存储、如何满足越来越多的数据采集还要在有限时间内采集。这篇文章结合我们自身项目经验谈一下。

我们来看一下作为人是怎么获取网页数据的呢?

1、打开浏览器，输入网址url访问页面内容。

2、复制页面内容的标题、作者、内容。

3、存储到文本文件或者excel。

从技术角度来说整个过程主要为 网络访问、扣取结构化数据、存储。我们看一下用java程序如何来实现这一过程。

import java.io.IOException;
import org.apache.commons.httpclient.HttpClient;
import org.apache.commons.httpclient.HttpException;
import org.apache.commons.httpclient.HttpStatus;
import org.apache.commons.httpclient.methods.GetMethod;
import org.apache.commons.lang.StringUtils;

public class HttpCrawler {
       public static void main(String[] args) {

            String content = null ;
             try {
                  HttpClient httpClient = new HttpClient();
                   //1、网络请求
                  GetMethod method = new GetMethod("http://www.baidu.com" );
                   int statusCode = httpClient.executeMethod(method);
                   if (statusCode == HttpStatus. SC_OK) {
                        content = method.getResponseBodyAsString();
                         //结构化扣取
                        String title = StringUtils.substringBetween(content, "<title>" , "</title>" );
                         //存储
                        System. out .println(title);
                  }

            } catch (HttpException e) {
                  e.printStackTrace();
            } catch (IOException e) {
                  e.printStackTrace();
            } finally {
            }
      }
}

通过这个例子，我们看到通过httpclient获取数据，通过字符串操作扣取标题内容，然后通过system.out输出内容。大家是不是感觉做一个爬虫也还是蛮简单呢。这是一个基本的入门例子，我们再详细介绍怎么一步一步构建一个分布式的适用于海量数据采集的爬虫框架。

整个框架应该包含以下部分，资源管理、反监控管理、抓取管理、监控管理。看一下整个框架的架构图：

 

 

资源管理指网站分类体系、网站、网站访问url等基本资源的管理维护;

反监控管理指被访问网站(特别是社会化媒体)会禁止爬虫访问，怎么让他们不能监控到我们的访问时爬虫软件，这就是反监控机制了;

一个好的采集框架，不管我们的目标数据在哪儿，只要用户能够看到都应该能采集到。所见即所得的无阻拦式采集，无论是否需要登录的数据都能够顺利采集。现在大部分社交网站都需要登录，为了应对登录的网站要有模拟用户登录的爬虫系统，才能正常获取数据。不过社会化网站都希望自己形成一个闭环，不愿意把数据放到站外，这种系统也不会像新闻等内容那么开放的让人获取。这些社会化网站大部分会采取一些限制防止机器人爬虫系统爬取数据，一般一个账号爬取不了多久就会被检测出来被禁止访问了。那是不是我们就不能爬取这些网站的数据呢?肯定不是这样的，只要社会化网站不关闭网页访问，正常人能够访问的数据，我们也能访问。说到底就是模拟人的正常行为操作，专业一点叫“反监控”。

那一般网站会有什么限制呢?

一定时间内单IP访问次数，没有哪个人会在一段持续时间内过快访问，除非是随意的点着玩，持续时间也不会太长。可以采用大量不规则代理IP来模拟。

一定时间内单账号访问次数，这个同上，正常人不会这么操作。可以采用大量行为正常的账号，行为正常就是普通人怎么在社交网站上操作，如果一个人一天24小时都在访问一个数据接口那就有可能是机器人了。

如果能把账号和IP的访问策略控制好了，基本可以解决这个问题了。当然对方网站也会有运维会调整策略，说到底这是一个战争，躲在电脑屏幕后的敌我双方，爬虫必须要能感知到对方的反监控策略进行了调整，通知管理员及时处理。未来比较理想应该是通过机器学习算法自动完成策略调整，保证抓取不间断。

抓取管理指通过url，结合资源、反监控抓取数据并存储;我们现在大部分爬虫系统，很多都需要自己设定正则表达式，或者使用htmlparser、jsoup等软件来硬编码解决结构化抓取的问题。不过大家在做爬虫也会发现，如果爬取一个网站就去开发一个类，在规模小的时候还可以接受，如果需要抓取的网站成千上万，那我们不是要开发成百上千的类。为此我们开发了一个通用的抓取类，可以通过参数驱动内部逻辑调度。比如我们在参数里指定抓取新浪微博，抓取机器就会调度新浪微博网页扣取规则抓取节点数据，调用存储规则存储数据，不管什么类型最后都调用同一个类来处理。对于我们用户只需要设置抓取规则，相应的后续处理就交给抓取平台了。

整个抓取使用了 xpath、正则表达式、消息中间件、多线程调度框架(参考)。xpath 是一种结构化网页元素选择器，支持列表和单节点数据获取，他的好处可以支持规整网页数据抓取。我们使用的是google插件 XPath Helper，这个玩意可以支持在网页点击元素生成xpath，就省去了自己去查找xpath的功夫，也便于未来做到所点即所得的功能。正则表达式补充xpath抓取不到的数据，还可以过滤一些特殊字符。消息中间件，起到抓取任务中间转发的目的，避免抓取和各个需求方耦合。比如各个业务系统都可能抓取数据，只需要向消息中间件发送一个抓取指令，抓取平台抓完了会返回一条消息给消息中间件，业务系统在从消息中间件收到消息反馈，整个抓取完成。多线程调度框架之前提到过，我们的抓取平台不可能在同一时刻只抓一个消息的任务;也不可能无限制抓取，这样资源会耗尽，导致恶性循环。这就需要使用多线程调度框架来调度多线程任务并行抓取，并且任务的数量，保证资源的消耗正常。

不管怎么模拟总还是会有异常的，这就需要有个异常处理模块，有些网站访问一段时间需要输入验证码，如果不处理后续永远返回不了正确数据。我们需要有机制能够处理像验证码这类异常，简单就是有验证码了人为去输入，高级一些可以破解验证码识别算法实现自动输入验证码的目的。

扩展一下 ：所见即所得我们是不是真的做到?规则配置也是个重复的大任务?重复网页如何不抓取?

1、有些网站利用js生成网页内容，直接查看源代码是一堆js。 可以使用mozilla、webkit等可以解析浏览器的工具包解析js、ajax，不过速度会有点慢。

2、网页里有一些css隐藏的文字。使用工具包把css隐藏文字去掉。

3、图片flash信息。 如果是图片中文字识别，这个比较好处理，能够使用ocr识别文字就行，如果是flash目前只能存储整个url。

4、一个网页有多个网页结构。如果只有一套抓取规则肯定不行的，需要多个规则配合抓取。

5、html不完整，不完整就不能按照正常模式去扣取。这个时候用xpath肯定解析不了，我们可以先用htmlcleaner清洗网页后再解析。

6、 如果网站多起来，规则配置这个工作量也会非常大。如何帮助系统快速生成规则呢?首先可以配置规则可以通过可视化配置，比如用户在看到的网页想对它抓取数据，只需要拉开插件点击需要的地方，规则就自动生成好了。另在量比较大的时候可视化还是不够的，可以先将类型相同的网站归类，再通过抓取的一些内容聚类，可以统计学、可视化抓取把内容扣取出几个版本给用户去纠正，最后确认的规则就是新网站的规则。这些算法后续再讲。这块再补充一下(多谢zicjin建议)：

背景：如果我们需要抓取的网站很多，那如果靠可视化配置需要耗费大量的人力，这是个成本。并且这个交给不懂 html的业务去配置准确性值得考量，所以最后还是需要技术做很多事情。那我们能否通过技术手段可以帮助生成规则减少人力成本，或者帮助不懂技术的业务准确的把数据扣取下来并大量复制。

方案：先对网站分类，比如分为新闻、论坛、视频等，这一类网站的网页结构是类似的。在业务打开需要扣取的还没有录入我们规则库的网页时，他先设定这个页面的分类(当然这个也可以机器预先判断，他们来选择，这一步必须要人判断下)，有了分类后，我们会通过“统计学、可视化判断”识别这一分类的字段规则，但是这个是机器识别的规则，可能不准确，机器识别完后，还需要人在判断一下。判断完成后，最后形成规则才是新网站的规则

7、对付重复的网页，如果重复抓取会浪费资源，如果不抓需要一个海量的去重判断缓存。判断抓不抓，抓了后存不存，并且这个缓存需要快速读写。常见的做法有bloomfilter、相似度聚合、分类海明距离判断。

监控管理指不管什么系统都可能出问题，如果对方服务器宕机、网页改版、更换地址等我们需要第一时间知道，这时监控系统就起到出现了问题及时发现并通知联系人。

目前这样的框架搭建起来基本可以解决大量的抓取需求了。通过界面可以管理资源、反监控规则、网页扣取规则、消息中间件状态、数据监控图表，并且可以通过后台调整资源分配并能动态更新保证抓取不断电。不过如果一个任务的处理特别大，可能需要抓取24个小时或者几天。比如我们要抓取一条微博的转发，这个转发是 30w，那如果每页线性去抓取耗时肯定是非常慢了，如果能把这30w拆分很多小任务，那我们的并行计算能力就会提高很多。不得不提的就是把大型的抓取任务 hadoop化，废话不说直接上图：

 

 

今天先写到这里，后续再介绍下 日均千万大型采集项目实战。

Redis是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库，并提供多种语言的API。从2010年3月15日起，Redis的开发工作由VMware主持。

1. MySql+Memcached架构的问题

实际MySQL是适合进行海量数据存储的，通过Memcached将热点数据加载到cache，加速访问，很多公司都曾经使用过这样的架构，但随着业务数据量的不断增加，和访问量的持续增长，我们遇到了很多问题：

1.MySQL需要不断进行拆库拆表，Memcached也需不断跟着扩容，扩容和维护工作占据大量开发时间。

2.Memcached与MySQL数据库数据一致性问题。

3.Memcached数据命中率低或down机，大量访问直接穿透到DB，MySQL无法支撑。

4.跨机房cache同步问题。

众多NoSQL百花齐放，如何选择

最近几年，业界不断涌现出很多各种各样的NoSQL产品，那么如何才能正确地使用好这些产品，最大化地发挥其长处，是我们需要深入研究和思考的问题，实际归根结底最重要的是了解这些产品的定位，并且了解到每款产品的tradeoffs，在实际应用中做到扬长避短，总体上这些NoSQL主要用于解决以下几种问题

1.少量数据存储，高速读写访问。此类产品通过数据全部in-momery 的方式来保证高速访问，同时提供数据落地的功能，实际这正是Redis最主要的适用场景。

2.海量数据存储，分布式系统支持，数据一致性保证，方便的集群节点添加/删除。

3.这方面最具代表性的是dynamo和bigtable 2篇论文所阐述的思路。前者是一个完全无中心的设计，节点之间通过gossip方式传递集群信息，数据保证最终一致性，后者是一个中心化的方案设计，通过类似一个分布式锁服务来保证强一致性,数据写入先写内存和redo log，然后定期compat归并到磁盘上，将随机写优化为顺序写，提高写入性能。

4.Schema free，auto-sharding等。比如目前常见的一些文档数据库都是支持schema-free的，直接存储json格式数据，并且支持auto-sharding等功能，比如mongodb。

面对这些不同类型的NoSQL产品,我们需要根据我们的业务场景选择最合适的产品。

Redis最适合所有数据in-momory的场景，虽然Redis也提供持久化功能，但实际更多的是一个disk-backed的功能，跟传统意义上的持久化有比较大的差别，那么可能大家就会有疑问，似乎Redis更像一个加强版的Memcached，那么何时使用Memcached,何时使用 Redis呢?

如果简单地比较Redis与Memcached的区别，大多数都会得到以下观点：

1 、Redis不仅仅支持简单的k/v类型的数据，同时还提供list，set，zset，hash等数据结构的存储。

2 、Redis支持数据的备份，即master-slave模式的数据备份。

3 、Redis支持数据的持久化，可以将内存中的数据保持在磁盘中，重启的时候可以再次加载进行使用。

2. Redis常用数据类型

Redis最为常用的数据类型主要有以下：

String

Hash

List

Set

Sorted set

pub/sub

Transactions

在具体描述这几种数据类型之前，我们先通过一张图了解下Redis内部内存管理中是如何描述这些不同数据类型的：

 

 

首先Redis内部使用一个redisObject对象来表示所有的key和value,redisObject最主要的信息如上图所示：

type代表一个value对象具体是何种数据类型，

encoding是不同数据类型在redis内部的存储方式，

比如：type=string代表value存储的是一个普通字符串，那么对应的encoding可以是raw或者是int,如果是int则代表实际 redis内部是按数值型类存储和表示这个字符串的，当然前提是这个字符串本身可以用数值表示，比如:”123″ “456″这样的字符串。

这里需要特殊说明一下vm字段，只有打开了Redis的虚拟内存功能，此字段才会真正的分配内存，该功能默认是关闭状态的，该功能会在后面具体描述。通过上图我们可以发现Redis使用redisObject来表示所有的key/value数据是比较浪费内存的，当然这些内存管理成本的付出主要也是为了给 Redis不同数据类型提供一个统一的管理接口，实际作者也提供了多种方法帮助我们尽量节省内存使用，我们随后会具体讨论。

3. 各种数据类型应用和实现方式

下面我们先来逐一的分析下这7种数据类型的使用和内部实现方式:

String:

Strings 数据结构是简单的key-value类型，value其实不仅是String，也可以是数字.

常用命令: set,get,decr,incr,mget 等。

应用场景：String是最常用的一种数据类型，普通的key/ value 存储都可以归为此类.即可以完全实现目前 Memcached 的功能，并且效率更高。还可以享受Redis的定时持久化，操作日志及 Replication等功能。除了提供与 Memcached 一样的get、set、incr、decr 等操作外，Redis还提供了下面一些操作：

获取字符串长度

往字符串append内容

设置和获取字符串的某一段内容

设置及获取字符串的某一位(bit)

批量设置一系列字符串的内容

实现方式：String在redis内部存储默认就是一个字符串，被redisObject所引用，当遇到incr,decr等操作时会转成数值型进行计算，此时redisObject的encoding字段为int。

Hash

常用命令：hget,hset,hgetall 等。

应用场景：在Memcached中，我们经常将一些结构化的信息打包成HashMap，在客户端序列化后存储为一个字符串的值，比如用户的昵称、年龄、性别、积分等，这时候在需要修改其中某一项时，通常需要将所有值取出反序列化后，修改某一项的值，再序列化存储回去。这样不仅增大了开销，也不适用于一些可能并发操作的场合(比如两个并发的操作都需要修改积分)。而Redis的Hash结构可以使你像在数据库中Update一个属性一样只修改某一项属性值。

我们简单举个实例来描述下Hash的应用场景，比如我们要存储一个用户信息对象数据，包含以下信息：

用户ID为查找的key，存储的value用户对象包含姓名，年龄，生日等信息，如果用普通的key/value结构来存储，主要有以下2种存储方式：

 

 

第一种方式将用户ID作为查找key,把其他信息封装成一个对象以序列化的方式存储，这种方式的缺点是，增加了序列化/反序列化的开销，并且在需要修改其中一项信息时，需要把整个对象取回，并且修改操作需要对并发进行保护，引入CAS等复杂问题。

 

 

第二种方法是这个用户信息对象有多少成员就存成多少个key-value对儿，用用户ID+对应属性的名称作为唯一标识来取得对应属性的值，虽然省去了序列化开销和并发问题，但是用户ID为重复存储，如果存在大量这样的数据，内存浪费还是非常可观的。

那么Redis提供的Hash很好的解决了这个问题，Redis的Hash实际是内部存储的Value为一个HashMap，并提供了直接存取这个Map成员的接口，如下图：

 

 

也就是说，Key仍然是用户ID, value是一个Map，这个Map的key是成员的属性名，value是属性值，这样对数据的修改和存取都可以直接通过其内部Map的 Key(Redis里称内部Map的key为field), 也就是通过 key(用户ID) + field(属性标签) 就可以操作对应属性数据了，既不需要重复存储数据，也不会带来序列化和并发修改控制的问题。很好的解决了问题。

这里同时需要注意，Redis提供了接口(hgetall)可以直接取到全部的属性数据,但是如果内部Map的成员很多，那么涉及到遍历整个内部 Map的操作，由于Redis单线程模型的缘故，这个遍历操作可能会比较耗时，而另其它客户端的请求完全不响应，这点需要格外注意。

实现方式：

上面已经说到Redis Hash对应Value内部实际就是一个HashMap，实际这里会有2种不同实现，这个Hash的成员比较少时Redis为了节省内存会采用类似一维数组的方式来紧凑存储，而不会采用真正的HashMap结构，对应的value redisObject的encoding为zipmap,当成员数量增大时会自动转成真正的HashMap,此时encoding为ht。

List

常用命令：lpush,rpush,lpop,rpop,lrange等。

应用场景：

Redis list的应用场景非常多，也是Redis最重要的数据结构之一，比如twitter的关注列表，粉丝列表等都可以用Redis的list结构来实现。

Lists 就是链表，相信略有数据结构知识的人都应该能理解其结构。使用Lists结构，我们可以轻松地实现最新消息排行等功能。Lists的另一个应用就是消息队列，

可以利用Lists的PUSH操作，将任务存在Lists中，然后工作线程再用POP操作将任务取出进行执行。Redis还提供了操作Lists中某一段的api，你可以直接查询，删除Lists中某一段的元素。

实现方式：

Redis list的实现为一个双向链表，即可以支持反向查找和遍历，更方便操作，不过带来了部分额外的内存开销，Redis内部的很多实现，包括发送缓冲队列等也都是用的这个数据结构。

Set

常用命令：

sadd,spop,smembers,sunion 等。

应用场景：

Redis set对外提供的功能与list类似是一个列表的功能，特殊之处在于set是可以自动排重的，当你需要存储一个列表数据，又不希望出现重复数据时，set 是一个很好的选择，并且set提供了判断某个成员是否在一个set集合内的重要接口，这个也是list所不能提供的。

Sets 集合的概念就是一堆不重复值的组合。利用Redis提供的Sets数据结构，可以存储一些集合性的数据，比如在微博应用中，可以将一个用户所有的关注人存在一个集合中，将其所有粉丝存在一个集合。Redis还为集合提供了求交集、并集、差集等操作，可以非常方便的实现如共同关注、共同喜好、二度好友等功能，对上面的所有集合操作，你还可以使用不同的命令选择将结果返回给客户端还是存集到一个新的集合中。

实现方式：

set 的内部实现是一个 value永远为null的HashMap，实际就是通过计算hash的方式来快速排重的，这也是set能提供判断一个成员是否在集合内的原因。

Sorted Set

常用命令：

zadd,zrange,zrem,zcard等

使用场景：

Redis sorted set的使用场景与set类似，区别是set不是自动有序的，而sorted set可以通过用户额外提供一个优先级(score)的参数来为成员排序，并且是插入有序的，即自动排序。当你需要一个有序的并且不重复的集合列表，那么可以选择sorted set数据结构，比如twitter 的public timeline可以以发表时间作为score来存储，这样获取时就是自动按时间排好序的。

另外还可以用Sorted Sets来做带权重的队列，比如普通消息的score为1，重要消息的score为2，然后工作线程可以选择按score的倒序来获取工作任务。让重要的任务优先执行。

实现方式：

Redis sorted set的内部使用HashMap和跳跃表(SkipList)来保证数据的存储和有序，HashMap里放的是成员到score的映射，而跳跃表里存放的是所有的成员，排序依据是HashMap里存的score,使用跳跃表的结构可以获得比较高的查找效率，并且在实现上比较简单。

Pub/Sub

Pub/Sub 从字面上理解就是发布(Publish)与订阅(Subscribe)，在Redis中，你可以设定对某一个key值进行消息发布及消息订阅，当一个 key值上进行了消息发布后，所有订阅它的客户端都会收到相应的消息。这一功能最明显的用法就是用作实时消息系统，比如普通的即时聊天，群聊等功能。

Transactions

谁说NoSQL都不支持事务，虽然Redis的Transactions提供的并不是严格的ACID的事务(比如一串用EXEC提交执行的命令，在执行中服务器宕机，那么会有一部分命令执行了，剩下的没执行)，但是这个Transactions还是提供了基本的命令打包执行的功能(在服务器不出问题的情况下，可以保证一连串的命令是顺序在一起执行的，中间有会有其它客户端命令插进来执行)。Redis还提供了一个Watch功能，你可以对一个key进行 Watch，然后再执行Transactions，在这过程中，如果这个Watched的值进行了修改，那么这个Transactions会发现并拒绝执行。

4. Redis实际应用场景

Redis在很多方面与其他数据库解决方案不同：它使用内存提供主存储支持，而仅使用硬盘做持久性的存储;它的数据模型非常独特，用的是单线程。另一个大区别在于，你可以在开发环境中使用Redis的功能，但却不需要转到Redis。

转向Redis当然也是可取的，许多开发者从一开始就把Redis作为首选数据库;但设想如果你的开发环境已经搭建好，应用已经在上面运行了，那么更换数据库框架显然不那么容易。另外在一些需要大容量数据集的应用，Redis也并不适合，因为它的数据集不会超过系统可用的内存。所以如果你有大数据应用，而且主要是读取访问模式，那么Redis并不是正确的选择。

然而我喜欢Redis的一点就是你可以把它融入到你的系统中来，这就能够解决很多问题，比如那些你现有的数据库处理起来感到缓慢的任务。这些你就可以通过 Redis来进行优化，或者为应用创建些新的功能。在本文中，我就想探讨一些怎样将Redis加入到现有的环境中，并利用它的原语命令等功能来解决 传统环境中碰到的一些常见问题。在这些例子中，Redis都不是作为首选数据库。

1、显示最新的项目列表

下面这个语句常用来显示最新项目，随着数据多了，查询毫无疑问会越来越慢。

SELECT * FROM foo WHERE … ORDER BY time DESC LIMIT 10

在Web应用中，“列出最新的回复”之类的查询非常普遍，这通常会带来可扩展性问题。这令人沮丧，因为项目本来就是按这个顺序被创建的，但要输出这个顺序却不得不进行排序操作。

类似的问题就可以用Redis来解决。比如说，我们的一个Web应用想要列出用户贴出的最新20条评论。在最新的评论边上我们有一个“显示全部”的链接，点击后就可以获得更多的评论。

我们假设数据库中的每条评论都有一个唯一的递增的ID字段。

我们可以使用分页来制作主页和评论页，使用Redis的模板，每次新评论发表时，我们会将它的ID添加到一个Redis列表：

LPUSH latest.comments

我们将列表裁剪为指定长度，因此Redis只需要保存最新的5000条评论：

LTRIM latest.comments 0 5000

每次我们需要获取最新评论的项目范围时，我们调用一个函数来完成(使用伪代码)：

FUNCTION get_latest_comments(start, num_items):
id_list = redis.lrange(“latest.comments”,start,start+num_items – 1)
IF id_list.length < num_items
id_list = SQL_DB(“SELECT … ORDER BY time LIMIT …”)
END
RETURN id_list
END

这里我们做的很简单。在Redis中我们的最新ID使用了常驻缓存，这是一直更新的。但是我们做了限制不能超过5000个ID，因此我们的获取ID函数会一直询问Redis。只有在start/count参数超出了这个范围的时候，才需要去访问数据库。

我们的系统不会像传统方式那样“刷新”缓存，Redis实例中的信息永远是一致的。SQL数据库(或是硬盘上的其他类型数据库)只是在用户需要获取“很远”的数据时才会被触发，而主页或第一个评论页是不会麻烦到硬盘上的数据库了。

2、删除与过滤

我们可以使用LREM来删除评论。如果删除操作非常少，另一个选择是直接跳过评论条目的入口，报告说该评论已经不存在。

有些时候你想要给不同的列表附加上不同的过滤器。如果过滤器的数量受到限制，你可以简单的为每个不同的过滤器使用不同的Redis列表。毕竟每个列表只有5000条项目，但Redis却能够使用非常少的内存来处理几百万条项目。

3、排行榜相关

另一个很普遍的需求是各种数据库的数据并非存储在内存中，因此在按得分排序以及实时更新这些几乎每秒钟都需要更新的功能上数据库的性能不够理想。

典型的比如那些在线游戏的排行榜，比如一个Facebook的游戏，根据得分你通常想要：

– 列出前100名高分选手

– 列出某用户当前的全球排名

这些操作对于Redis来说小菜一碟，即使你有几百万个用户，每分钟都会有几百万个新的得分。

模式是这样的，每次获得新得分时，我们用这样的代码：

ZADD leaderboard

你可能用userID来取代username，这取决于你是怎么设计的。

得到前100名高分用户很简单：ZREVRANGE leaderboard 0 99。

用户的全球排名也相似，只需要：ZRANK leaderboard 。

4、按照用户投票和时间排序

排行榜的一种常见变体模式就像Reddit或Hacker News用的那样，新闻按照类似下面的公式根据得分来排序：

score = points / time^alpha

因此用户的投票会相应的把新闻挖出来，但时间会按照一定的指数将新闻埋下去。下面是我们的模式，当然算法由你决定。

模式是这样的，开始时先观察那些可能是最新的项目，例如首页上的1000条新闻都是候选者，因此我们先忽视掉其他的，这实现起来很简单。

每次新的新闻贴上来后，我们将ID添加到列表中，使用LPUSH + LTRIM，确保只取出最新的1000条项目。

有一项后台任务获取这个列表，并且持续的计算这1000条新闻中每条新闻的最终得分。计算结果由ZADD命令按照新的顺序填充生成列表，老新闻则被清除。这里的关键思路是排序工作是由后台任务来完成的。

5、处理过期项目

另一种常用的项目排序是按照时间排序。我们使用unix时间作为得分即可。

模式如下：

– 每次有新项目添加到我们的非Redis数据库时，我们把它加入到排序集合中。这时我们用的是时间属性，current_time和time_to_live。

– 另一项后台任务使用ZRANGE…SCORES查询排序集合，取出最新的10个项目。如果发现unix时间已经过期，则在数据库中删除条目。

6、计数

Redis是一个很好的计数器，这要感谢INCRBY和其他相似命令。

我相信你曾许多次想要给数据库加上新的计数器，用来获取统计或显示新信息，但是最后却由于写入敏感而不得不放弃它们。

好了，现在使用Redis就不需要再担心了。有了原子递增(atomic increment)，你可以放心的加上各种计数，用GETSET重置，或者是让它们过期。

例如这样操作：

INCR user: EXPIRE

user: 60

你可以计算出最近用户在页面间停顿不超过60秒的页面浏览量，当计数达到比如20时，就可以显示出某些条幅提示，或是其它你想显示的东西。

7、特定时间内的特定项目

另一项对于其他数据库很难，但Redis做起来却轻而易举的事就是统计在某段特点时间里有多少特定用户访问了某个特定资源。比如我想要知道某些特定的注册用户或IP地址，他们到底有多少访问了某篇文章。

每次我获得一次新的页面浏览时我只需要这样做：

SADD page:day1:

当然你可能想用unix时间替换day1，比如time()-(time()%3600*24)等等。

想知道特定用户的数量吗?只需要使用SCARD page:day1: 。

需要测试某个特定用户是否访问了这个页面?SISMEMBER page:day1: 。

8、实时分析正在发生的情况，用于数据统计与防止垃圾邮件等

我们只做了几个例子，但如果你研究Redis的命令集，并且组合一下，就能获得大量的实时分析方法，有效而且非常省力。使用Redis原语命令，更容易实施垃圾邮件过滤系统或其他实时跟踪系统。

9、Pub/Sub

Redis的Pub/Sub非常非常简单，运行稳定并且快速。支持模式匹配，能够实时订阅与取消频道。

10、队列

你应该已经注意到像list push和list pop这样的Redis命令能够很方便的执行队列操作了，但能做的可不止这些：比如Redis还有list pop的变体命令，能够在列表为空时阻塞队列。

现代的互联网应用大量地使用了消息队列(Messaging)。消息队列不仅被用于系统内部组件之间的通信，同时也被用于系统跟其它服务之间的交互。消息队列的使用可以增加系统的可扩展性、灵活性和用户体验。非基于消息队列的系统，其运行速度取决于系统中最慢的组件的速度(注：短板效应)。而基于消息队列可以将系统中各组件解除耦合，这样系统就不再受最慢组件的束缚，各组件可以异步运行从而得以更快的速度完成各自的工作。

此外，当服务器处在高并发操作的时候，比如频繁地写入日志文件。可以利用消息队列实现异步处理。从而实现高性能的并发操作。

11、缓存

Redis的缓存部分值得写一篇新文章，我这里只是简单的说一下。Redis能够替代memcached，让你的缓存从只能存储数据变得能够更新数据，因此你不再需要每次都重新生成数据了。

此部分内容的原文地址：http://antirez.com/post/take-advantage-of-redis-adding-it-to-your-stack.html

5. 国内外三个不同领域巨头分享的Redis实战经验及使用场景

随着应用对高性能需求的增加，NoSQL逐渐在各大名企的系统架构中生根发芽。这里我们将为大家分享社交巨头新浪微博、传媒巨头Viacom及图片分享领域佼佼者Pinterest带来的Redis实践，首先我们看新浪微博 @启盼cobain的Redis实战经验分享：

一、新浪微博：史上最大的Redis集群

Tape is Dead，Disk is Tape，Flash is Disk，RAM Locality is King. — Jim Gray

Redis不是比较成熟的memcache或者Mysql的替代品，是对于大型互联网类应用在架构上很好的补充。现在有越来越多的应用也在纷纷基于Redis做架构的改造。首先简单公布一下Redis平台实际情况：

2200+亿 commands/day 5000亿Read/day 500亿Write/day

18TB+ Memory

500+ Servers in 6 IDC 2000+instances

应该是国内外比较大的Redis使用平台，今天主要从应用角度谈谈Redis服务平台。

Redis使用场景

1.Counting(计数)

计数的应用在另外一篇文章里较详细的描述，计数场景的优化 http://www.xdata.me/?p=262这里就不多加描述了。

可以预见的是，有很多同学认为把计数全部存在内存中成本非常高，我在这里用个图表来表达下我的观点：

 

 

很多情况大家都会设想纯使用内存的方案会很有很高成本，但实际情况往往会有一些不一样：

COST，对于有一定吞吐需求的应用来说，肯定会单独申请DB、Cache资源，很多担心DB写入性能的同学还会主动将DB更新记入异步队列，而这三块的资源的利用率一般都不会太高。资源算下来，你惊异的发现：反而纯内存的方案会更精简!

KISS原则，这对于开发是非常友好的，我只需要建立一套连接池，不用担心数据一致性的维护，不用维护异步队列。

Cache穿透风险，如果后端使用DB，肯定不会提供很高的吞吐能力，cache宕机如果没有妥善处理，那就悲剧了。

大多数的起始存储需求，容量较小。

2.Reverse cache(反向cache)

面对微博常常出现的热点，如最近出现了较为火爆的短链，短时间有数以万计的人点击、跳转，而这里会常常涌现一些需求，比如我们向快速在跳转时判定用户等级，是否有一些账号绑定，性别爱好什么的，已给其展示不同的内容或者信息。

普通采用memcache+Mysql的解决方案，当调用id合法的情况下，可支撑较大的吞吐。但当调用id不可控，有较多垃圾用户调用时，由于memcache未有命中，会大量的穿透至Mysql服务器，瞬间造成连接数疯长，整体吞吐量降低，响应时间变慢。

这里我们可以用redis记录全量的用户判定信息，如string key:uid int:type，做一次反向的cache，当用户在redis快速获取自己等级等信息后，再去Mc+Mysql层去获取全量信息。如图：

 

 

当然这也不是最优化的场景，如用Redis做bloomfilter，可能更加省用内存。

3.Top 10 list

产品运营总会让你展示最近、最热、点击率最高、活跃度最高等等条件的top list。很多更新较频繁的列表如果使用MC+MySQL维护的话缓存失效的可能性会比较大，鉴于占用内存较小的情况，使用Redis做存储也是相当不错的。

4.Last Index

用户最近访问记录也是redis list的很好应用场景，lpush lpop自动过期老的登陆记录，对于开发来说还是非常友好的。

5.Relation List/Message Queue

这里把两个功能放在最后，因为这两个功能在现实问题当中遇到了一些困难，但在一定阶段也确实解决了我们很多的问题，故在这里只做说明。

Message Queue就是通过list的lpop及lpush接口进行队列的写入和消费，由于本身性能较好也能解决大部分问题。

6.Fast transaction with Lua

Redis 的Lua的功能扩展实际给Redis带来了更多的应用场景，你可以编写若干command组合作为一个小型的非阻塞事务或者更新逻辑，如：在收到 message推送时，同时1.给自己的增加一个未读的对话 2.给自己的私信增加一个未读消息 3.最后给发送人回执一个完成推送消息，这一层逻辑完全可以在Redis Server端实现。

但是，需要注意的是Redis会将lua script的全部内容记录在aof和传送给slave，这也将是对磁盘，网卡一个不小的开销。

7.Instead of Memcache

很多测试和应用均已证明，

在性能方面Redis并没有落后memcache多少，而单线程的模型给Redis反而带来了很强的扩展性。

在很多场景下，Redis对同一份数据的内存开销是小于memcache的slab分配的。

Redis提供的数据同步功能，其实是对cache的一个强有力功能扩展。

Redis使用的重要点

1.rdb/aof Backup!

我们线上的Redis 95%以上是承担后端存储功能的，我们不仅用作cache，而更为一种k-v存储，他完全替代了后端的存储服务(MySQL)，故其数据是非常重要的，如果出现数据污染和丢失，误操作等情况，将是难以恢复的。所以备份是非常必要的!为此，我们有共享的hdfs资源作为我们的备份池，希望能随时可以还原业务所需数据。

2.Small item & Small instance!

由于Redis单线程(严格意义上不是单线程，但认为对request的处理是单线程的)的模型，大的数据结构list,sorted set,hash set的批量处理就意味着其他请求的等待，故使用Redis的复杂数据结构一定要控制其单key-struct的大小。

另外，Redis单实例的内存容量也应该有严格的限制。单实例内存容量较大后，直接带来的问题就是故障恢复或者Rebuild从库的时候时间较长，而更糟糕的是，Redis rewrite aof和save rdb时，将会带来非常大且长的系统压力，并占用额外内存，很可能导致系统内存不足等严重影响性能的线上故障。我们线上96G/128G内存服务器不建议单实例容量大于20/30G。

3.Been Available!

业界资料和使用比较多的是Redis sentinel(哨兵)

http://www.huangz.me/en/latest/storage/redis_code_analysis/sentinel.html

http://qiita.com/wellflat/items/8935016fdee25d4866d9

2000行C实现了服务器状态检测，自动故障转移等功能。

但由于自身实际架构往往会复杂，或者考虑的角度比较多，为此 @许琦eryk和我一同做了hypnos项目。

hypnos是神话中的睡神，字面意思也是希望我们工程师无需在休息时间处理任何故障。:-)

其工作原理示意如下：

 

 

Talk is cheap, show me your code! 稍后将单独写篇博客细致讲下Hypnos的实现。

4.In Memory or not?

发现一种情况，开发在沟通后端资源设计的时候，常常因为习惯使用和错误了解产品定位等原因，而忽视了对真实使用用户的评估。也许这是一份历史数据，只有最近一天的数据才有人进行访问，而把历史数据的容量和最近一天请求量都抛给内存类的存储现实是非常不合理的。

所以当你在究竟使用什么样的数据结构存储的时候，请务必先进行成本衡量，有多少数据是需要存储在内存中的?有多少数据是对用户真正有意义的。因为这其实对后端资源的设计是至关重要的，1G的数据容量和1T的数据容量对于设计思路是完全不一样的

Plans in future?

1.slave sync改造

全部改造线上master-slave数据同步机制，这一点我们借鉴了MySQL Replication的思路，使用rdb+aof+pos作为数据同步的依据，这里简要说明为什么官方提供的psync没有很好的满足我们的需求：

假设A有两个从库B及C，及 A `— B&C，这时我们发现master A服务器有宕机隐患需要重启或者A节点直接宕机，需要切换B为新的主库，如果A、B、C不共享rdb及aof信息，C在作为B的从库时，仍会清除自身数据，因为C节点只记录了和A节点的同步状况。

故我们需要有一种将A`–B&C 结构切换切换为A`–B`–C结构的同步机制，psync虽然支持断点续传，但仍无法支持master故障的平滑切换。

实际上我们已经在我们定制的Redis计数服务上使用了如上功能的同步，效果非常好，解决了运维负担，但仍需向所有Redis服务推广，如果可能我们也会向官方Redis提出相关sync slave的改进。

2.更适合redis的name-system Or proxy

细心的同学发现我们除了使用DNS作为命名系统，也在zookeeper中有一份记录，为什么不让用户直接访问一个系统，zk或者DNS选择其一呢?

其实还是很简单，命名系统是个非常重要的组件，而dns是一套比较完善的命名系统，我们为此做了很多改进和试错，zk的实现还是相对复杂，我们还没有较强的把控粒度。我们也在思考用什么做命名系统更符合我们需求。

3.后端数据存储

大内存的使用肯定是一个重要的成本优化方向，flash盘及分布式的存储也在我们未来计划之中。(原文链接： Largest Redis Clusters Ever)

二、Pinterest：Reids维护上百亿的相关性

Pinterest已经成为硅谷最疯故事之一，在2012年，他们基于PC的业务增加1047%，移动端采用增加1698%， 该年3月其独立访问数量更飙升至533亿。在Pinterest，人们关注的事物以百亿记——每个用户界面都会查询某个board或者是用户是否关注的行为促成了异常复杂的工程问题。这也让Redis获得了用武之地。经过数年的发展，Pinterest已经成为媒体、社交等多个领域的佼佼者，其辉煌战绩如下：

获得的推荐流量高于Google+、YouTube及LinkedIn三者的总和

与Facebook及Twitter一起成为最流行的三大社交网络

参考Pinterest进行购买的用户比其它网站更高( 更多详情)

如您所想，基于其独立访问数，Pinterest的高规模促成了一个非常高的IT基础设施需求。

 

 

通过缓存来优化用户体验

近日，Pinterest工程经理Abhi Khune对其公司的用户体验需求及Redis的使用经验 进行了分享。即使是滋生的应用程序打造者，在分析网站的细节之前也不会理解这些特性，因此先大致的理解一下使用场景：首先，为每个粉丝进行提及到的预检查;其次，UI将准确的显示用户的粉丝及关注列表分页。高效的执行这些操作，每次点击都需要非常高的性能架构。

不能免俗，Pinterest的软件工程师及架构师已经使用了MySQL及memcache，但是缓存解决方案仍然达到了他们的瓶颈;因此为了拥有更好的用户体验，缓存必须被扩充。而在实际操作过程中，工程团队已然发现缓存只有当用户sub-graph已经在缓存中时才会起到作用。因此。任何使用这个系统的人都需要被缓存，这就导致了整个图的缓存。同时，最常见的查询“用户A是否关注了用户B”的答案经常是否定的，然而这却被作为了缓存丢失，从而促成一个数据库查询，因此他们需要一个新的方法来扩展缓存。最终，他们团队决定使用Redis来存储整个图，用以服务众多的列表。

使用Redis存储大量的Pinterest列表

Pinterest使用了Redis作为解决方案，并将性能推至了内存数据库等级，为用户保存多种类型列表：

关注者列表

你所关注的board列表

粉丝列表

关注你board的用户列表

某个用户中board中你没有关注的列表

每个board的关注者及非关注者

Redis 为其7000万用户存储了以上的所有列表，本质上讲可以说是储存了所有粉丝图，通过用户ID分片。鉴于你可以通过类型来查看以上列表的数据，分析概要信息被用看起来更像事务的系统储存及访问。Pinterest当下的用户like被限制为10万，初略进行统计：如果每个用户关注25个board，将会在用户及board间产生17.5亿的关系。同时更加重要的是，这些关系随着系统的使用每天都会增加。

Pinterest的Reids架构及运营

通过Pinterest的一个创始人了解到，Pinterest开始使用Python及订制的Django编写应用程序，并一直持续到其拥有1800万用户级日410TB用户数据的时候。虽然使用了多个存储对数据进行储存，工程师根据用户id使用了8192个虚拟分片，每个分片都运行在一个Redis DB之上，同时1个Redis实例将运行多个Redis DB。为了对CPU核心的充分使用，同一台主机上同时使用多线程和单线程Redis实例。

鉴于整个数据集运行在内存当中，Redis在Amazon EBS上对每秒传输进来的写入都会进行持久化。扩展主要通过两个方面进行：第一，保持50%的利用率，通过主从转换，机器上运行的Redis实例一半会转译到一个新机器上;第二，扩展节点和分片。整个Redis集群都会使用一个主从配置，从部分将被当做一个热备份。一旦主节点失败，从部分会立刻完成主的转换，同时一个新的从部分将会被添加，ZooKeeper将完成整个过程。同时他们每个小时都会在Amazon S3上运行BGsave做更持久的储存——这项Reids操作会在后端进行，之后Pinterest会使用这些数据做MapReduce和分析作业。(更多内容见原文)

 

 

三、Viacom：Redis在系统中的用例盘点

Viacom是全球最大的传媒集体之一，同时也遭遇了当下最大的数据难题之一：如何处理日益剧增的动态视频内容。

着眼这一挑战的上升趋势，我们会发现：2010年世界上所有数据体积达到ZB级，而单单2012这一年，互联网产生的数据就增加了2.8个ZB，其中大部分的数据都是非结构化的，包括了视频和图片。

覆盖MVN(以前称为MTV Networks、Paramount及BET)，Viacom是个名副其实的传媒巨头，支持众多人气站点，其中包括The Daily Show、osh.0、South Park Studios、GameTrailers.com等。作为媒体公司，这些网站上的文档、图片、视频短片都在无时无刻的更新。长话短说，下面就进入 Viacom高级架构师Michael Venezia 分享的Redis实践：

Viacom的网站架构背景

对于Viacom，横跨多个站点传播内容让必须专注于规模的需求，同时为了将内容竟可能快的传播到相应用户，他们还必须聚焦内容之间的关系。然而即使The Daily Show、Nickelodeon、Spike或者是VH1 这些单独的网站上，日平均PV都可以达到千万，峰值时流量更会达到平均值的20-30倍。同时基于对实时的需求，动态的规模及速度已成为架构的基础之一。

除去动态规模之外，服务还必须基于用户正在浏览的视频或者是地理位置来推测用户的喜好。比如说，某个页面可能会将一个独立的视频片段与本地的促销，视频系列的额外部分，甚至是相关视频联系起来。为了能让用户能在网站上停留更长的时间，他们建立了一个能基于详细元数据自动建立页面的软件引擎，这个引擎可以根据用户当下兴趣推荐额外的内容。鉴于用于兴趣的随时改变，数据的类型非常广泛——类似graph-like，实际上做的是大量的join。

这样做有利于减少类似视频的大体积文件副本数，比如数据存储中一个独立的记录是Southpark片段“Cartman gets an Anal Probe”，这个片段可能也会出现在德语的网站上。虽然视频是一样的，但是英语用户搜索的可能就是另一个不同的词语。元数据的副本转换成搜索结果，并指向相同的视频。因此在美国用户搜索真实标题的情况下，德国浏览者可能会使用转译的标题——德国网站上的“Cartman und die Analsonde”。

这些元数据覆盖了其它记录或者是对象，同时还可以根据使用环境来改变内容，通过不同的规则集来限制不同地理位置或者是设备请求的内容。

Viacom的实现方法

尽管许多机构通过使用ORM及传统关系型数据库来解决这个问题，Viacom却使用了一个迥然不同的方法。

本质上，他们完全承担不了对数据库的直接访问。首先，他们处理的大部分都是流数据，他们偏向于使用Akamai从地理上来分配内容。其次，基于页面的复杂性可能会取上万个对象。取如此多的数据显然会影响到性能，因此JSON在1个数据服务中投入了使用。当然，这些JSON对象的缓存将直接影响到网站性能。同时，当内容或者是内容之间的关系发生改变时，缓存还需要动态的进行更新。

Viacom 依靠对象基元和超类解决这个问题，继续以South Park为例：一个私有的“episode”类包含了所有该片段相关信息，一个“super object”将有助于发现实际的视频对象。超类这个思想确实非常有益于建设低延迟页面的自动建设，这些超类可以帮助到基元对象到缓存的映射及保存。

Viacom为什么要使用Redis

每当Viacom上传一个视频片段，系统将建立一个私有的对象，并于1个超类关联。每一次修改，他们都需要重估私有对象的每个改变，并更新所有复合对象。同时，系统还需要无效Akamail中的URL请求。系统现有架构的组合及更敏捷的管理方法需求将Viacom推向了Redis。

基于Viacom主要基于PHP，所以这个解决方案必须支持PHP。他们首先选择了memcached做对象存储，但是它并不能很好的支持hashmap;同时他们还需要一个更有效的进行无效步骤的重估，即更好的理解内容的依赖性。本质上说，他们需要时刻跟进无效步骤中的依赖性改变。因此他们选择了 Redis及Predis的组合来解决这个问题。

他们团队使用Redis给southparkstudios.com和thedailyshow.com两个网站建设依赖性图，在取得了很大的成功后他们开始着眼Redis其它适合场景。

Redis的其它使用场景

显而易见，如果有人使用Redis来建设依赖性图，那么使用它来做对象处理也是说得通的。同样，这也成了架构团队为Redis选择的第二使用场景。 Redis的复制及持久化特性同时也征服了Viacom的运营团队，因此在几个开发周期后，Redis成为他们网站的主要数据及依赖性储存。

后两个用例则是行为追踪及浏览计数的缓冲，改变后的架构是Redis每几分钟向MySQL中储存一次，而浏览计数则通过Redis进行存储及计数。同时 Redis还被用来做人气的计算，一个基于访问数及访问时间的得分系统——如果某个视频最近被访问的次数越多，它的人气就越高。在如此多内容上每隔 10-15分钟做一次计算绝对不是类似MySQL这样传统关系型数据库的强项，Viacom使用Redis的理由也非常简单——在1个存储浏览信息的 Redis实例上运行Lua批处理作业，计算出所有的得分表。信息被拷贝到另一个Redis实例上，用以支持相关的产品查询。同时还在MySQL上做了另一个备份，用以以后的分析，这种组合会将这个过程耗费的时间降低60倍。

Viacom还使用Redis存储一步作业信息，这些信息被插入一个列表中，工作人员则使用BLPOP命令行在队列中抓取顶端的任务。同时zsets被用于从众多社交网络(比如Twitter及Tumblr)上综合内容，Viacom通过Brightcove视频播放器来同步多个内容管理系统。

横跨这些用例，几乎所有的Redis命令都被使用——sets、lists、zlists、hashmaps、scripts、counters等。同时，Redis也成为Viacom可扩展架构中不可或缺的一环。

simhash处理数据速度虽然很快，但是随着业务的增长，simhash数据也会越来越大，达到海量的时候，处理时间就会很长了，现在我们来看看simhash短文本查找。

前面的 海量数据相似度计算实例 simhash和海明距离 我们介绍了 介绍了simhash的原理，大家应该感觉到了算法的魅力。但是随着业务的增长 simhash的数据也会暴增，如果一天100w，10天就1000w了。我们如果插入一条数据就要去比较1000w次的simhash，计算量还是蛮大，普通PC 比较1000w次海明距离需要 300ms ，和5000w数据比较需要1.8 s。看起来相似度计算不是很慢，还在秒级别。给大家算一笔账就知道了：

随着业务增长需要一个小时处理100w次，一个小时为3600 *1000 = 360w毫秒，计算一下一次相似度比较最多只能消耗 360w / 100w = 3.6毫秒。300ms慢吗，慢!1.8S慢吗，太慢了!很多情况大家想的就是升级、增加机器，但有些时候光是增加机器已经解决不了问题了，就算增加机器也不是短时间能够解决的，需要考虑分布式、客户预算、问题解决的容忍时间?头大时候要相信人类的智慧是无穷的，泡杯茶，听下轻音乐：)畅想下宇宙有多大，宇宙外面还有什么东西，程序员有什么问题能够难倒呢?

加上客户还提出的几个，汇总一下技术问题：

1、一个小时需要比较100w次，也就是每条数据和simhash库里的数据比较需要做到3.6毫秒。

2、两条同一时刻发出的文本如果重复也只能保留一条。

3、希望保留2天的数据进行比较去重，按照目前的量级和未来的增长，2天大概在2000w — 5000w 中间。

4、短文本和长文本都要去重，经过测试长文本使用simhash效果很好，短文本使用simhash 准备度不高。

目前我们估算一下存储空间的大小，就以JAVA 来说，存储一个simhash 需要一个原生态 lang 类型是64位 = 8 byte，如果是 Object 对象还需要额外的 8 byte，所以我们尽量节约空间使用原生态的lang类型。假设增长到最大的5000w数据， 5000w * 8byte = 400000000byte = 400000000/( 1024 * 1024) = 382 Mb，所以按照这个大小普通PC服务器就可以支持，这样第三个问题就解决了。

比较5000w次怎么减少时间呢?其实这也是一个查找的过程，我们想想以前学过的查找算法： 顺序查找、二分查找、二叉排序树查找、索引查找、哈希查找。不过我们这个不是比较数字是否相同，而是比较海明距离，以前的算法并不怎么通用，不过解决问题的过程都是通用的。还是和以前一样，不使用数学公式，使用程序猿大家都理解的方式。还记得JAVA里有个HashMap吗?我们要查找一个key值时，通过传入一个key就可以很快的返回一个value，这个号称查找速度最快的数据结构是如何实现的呢?看下hashmap的内部结构：

 

 

如果我们需要得到key对应的value，需要经过这些计算，传入key，计算key的hashcode，得到7的位置;发现7位置对应的 value还有好几个，就通过链表查找，直到找到v72。其实通过这么分析，如果我们的hashcode设置的不够好，hashmap的效率也不见得高。借鉴这个算法，来设计我们的simhash查找。通过顺序查找肯定是不行的，能否像hashmap一样先通过键值对的方式减少顺序比较的次数。看下图：

 

 

存储：

1、将一个64位的simhash code拆分成4个16位的二进制码。(图上红色的16位)

2、分别拿着4个16位二进制码查找当前对应位置上是否有元素。(放大后的16位)

3、对应位置没有元素，直接追加到链表上;对应位置有则直接追加到链表尾端。(图上的 S1 — SN)

查找：

1、将需要比较的simhash code拆分成4个16位的二进制码。

2、分别拿着4个16位二进制码每一个去查找simhash集合对应位置上是否有元素。

2、如果有元素，则把链表拿出来顺序查找比较，直到simhash小于一定大小的值，整个过程完成。

原理：

借鉴hashmap算法找出可以hash的key值，因为我们使用的simhash是局部敏感哈希，这个算法的特点是只要相似的字符串只有个别的位数是有差别变化。那这样我们可以推断两个相似的文本，至少有16位的simhash是一样的。具体选择16位、8位、4位，大家根据自己的数据测试选择，虽然比较的位数越小越精准，但是空间会变大。分为4个16位段的存储空间是单独simhash存储空间的4倍。之前算出5000w数据是 382 Mb，扩大4倍1.5G左右，还可以接受：)

通过这样计算，我们的simhash查找过程全部降到了1毫秒以下。就加了一个hash效果这么厉害?我们可以算一下，原来是5000w次顺序比较，现在是少了2的16次方比较，前面16位变成了hash查找。后面的顺序比较的个数是多少? 2^16 = 65536， 5000w/65536 = 763 次。。。。实际最后链表比较的数据也才 763次!所以效率大大提高!

到目前第一点降到3.6毫秒、支持5000w数据相似度比较做完了。还有第二点同一时刻发出的文本如果重复也只能保留一条和短文本相识度比较怎么解决。其实上面的问题解决了，这两个就不是什么问题了。

之前的评估一直都是按照线性计算来估计的，就算有多线程提交相似度计算比较，我们提供相似度计算服务器也需要线性计算。比如同时客户端发送过来两条需要比较相似度的请求，在服务器这边都进行了一个排队处理，一个接着一个，第一个处理完了在处理第二个，等到第一个处理完了也就加入了simhash 库。所以只要服务端加了队列，就不存在同时请求不能判断的情况。

simhash如何处理短文本?换一种思路，simhash可以作为局部敏感哈希第一次计算缩小整个比较的范围，等到我们只有比较700多次比较时，就算使用我们之前精准度高计算很慢的编辑距离也可以搞定。当然如果觉得慢了，也可以使用余弦夹角等效率稍微高点的相似度算法。

simHash是用来网页去重最常用的hash方法，速度很快。海明距离是在信息编码中，两个合法代码对应位上编码不同的位数称为码距。

通过 采集系统 我们采集了大量文本数据，但是文本中有很多重复数据影响我们对于结果的分析。分析前我们需要对这些数据去除重复，如何选择和设计文本的去重算法?常见的有余弦夹角算法、欧式距离、Jaccard相似度、最长公共子串、编辑距离等。这些算法对于待比较的文本数据不多时还比较好用，如果我们的爬虫每天采集的数据以千万计算，我们如何对于这些海量千万级的数据进行高效的合并去重。最简单的做法是拿着待比较的文本和数据库中所有的文本比较一遍如果是重复的数据就标示为重复。看起来很简单，我们来做个测试，就拿最简单的两个数据使用Apache提供的 Levenshtein for 循环100w次计算这两个数据的相似度。代码结果如下：

String s1 = "你妈妈喊你回家吃饭哦，回家罗回家罗" ;
String s2 = "你妈妈叫你回家吃饭啦，回家罗回家罗" ;

long t1 = System.currentTimeMillis();

for (int i = 0; i < 1000000; i++) {
       int dis = StringUtils .getLevenshteinDistance(s1, s2);
}

long t2 = System.currentTimeMillis();

System. out .println(" 耗费时间： " + (t2 - t1) + "  ms ");

耗费时间： 4266 ms

大跌眼镜，居然计算耗费4秒。假设我们一天需要比较100w次，光是比较100w次的数据是否重复就需要4s，就算4s一个文档，单线程一分钟才处理15个文档，一个小时才900个，一天也才21600个文档，这个数字和一天100w相差甚远，需要多少机器和资源才能解决。

为此我们需要一种应对于海量数据场景的去重方案，经过研究发现有种叫 local sensitive hash 局部敏感哈希 的东西，据说这玩意可以把文档降维到hash数字，数字两两计算运算量要小很多。查找很多文档后看到google对于网页去重使用的是simhash，他们每天需要处理的文档在亿级别，大大超过了我们现在文档的水平。既然老大哥也有类似的应用，我们也赶紧尝试下。simhash是由 Charikar 在2002年提出来的，参考 《Similarity estimation techniques from rounding algorithms》 。 介绍下这个算法主要原理，为了便于理解尽量不使用数学公式，分为这几步：

1、分词，把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重，我们假设权重分为5个级别(1~5)。比如：“ 美国“51区”雇员称内部有9架飞碟，曾看见灰色外星人 ” ==> 分词后为 “ 美国(4) 51区(5) 雇员(3) 称(1) 内部(2) 有(1) 9架(3) 飞碟(5) 曾(1) 看见(3) 灰色(4) 外星人(5)”，括号里是代表单词在整个句子里重要程度，数字越大越重要。

2、hash，通过hash算法把每个词变成hash值，比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字，还记得文章开头说过的吗，要把文章变为数字计算才能提高相似度计算性能，现在是降维过程进行时。

3、加权，通过 2步骤的hash生成结果，需要按照单词的权重形成加权数字串，比如“美国”的hash值为“100101”，通过加权计算为“4 -4 -4 4 -4 4”;“51区”的hash值为“101011”，通过加权计算为 “ 5 -5 5 -5 5 5”。

4、合并，把上面各个单词算出来的序列值累加，变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”，“51区”的 “ 5 -5 5 -5 5 5”， 把每一位进行累加， “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的，真实计算需要把所有单词的序列串累加。

5、降维，把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串，形成我们最终的simhash签名。 如果每一位大于0 记为 1，小于0 记为 0。最后算出结果为：“1 0 1 0 1 1”。

整个过程图为：

 

 

大家可能会有疑问，经过这么多步骤搞这么麻烦，不就是为了得到个 0 1 字符串吗?我直接把这个文本作为字符串输入，用hash函数生成 0 1 值更简单。其实不是这样的，传统hash函数解决的是生成唯一值，比如 md5、hashmap等。md5是用于生成唯一签名串，只要稍微多加一个字符md5的两个数字看起来相差甚远;hashmap也是用于键值对查找，便于快速插入和查找的数据结构。不过我们主要解决的是文本相似度计算，要比较的是两个文章是否相识，当然我们降维生成了hashcode也是用于这个目的。看到这里估计大家就明白了，我们使用的simhash就算把文章中的字符串变成 01 串也还是可以用于计算相似度的，而传统的hashcode却不行。我们可以来做个测试，两个相差只有一个字符的文本串，“你妈妈喊你回家吃饭哦，回家罗回家罗” 和 “你妈妈叫你回家吃饭啦，回家罗回家罗”。

通过simhash计算结果为：

1000010010101101111111100000101011010001001111100001001011001011

1000010010101101011111100000101011010001001111100001101010001011

通过 hashcode计算为：

1111111111111111111111111111111110001000001100110100111011011110

1010010001111111110010110011101

大家可以看得出来，相似的文本只有部分 01 串变化了，而普通的hashcode却不能做到，这个就是局部敏感哈希的魅力。目前Broder提出的shingling算法和Charikar的 simhash算法应该算是业界公认比较好的算法。在simhash的发明人Charikar的论文中并没有给出具体的simhash算法和证明，“量子图灵”得出的证明simhash是由随机超平面hash算法演变而来的。

现在通过这样的转换，我们把库里的文本都转换为simhash 代码，并转换为long类型存储，空间大大减少。现在我们虽然解决了空间，但是如何计算两个simhash的相似度呢?难道是比较两个simhash的 01有多少个不同吗?对的，其实也就是这样，我们通过海明距离(Hamming distance)就可以计算出两个simhash到底相似不相似。两个simhash对应二进制(01串)取值不同的数量称为这两个simhash的海明距离。举例如下： 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同，则海明距离为3。对于二进制字符串的a和b，海明距离为等于在a XOR b运算结果中1的个数(普遍算法)。

为了高效比较，我们预先加载了库里存在文本并转换为simhash code 存储在内存空间。来一条文本先转换为 simhash code，然后和内存里的simhash code 进行比较，测试100w次计算在100ms。速度大大提升。

未完待续：

1、目前速度提升了但是数据是不断增量的，如果未来数据发展到一个小时100w，按现在一次100ms，一个线程处理一秒钟 10次，一分钟 60 * 10 次，一个小时 60*10 *60 次 = 36000次，一天 60*10*60*24 = 864000次。 我们目标是一天100w次，通过增加两个线程就可以完成。但是如果要一个小时100w次呢?则需要增加30个线程和相应的硬件资源保证速度能够达到，这样成本也上去了。能否有更好的办法，提高我们比较的效率?

2、通过大量测试，simhash用于比较大文本，比如500字以上效果都还蛮好，距离小于3的基本都是相似，误判率也比较低。但是如果我们处理的是微博信息，最多也就140个字，使用simhash的效果并不那么理想。看如下图，在距离为3时是一个比较折中的点，在距离为10时效果已经很差了，不过我们测试短文本很多看起来相似的距离确实为10。如果使用距离为3，短文本大量重复信息不会被过滤，如果使用距离为10，长文本的错误率也非常高，如何解决?

 

 

下面给各位介绍一个Memcached分布式部署方案设计（含PHP代码），有需要了解的朋友不防进来看看

一台Memcache通常不能满足我们的需求，这就需要分布式部署。Memcached分布式部署方案通常会采用两种方式，一种是普通Hash分布，一种是一致性Hash分布。本篇将以PHP作为客户端，来分析两种方案。
    一、普通Hash分布：
<?php
function test($key='name'){
    $md5 = substr(md5($key), 0, 8);
    $seed = 31;
    $hash = 0;
    for($i=0; $i<8; $i++){
        $hash = $hash * $seed + ord($md5[$i]);
    }
    return $hash & 0x7FFFFFFF;
}

$memcacheList = array(
        array('host'=>'192.168.1.2', 'port'=>6379),
        array('host'=>'192.168.1.3', 'port'=>6379),
        array('host'=>'192.168.1.4', 'port'=>6379),
        array('host'=>'192.168.1.5', 'port'=>6379),
);
$key = 'username';
$value = 'lane';
//根据KEY获取hash
$hash = $this->test($key);
$count = count($memcacheList);
$memcache = $memcacheList[$hash % $count];
$mc = new Memcached($memcache);
$mc->set($key, $value);
?>

代码很简单，一个Hash函数，根据所需要的key，将他md5后取前8位，然后经过Hash算法返回一个整数。将这个整数对服务器总数求模。得到的就是服务器列表的编号。这种方式的缺点是服务器数量改变后，同一个key不同hash，将取不到值了。

二、一致性Hash分布

一致性Hash尽管也会造成数据的丢失，但是损失是最小的。
将2的32次方-1想象成一个圆环，服务器列表在上面排列。根据key通过hash算法求得在圆环上的位置，那么所需要的服务器的位置在key的位置前面最近的一个（顺时针）。

<?php
class FlexiHash{
    //服务器列表
    private $serverList = array();
    //是否排序
    private $isSort = false;

    /**
     * Description: Hash函数，将传入的key以整数形式返回
     * @param string $key
     * @return int
     */
    private function myHash($key){
        $md5 = substr(md5($key), 0, 8);
        $seed = 31;
        $hash = 0;
        for($i=0; $i<8; $i++){
            $hash = $hash * $seed + ord($md5[$i]);
        }
        return $hash & 0x7FFFFFFF;
    }

    /**
     * Description: 添加新服务器
     * @param $server
     */
    public function addServer($server){
        $hash = $this->myHash($server);
        if(!isset($this->serverList[$hash])){
            $this->serverList[$hash] = $server;
        }
        $this->isSort = false;
        return true;
    }

    /**
     * Description: 删除指定服务器
     * @param $server
     * @return bool
     */
    public function removeServer($server){
        $hash = $this->myHash($server);
        if(isset($this->serverList[$hash])){
            unset($this->serverList[$hash]);
        }
        $this->isSort = false;
        return true;
    }

    /**
     * Description: 根据要操作的KEY返回一个操作的服务器信息
     * @param $key
     * @return mixed
     */
    public function lookup($key){
        //将指定的KEYhash出一个整数
        $hash = $this->myHash($key);
        if($this->isSort !== true){
            krsort($this->serverList);
            $this->isSort = false;
        }
        foreach($this->serverList as $key=>$server){
            if($key <= $hash){
                return $server;
            }
        }
        return array_pop($this->serverList);
    }
}
//使用方法
$mc = new FlexiHash();
$mc->addServer('192.168.1.2');
$mc->addServer('192.168.1.3');
$mc->addServer('192.168.1.4');
$mc->addServer('192.168.1.5');

echo 'KEY=key1时，操作的服务器为：'.$mc->lookup('key1').'<br>';
echo 'KEY=key1时，操作的服务器为：'.$mc->lookup('key2').'<br>';
echo 'KEY=key1时，操作的服务器为：'.$mc->lookup('key3').'<br>';
echo 'KEY=key1时，操作的服务器为：'.$mc->lookup('key4').'<br>';
echo 'KEY=key1时，操作的服务器为：'.$mc->lookup('key5').'<br>';
?>