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

wwwsq

原帖由 shan_ghost 于 2008-6-27 11:11 发表
呵呵，不好意思。

最近心情不好，见不得宵小闹腾。

本来只是看有人低级错误太多——数据库服务器和100MHZ 200M内存的对比实在强烈，让人实在忍俊不禁，于是就随手发出给大家共享了^_^

还怕某人面子上过 ...

boom filter是可以很方便的把新增用户也hash之后插进去，对于降低误判率有帮助。不过我猜对系统应该改进不大，因为在分布式系统里面还是有同步的问题，把错误率从百万分之一降低到十亿分之一不一定有意义，需要衡量一下成本和收益了。

wwwsq

原帖由 zszyj 于 2008-6-27 11:22 发表

你还是没有精确理解我前面提的问题.
"已注册用户ID"一部分在过滤器的"黑名单"中, 一部分是最近新增用户放数据库里, 时间成本是1次过滤器查找+1次数据库查找, 副作用时注册用户时增加1次新增用户表插入和定期 ...

界面上提示是否可用的时候，都不一定需要去检查黑名单（这取决于用户想不想让这个提示严格的100%正确）。

wwwsq

原帖由 zszyj 于 2008-6-27 11:31 发表

对, 这就是我前面提出的问题, 检测用户是否重复, 定义到底是"不与几天以前的用户重复",还是"不与目前系统内的所有用户重复"? 如果你是客户, 你会接受哪一个, 如果你是邮件用户, 服务器告诉我可用了,输入了一大 ...

首先，这个概率非常低。低到你可能一辈子都遇不到。

第二，谁告诉你用户需要重新输入？注册的时候发现用户名重复，就让客户改下用户名就是了。网页技术上有很多技巧可以让用户不用再次填内容。

第三，注册检查通不过有很多可能的原因，用户名重复只是其中的一种可能。这需要协调一致的处理方式。

第四，同时给客户两个方案，一个花费1w（在0.00001%的概率下，用户注册提交之后会被要求改一下用户名），一个花费100w，你认为客户会选哪个方案？

[ 本帖最后由 wwwsq 于 2008-6-27 12:48 编辑 ]

wwwsq

原帖由 zszyj 于 2008-6-27 12:54 发表

低不低, 看网站的规模了, 小网站上注册,可能一辈子都遇不到.但全球性的大网站呢? 概率多少, 恐怕谁都不好说.
是否只改名? 相信大家都遇到过好多这种经验, 除了大部分不用重输, 还是有不少要重输的, 用户名,密 ...

你恰恰说反了。小网站是不在乎这点性能和成本的，直接去查数据库就好了，反正用户少请求少，机器空着也是空着，查查数据库也无所谓。

布隆过滤器过滤几百亿的垃圾邮件地址都没问题，何况过滤区区几亿的合法注册用户。概率问题，你去看看前面贴的bloom filter文章就知道了。

这确实是一个选择问题，需要根据不同的情况来选用。而不能一概认为，只能用数据库来做。

wwwsq

原帖由 zszyj 于 2008-6-27 13:09 发表

你又在逃避一个问题了．布隆过滤器 的概率，指的是已经进过滤器的ＩＤ，只是错判的概率．　并不包含你前面说的几天内的新增用户，对于大型网站，如果每天新增几万，漏判的概率会低吗？
布隆过滤器过滤几百亿 ...

一个小时更新一次可不可以？一分钟更新一次可不可以？

真是无语言。

另外，谁告诉你要几十G内存？去看下Bloom filter的原理再来。你连什么叫bloom filter都还没搞清楚，讨论怎么继续下去？

[ 本帖最后由 wwwsq 于 2008-6-27 13:14 编辑 ]

wwwsq

原帖由 zszyj 于 2008-6-27 13:24 发表

"假定我们存储一亿个电子邮件地址，我们先建立一个十六亿二进制（比特），即两亿字节的向量，然后将这十六亿个二进制全部设置为零。对于每一个电子邮件地址 X，我们用八个不同的随机数产生器（F1,F2, ...,F8） ...

google那个黑板报是科普性质的东西。

wiki上的说明稍微详细一些：
http://en.wikipedia.org/wiki/Bloom_filter

wwwsq

原帖由 zszyj 于 2008-6-27 13:41 发表

你找哪个材料, 都是一个说明, 即使一个ID一位, 无论如何1亿用户就要大于125M, 几百亿仍然是几十G.可能大家都看不懂高深的中文也看不懂英文,你是很懂的, 说说看怎么几百亿邮件地址就不需要几十G内存了?

谁告诉你一个ID要一位？

麻烦你认真看下文档。