按照上一节中《搭建高可用mongodb集群(三)—— 深入副本集》搭建后还有两个问题没有解决:

  • 从节点每个上面的数据都是对数据库全量拷贝,从节点压力会不会过大?
  • 数据压力大到机器支撑不了的时候能否做到自动扩展?

在系统早期,数据量还小的时候不会引起太大的问题,但是随着数据量持续增多,后续迟早会出现一台机器硬件瓶颈问题的。而mongodb主打的就是海量数据架构,他不能解决海量数据怎么行!不行!“分片”就用这个来解决这个问题。

传统数据库怎么做海量数据读写?其实一句话概括:分而治之。上图看看就清楚了,如下 taobao岳旭强在infoq中提到的 架构图:

fenpian1

上图中有个TDDL,是taobao的一个数据访问层组件,他主要的作用是SQL解析、路由处理。根据应用的请求的功能解析当前访问的sql判断是在哪个业务数据库、哪个表访问查询并返回数据结果。具体如图:

fenpian2

说了这么多传统数据库的架构,那Nosql怎么去做到了这些呢?mysql要做到自动扩展需要加一个数据访问层用程序去扩展,数据库的增加、删除、备份还需要程序去控制。一但数据库的节点一多,要维护起来也是非常头疼的。不过mongodb所有的这一切通过他自己的内部机制就可以搞定!顿时石化了,这么牛X!还是上图看看mongodb通过哪些机制实现路由、分片:

fenpian3

从图中可以看到有四个组件:mongos、config server、shard、replica set。

mongos,数据库集群请求的入口,所有的请求都通过mongos进行协调,不需要在应用程序添加一个路由选择器,mongos自己就是一个请求分发中心,它负责把对应的数据请求请求转发到对应的shard服务器上。在生产环境通常有多mongos作为请求的入口,防止其中一个挂掉所有的mongodb请求都没有办法操作。

config server,顾名思义为配置服务器,存储所有数据库元信息(路由、分片)的配置。mongos本身没有物理存储分片服务器和数据路由信息,只是缓存在内存里,配置服务器则实际存储这些数据。mongos第一次启动或者关掉重启就会从 config server 加载配置信息,以后如果配置服务器信息变化会通知到所有的 mongos 更新自己的状态,这样 mongos 就能继续准确路由。在生产环境通常有多个 config server 配置服务器,因为它存储了分片路由的元数据,这个可不能丢失!就算挂掉其中一台,只要还有存货, mongodb集群就不会挂掉。

shard,这就是传说中的分片了。上面提到一个机器就算能力再大也有天花板,就像军队打仗一样,一个人再厉害喝血瓶也拼不过对方的一个师。俗话说三个臭皮匠顶个诸葛亮,这个时候团队的力量就凸显出来了。在互联网也是这样,一台普通的机器做不了的多台机器来做,如下图:

fenpian4

一台机器的一个数据表 Collection1 存储了 1T 数据,压力太大了!在分给4个机器后,每个机器都是256G,则分摊了集中在一台机器的压力。也许有人问一台机器硬盘加大一点不就可以了,为什么要分给四台机器呢?不要光想到存储空间,实际运行的数据库还有硬盘的读写、网络的IO、CPU和内存的瓶颈。在mongodb集群只要设置好了分片规则,通过mongos操作数据库就能自动把对应的数据操作请求转发到对应的分片机器上。在生产环境中分片的片键可要好好设置,这个影响到了怎么把数据均匀分到多个分片机器上,不要出现其中一台机器分了1T,其他机器没有分到的情况,这样还不如不分片!

replica set,上两节已经详细讲过了这个东东,怎么这里又来凑热闹!其实上图4个分片如果没有 replica set 是个不完整架构,假设其中的一个分片挂掉那四分之一的数据就丢失了,所以在高可用性的分片架构还需要对于每一个分片构建 replica set 副本集保证分片的可靠性。生产环境通常是 2个副本 + 1个仲裁。

说了这么多,还是来实战一下如何搭建高可用的mongodb集群:

首先确定各个组件的数量,mongos 3个, config server 3个,数据分3片 shard server 3个,每个shard 有一个副本一个仲裁也就是 3 * 2 = 6 个,总共需要部署15个实例。这些实例可以部署在独立机器也可以部署在一台机器,我们这里测试资源有限,只准备了 3台机器,在同一台机器只要端口不同就可以,看一下物理部署图:

fenpian5

架构搭好了,安装软件!

  • 1、准备机器,IP分别设置为: 192.168.0.136、192.168.0.137、192.168.0.138。
  • 2、分别在每台机器上建立mongodb分片对应测试文件夹。
    #存放mongodb数据文件
    mkdir -p /data/mongodbtest
    
    #进入mongodb文件夹
    cd  /data/mongodbtest
    
  • 3、下载mongodb的安装程序包
    wget http://fastdl.mongodb.org/linux/mongodb-linux-x86_64-2.4.8.tgz
    
    
    #解压下载的压缩包
    tar xvzf mongodb-linux-x86_64-2.4.8.tgz
    
  • 4、分别在每台机器建立mongos 、config 、 shard1 、shard2、shard3 五个目录。
    因为mongos不存储数据,只需要建立日志文件目录即可。

               #建立mongos目录
               mkdir -p /data/mongodbtest/mongos/log
    
               #建立config server 数据文件存放目录
               mkdir -p /data/mongodbtest/config/data
    
               #建立config server 日志文件存放目录
               mkdir -p /data/mongodbtest/config/log
    
               #建立config server 日志文件存放目录
               mkdir -p /data/mongodbtest/mongos/log
    
               #建立shard1 数据文件存放目录
               mkdir -p /data/mongodbtest/shard1/data
    
               #建立shard1 日志文件存放目录
               mkdir -p /data/mongodbtest/shard1/log
    
               #建立shard2 数据文件存放目录
               mkdir -p /data/mongodbtest/shard2/data
    
    #建立shard2 日志文件存放目录
    mkdir -p /data/mongodbtest/shard2/log
    
    #建立shard3 数据文件存放目录
    mkdir -p /data/mongodbtest/shard3/data
    
    #建立shard3 日志文件存放目录
    mkdir -p /data/mongodbtest/shard3/log
    
  • 5、规划5个组件对应的端口号,由于一个机器需要同时部署 mongos、config server 、shard1、shard2、shard3,所以需要用端口进行区分。
    这个端口可以自由定义,在本文 mongos为 20000, config server 为 21000, shard1为 22001 , shard2为22002, shard3为22003.
  • 6、在每一台服务器分别启动配置服务器。
                 /data/mongodbtest/mongodb-linux-x86_64-2.4.8/bin/mongod --configsvr --dbpath /data/mongodbtest/config/data --port 21000 --logpath /data/mongodbtest/config/log/config.log --fork
    
  • 7、在每一台服务器分别启动mongos服务器。
    /data/mongodbtest/mongodb-linux-x86_64-2.4.8/bin/mongos  --configdb 192.168.0.136:21000,192.168.0.137:21000,192.168.0.138:21000  --port 20000   --logpath  /data/mongodbtest/mongos/log/mongos.log --fork
    
  • 8、配置各个分片的副本集。
    #在每个机器里分别设置分片1服务器及副本集shard1
    /data/mongodbtest/mongodb-linux-x86_64-2.4.8/bin/mongod --shardsvr --replSet shard1 --port 22001 --dbpath /data/mongodbtest/shard1/data  --logpath /data/mongodbtest/shard1/log/shard1.log --fork --nojournal  --oplogSize 10
    

    为了快速启动并节约测试环境存储空间,这里加上 nojournal 是为了关闭日志信息,在我们的测试环境不需要初始化这么大的redo日志。同样设置 oplogsize是为了降低 local 文件的大小,oplog是一个固定长度的 capped collection,它存在于”local”数据库中,用于记录Replica Sets操作日志。注意,这里的设置是为了测试!

    #在每个机器里分别设置分片2服务器及副本集shard2
    /data/mongodbtest/mongodb-linux-x86_64-2.4.8/bin/mongod --shardsvr --replSet shard2 --port 22002 --dbpath /data/mongodbtest/shard2/data  --logpath /data/mongodbtest/shard2/log/shard2.log --fork --nojournal  --oplogSize 10
    
     
    #在每个机器里分别设置分片3服务器及副本集shard3 
    /data/mongodbtest/mongodb-linux-x86_64-2.4.8/bin/mongod --shardsvr --replSet shard3 --port 22003 --dbpath /data/mongodbtest/shard3/data  --logpath /data/mongodbtest/shard3/log/shard3.log --fork --nojournal  --oplogSize 10
    

    分别对每个分片配置副本集,深入了解副本集参考本系列前几篇文章。

    任意登陆一个机器,比如登陆192.168.0.136,连接mongodb

               
    #设置第一个分片副本集
    /data/mongodbtest/mongodb-linux-x86_64-2.4.8/bin/mongo  127.0.0.1:22001
    
                        
    #使用admin数据库
    use admin
    
    #定义副本集配置
    config = { _id:"shard1", members:[
                         {_id:0,host:"192.168.0.136:22001"},
                         {_id:1,host:"192.168.0.137:22001"},
                         {_id:2,host:"192.168.0.138:22001",arbiterOnly:true}
                    ]
             }
    
    #初始化副本集配置
    rs.initiate(config);
    
     
    #设置第二个分片副本集
    /data/mongodbtest/mongodb-linux-x86_64-2.4.8/bin/mongo  127.0.0.1:22002
    
                         
    #使用admin数据库
    use admin
    
     
    #定义副本集配置
    config = { _id:"shard2", members:[
                         {_id:0,host:"192.168.0.136:22002"},
                         {_id:1,host:"192.168.0.137:22002"},
                         {_id:2,host:"192.168.0.138:22002",arbiterOnly:true}
                    ]
             }
    
     
    #初始化副本集配置
    rs.initiate(config);
    
    #设置第三个分片副本集
    /data/mongodbtest/mongodb-linux-x86_64-2.4.8/bin/mongo    127.0.0.1:22003
    
                         
    #使用admin数据库
    use admin
    
     
    #定义副本集配置
    config = { _id:"shard3", members:[
                         {_id:0,host:"192.168.0.136:22003"},
                         {_id:1,host:"192.168.0.137:22003"},
                         {_id:2,host:"192.168.0.138:22003",arbiterOnly:true}
                    ]
             }
    
    #初始化副本集配置
    rs.initiate(config);
    
  • 9、目前搭建了mongodb配置服务器、路由服务器,各个分片服务器,不过应用程序连接到 mongos 路由服务器并不能使用分片机制,还需要在程序里设置分片配置,让分片生效。
    #连接到mongos
    /data/mongodbtest/mongodb-linux-x86_64-2.4.8/bin/mongo  127.0.0.1:20000
    
    #使用admin数据库
    user  admin
    
     
    #串联路由服务器与分配副本集1
    db.runCommand( { addshard : "shard1/192.168.0.136:22001,192.168.0.137:22001,192.168.0.138:22001"});
    

    如里shard是单台服务器,用 db.runCommand( { addshard : “[: ]” } )这样的命令加入,如果shard是副本集,用db.runCommand( { addshard : “replicaSetName/[:port][,serverhostname2[:port],…]” });这样的格式表示 。

    #串联路由服务器与分配副本集2
    db.runCommand( { addshard : "shard2/192.168.0.136:22002,192.168.0.137:22002,192.168.0.138:22002"});
    
    #串联路由服务器与分配副本集3
    db.runCommand( { addshard : "shard3/192.168.0.136:22003,192.168.0.137:22003,192.168.0.138:22003"});
    
    #查看分片服务器的配置
    db.runCommand( { listshards : 1 } );
    

    #内容输出

            {
                     "shards" : [
                            {
                                    "_id" : "shard1",
                                    "host" : "shard1/192.168.0.136:22001,192.168.0.137:22001"
                            },
                            {
                                    "_id" : "shard2",
                                    "host" : "shard2/192.168.0.136:22002,192.168.0.137:22002"
                            },
                            {
                                    "_id" : "shard3",
                                    "host" : "shard3/192.168.0.136:22003,192.168.0.137:22003"
                            }
                    ],
                    "ok" : 1
            }

    因为192.168.0.138是每个分片副本集的仲裁节点,所以在上面结果没有列出来。

  • 10、目前配置服务、路由服务、分片服务、副本集服务都已经串联起来了,但我们的目的是希望插入数据,数据能够自动分片,就差那么一点点,一点点。。。

    连接在mongos上,准备让指定的数据库、指定的集合分片生效。

    #指定testdb分片生效
    db.runCommand( { enablesharding :"testdb"});
    #指定数据库里需要分片的集合和片键
    db.runCommand( { shardcollection : "testdb.table1",key : {id: 1} } )

    我们设置testdb的 table1 表需要分片,根据 id 自动分片到 shard1 ,shard2,shard3 上面去。要这样设置是因为不是所有mongodb 的数据库和表 都需要分片!

  • 11、测试分片配置结果。
    #连接mongos服务器
    /data/mongodbtest/mongodb-linux-x86_64-2.4.8/bin/mongo  127.0.0.1:20000
    #使用testdb
    use  testdb;
     
    #插入测试数据
    for (var i = 1; i <= 100000; i++) 
    db.table1.save({id:i,"test1":"testval1"});
     
    #查看分片情况如下,部分无关信息省掉了
    db.table1.stats();
                  {
                          "sharded" : true,
                          "ns" : "testdb.table1",
                          "count" : 100000,
                          "numExtents" : 13,
                          "size" : 5600000,
                          "storageSize" : 22372352,
                          "totalIndexSize" : 6213760,
                          "indexSizes" : {
                                  "_id_" : 3335808,
                                  "id_1" : 2877952
                          },
                          "avgObjSize" : 56,
                          "nindexes" : 2,
                          "nchunks" : 3,
                          "shards" : {
                                  "shard1" : {
                                          "ns" : "testdb.table1",
                                          "count" : 42183,
                                          "size" : 0,
                                          ...
                                          "ok" : 1
                                  },
                                  "shard2" : {
                                          "ns" : "testdb.table1",
                                          "count" : 38937,
                                          "size" : 2180472,
                                          ...
                                          "ok" : 1
                                  },
                                  "shard3" : {
                                          "ns" : "testdb.table1",
                                          "count" :18880,
                                          "size" : 3419528,
                                          ...
                                          "ok" : 1
                                  }
                          },
                          "ok" : 1
                  }
    

    可以看到数据分到3个分片,各自分片数量为: shard1 “count” : 42183,shard2 “count” : 38937,shard3 “count” : 18880。已经成功了!不过分的好像不是很均匀,所以这个分片还是很有讲究的,后续再深入讨论。

  • 12、java程序调用分片集群,因为我们配置了三个mongos作为入口,就算其中哪个入口挂掉了都没关系,使用集群客户端程序如下:
    public class TestMongoDBShards {
    
           public static void main(String[] args) {
    
                 try {
                      List<ServerAddress> addresses = new ArrayList<ServerAddress>();
                      ServerAddress address1 = new ServerAddress("192.168.0.136" , 20000);
                      ServerAddress address2 = new ServerAddress("192.168.0.137" , 20000);
                      ServerAddress address3 = new ServerAddress("192.168.0.138" , 20000);
                      addresses.add(address1);
                      addresses.add(address2);
                      addresses.add(address3);
    
                      MongoClient client = new MongoClient(addresses);
                      DB db = client.getDB( "testdb" );
                      DBCollection coll = db.getCollection( "table1" );
    
                      BasicDBObject object = new BasicDBObject();
                      object.append( "id" , 1);
    
                      DBObject dbObject = coll.findOne(object);
    
                      System. out .println(dbObject);
    
                } catch (Exception e) {
                      e.printStackTrace();
                }
          }
    }
    
    

整个分片集群搭建完了,思考一下我们这个架构是不是足够好呢?其实还有很多地方需要优化,比如我们把所有的仲裁节点放在一台机器,其余两台机器承担了全部读写操作,但是作为仲裁的192.168.0.138相当空闲。让机器3 192.168.0.138多分担点责任吧!架构可以这样调整,把机器的负载分的更加均衡一点,每个机器既可以作为主节点、副本节点、仲裁节点,这样压力就会均衡很多了,如图:

fenpian6

当然生产环境的数据远远大于当前的测试数据,大规模数据应用情况下我们不可能把全部的节点像这样部署,硬件瓶颈是硬伤,只能扩展机器。要用好mongodb还有很多机制需要调整,不过通过这个东东我们可以快速实现高可用性、高扩展性,所以它还是一个非常不错的Nosql组件。

再看看我们使用的mongodb java 驱动客户端 MongoClient(addresses),这个可以传入多个mongos 的地址作为mongodb集群的入口,并且可以实现自动故障转移,但是负载均衡做的好不好呢?打开源代码查看:

fenpian7

它的机制是选择一个ping 最快的机器来作为所有请求的入口,如果这台机器挂掉会使用下一台机器。那这样。。。。肯定是不行的!万一出现双十一这样的情况所有请求集中发送到这一台机器,这台机器很有可能挂掉。一但挂掉了,按照它的机制会转移请求到下台机器,但是这个压力总量还是没有减少啊!下一台还是可能崩溃,所以这个架构还有漏洞!不过这个文章已经太长了,后续解决吧。

参考:
http://docs.mongodb.org/manual/core/sharding-introduction/

原创文章,转载请注明: 转载自LANCEYAN.COM

本文链接地址: 搭建高可用mongodb集群(四)—— 分片

在前一篇文章 《海量数据相似度计算之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的内部结构:

java hashmap内部结构

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

大规模simhash算法优化

存储
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与重复信息识别

原创文章,转载请注明: 转载自LANCEYAN.COM

本文链接地址: 海量数据相似度计算之simhash短文本查找

通过 采集系统 我们采集了大量文本数据,但是文本中有很多重复数据影响我们对于结果的分析。分析前我们需要对这些数据去除重复,如何选择和设计文本的去重算法?常见的有余弦夹角算法、欧式距离、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”。

整个过程图为:

simhash计算过程图

大家可能会有疑问,经过这么多步骤搞这么麻烦,不就是为了得到个 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的海明距离。举例如下: 1010100110 从第一位开始依次有第一位、第四、第五位不同,则海明距离为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,长文本的错误率也非常高,如何解决?

simhash_hammingdistance

参考:
Detecting near-duplicates for web crawling.

Similarity estimation techniques from rounding algorithms.

http://en.wikipedia.org/wiki/Locality_sensitive_hashing

http://en.wikipedia.org/wiki/Hamming_distance

simHash 简介以及 java 实现

simhash原理推导

原创文章,转载请注明: 转载自LANCEYAN.COM

本文链接地址: 海量数据相似度计算之simhash和海明距离