对Google算法优越性的一点小体会

zszyj

原帖由 yuhe27913 于 2008-6-27 01:10 发表

我支持这个说法，绝对是输入第一个字符的时候就开始过滤，不然没那么快的。有些网站根本没有“检测帐号是否可用”这个按钮。你再填写下一栏的时候帐号是否可用就已经出结果了。

你说的这种说法, 适合于小规模网站,每输入一个字符,就往服务器提交一次查询请求. 但对于大型网站,我认为是不合适的, 这会给服务器增加了数倍的压力. 其实前面已经有人提到了,数据库查询是很快的, 生成网页显示内容也是很快的, 真正造成延时的是网络传输时间. 在这种情况下,每按一个字符就检测一下,明显是没有必要的,也是不合适的.

lose

原帖由 wwwsq 于 2008-6-27 06:16 发表



很多事情其实去做做就可以了，没你想的那么难。大多数时候数据库确实可以解决问题，但是你要看到，也有很多时候，通用数据库并不是最佳解决方案。

布隆过滤器并不是什么很难的技术，只是你愿不愿意去掌 ...

我觉得你这些说的非常好，这也是为什么google选择在email名字查找上使用这个算法。
想把大家都说过的话重复一次，还是要看需求是什么。向我这样google外面人士，对这些需求如果没有仔细研究的话，很有可能觉得其他方法更好。

shan_ghost

http://googlechinablog.com/2007/07/bloom-filter.html

闹了半天，原来有人到现在都还不知道我们在说什么啊。

打一耳光，打一耳光。（楼上某位：哪里在响？打的不是我。一定不是。风吹树叶子刮红了脸……俺没错没错……不一一指出来就没错……）
      ——为了避免洒家被累死，谁帮俺打个120吧
      ——大家继续聊，俺决定退避三舍。

数学之美系列二十一 － 布隆过滤器（Bloom Filter）
2007年7月3日 上午 09:35:00

发表者：Google（谷歌）研究员 吴军

在日常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在一个集合中。比如在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断它是否在已知的字典中）；在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来了。比如说，一个象 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件（email）提供商，总是需要过滤来自发送垃圾邮件的人（spamer）的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址，全世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。如果用哈希表，每存储一亿个 email 地址， 就需要 1.6GB 的内存（用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹 googlechinablog.com/2006/08/blog-post.html，然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有 50%，因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB， 即十六亿字节的内存）。因此存贮几十亿个邮件地址可能需要上百 GB 的内存。除非是超级计算机，一般服务器是无法存储的。

今天，我们介绍一种称作布隆过滤器的数学工具，它只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题。

布隆过滤器是由巴顿.布隆于一九七零年提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。我们通过上面的例子来说明起工作原理。

假定我们存储一亿个电子邮件地址，我们先建立一个十六亿二进制（比特），即两亿字节的向量，然后将这十六亿个二进制全部设置为零。对于每一个电子邮件地址 X，我们用八个不同的随机数产生器（F1,F2, ...,F8） 产生八个信息指纹（f1, f2, ..., f8）。再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2, ...,g8。现在我们把这八个位置的二进制全部设置为一。当我们对这一亿个 email 地址都进行这样的处理后。一个针对这些 email 地址的布隆过滤器就建成了。（见下图）



现在，让我们看看如何用布隆过滤器来检测一个可疑的电子邮件地址 Y 是否在黑名单中。我们用相同的八个随机数产生器（F1, F2, ..., F8）对这个地址产生八个信息指纹 s1,s2,...,s8，然后将这八个指纹对应到布隆过滤器的八个二进制位，分别是 t1,t2,...,t8。如果 Y 在黑名单中，显然，t1,t2,..,t8 对应的八个二进制一定是一。这样在遇到任何在黑名单中的电子邮件地址，我们都能准确地发现。

布隆过滤器决不会漏掉任何一个在黑名单中的可疑地址。但是，它有一条不足之处。也就是它有极小的可能将一个不在黑名单中的电子邮件地址判定为在黑名单中，因为有可能某个好的邮件地址正巧对应个八个都被设置成一的二进制位。好在这种可能性很小。我们把它称为误识概率。在上面的例子中，误识概率在万分之一以下。

布隆过滤器的好处在于快速，省空间。但是有一定的误识别率。常见的补救办法是在建立一个小的白名单，存储那些可能别误判的邮件地址。

lose

原帖由 emacsnw 于 2008-6-27 03:10 发表



谁说Google的big table是关系数据库了？

自己看文档吧，有些地方像有些不像。

   In many ways, Bigtable resembles a database: it shares
many implementation strategies with databases. Paral-
lel databases [14] and main-memory databases [13] have
achieved scalability and high performance, but Bigtable
provides a different interface than such systems. Bigtable
does not support a full relational data model; instead, it
provides clients with a simple data model that supports
dynamic control over data layout and format, and al-
lows clients to reason about the locality properties of the
data represented in the underlying storage. Data is in-
dexed using row and column names that can be arbitrary
strings. Bigtable also treats data as uninterpreted strings,
although clients often serialize various forms of struc-
tured and semi-structured data into these strings. Clients
can control the locality of their data through careful
choices in their schemas. Finally, Bigtable schema pa-
rameters let clients dynamically control whether to serve
data out of memory or from disk.

zszyj

原帖由 shan_ghost 于 2008-6-27 09:17 发表
http://googlechinablog.com/2007/07/bloom-filter.html

闹了半天，原来有人到现在都还不知道我们在说什么啊。

打一耳光，打一耳光。（楼上某位：哪里在响？打的不是我。一定不是。风吹树叶子刮红了脸…… ...

同志, 自打耳光吧!
这里说的是用于垃圾邮件黑名单, 黑名单可以几天更新一次, 确实是不需要动态刷新的, 这是可以使用布隆过滤器的前提. 可它与用户名是否已存在的识别问题是一码事吗?注册用户信息也要几天才更新一次? 几天内的注册允许你随便重复吗?
正如前面某位仁兄谈到, 用什么技术, 要先看需求, 你看明白LZ的问题了吗? LZ的需求与google这里介绍的需求是一致的吗?

[ 本帖最后由 zszyj 于 2008-6-27 09:38 编辑 ]

haiyan_qi

原帖由 zszyj 于 2008-6-26 23:14 发表

心理扭曲， 思维混乱．　多说无益，　将你的可装入10亿元素，　"能支持10000并发写同时10000并发读,且具备分布式事务支持功能"的broom filter算法，　show出来让大家瞧瞧吧．　别将自已的智商降到三岁小孩的水 ...

为什么bloom filter非要支持事务呢？这种名单侦测是允许错误率的，只要错误率控制在一定程度上就可以。你肯定也不理解cache的含义。

haiyan_qi

你一直没有跳出联机交易系统的思维定势，估计你不是做银行的就是做电信的。

zszyj

原帖由 haiyan_qi 于 2008-6-27 09:41 发表



为什么bloom filter非要支持事务呢？这种名单侦测是允许错误率的，只要错误率控制在一定程度上就可以。你肯定也不理解cache的含义。

"这种名单侦测是允许错误率", 没错, 可它说的是允许"假命中率", 即没有重复的ID,你说别人重复了, 而如果确实重复的, 必须100%被查出来, 这就是bloom filter的作用. 因此,它是不允许你出现"漏判"的情况吧.

分布式事务这个话题, 是别人提出来的一个解决数据一致性的方案, 不是我的要求. 我只是照抄他的理论.
但不可否认, 允许误判, 不允许漏判, 这是bloom filter的一个设计要求. 即使不用事务, 你还是要保证,只要在数据库登记了用户信息, bloom filter就必须含这个用户ID, 否则就有漏判的可能性, 即保证数据一致的问题. 你不用事务可以, 只要你拿出保证数据一致的方案就行.

至于cache的含义, 与LZ需求无关, 我是否理解更不重要. 如果你觉得自已很懂, 希望给大家深入介绍, 也未尝不可, 但建议另开贴子.

emacsnw

原帖由 zszyj 于 2008-6-26 16:27 发表

确实是关系型数据库. bigtable框架的开源实现是hbase, 我前面给出个链接. 是不是关系型数据库, 请大家考虑几点:
1. 通过二维表(table)表示所有的对象和联系的数据库概念视图的DBMS, 除了关系型,还有什么? 关 ...

BigTable的确不是关系数据库系统，它的所谓的表非常sparse，并且几乎不支持绝大部分关系代数的操作。不要看到表就认为是关系数据库。另外Google最近出的App Engine，数据就是基于BigTable的，官方关于这个datastore的介绍overview就写了它不是关系数据库：

The App Engine datastore is not a relational database.

http://code.google.com/appengine/docs/datastore/overview.html

zszyj

原帖由 haiyan_qi 于 2008-6-27 09:41 发表
你一直没有跳出联机交易系统的思维定势，估计你不是做银行的就是做电信的。

不管做哪个系统, 技术方案都需要严谨, 经得起推敲, 做哪个行业都不重要.
这个世界上, 并没有任何一套方案, 可以通用于任何不同的需求, 正如前面提到的, 其实每个疑问都是很客观的.
再者, 不管是银行还是电信的系统,都不会将精力放在"用户管理"这个小得不能再小的问题上, 对于这种单表操作, 根本不会涉及到什么事务的概念.事务的代价是高昂,只能用在复杂的业务处理上.
我再重复一次,轻言事务者,不是我, 是别人提出的解决方法.

当然, 如果你最后坚持, "用户ID识别"="黑名单识别", 不支持实时更新, 允许漏判, 允许一定时间内的ID重复, 而且你的客户最终可以接受你的这个需求实现方案. 哪我也只能说,你找到了一个适用于你的客户的可用方案. 但如果我是客户方, 恐怕你这个方案无法过关.