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

wwwsq

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

你还是没想清楚吧, 只要不断有新用户注册, 就要不断刷新过滤器,否则无法保证"用户肯定不重复"这个要求. 这明显是不适用于bloom filter的.如果象某人所说,几天才更新一次过滤器, 你认为"用户肯定不重复"在没更 ...

“肯定不重复”是基于几天前的数据做出的判断。要精确的实时判断，就再从最近几天新注册的用户名里面再查找一次就可以了。

实际上这种冲突的概率实在太小了，也许等到了真正创建用户的时候再检查都不迟。界面上提示是否可用的时候，都不一定需要去检查黑名单（这取决于用户想不想让这个提示严格的100%正确）。

zszyj

原帖由 wwwsq 于 2008-6-27 11:02 发表




如果要精确判断，就要有黑名单。黑名单里面只要放最近几天新注册的用户名就可以了。这比同步处理几亿个用户名容易多了，成本也低得多。

其实我觉得你也没细看, 别人的用法刚好相反, 是将黑名单放过滤器, 只要是垃圾邮箱,肯定被查出来. 不幸被误判的, 才会再找一次白名单(通常是放数据库里). 因此别人查库的可能性,只有0.01%的可能性,代价是很低的, 而且绝对不公漏判.
你如果采用你的做法, 由于过滤器不及时更新, 会存在漏判的可能性, 那么100%还要查询一次几天内的新增用户信息(也是数据库). 这带来两个问题:
1.每个新增用户, 即要登记基本信息表,也要登记新增用户信息表,存储和工作量的代价都高了一倍吧.
2.由于每次100%需要查找新增用户信息, 那么其实每次还是要访问一次数据库. 前面已经提过, 对于数据库按索引查询, 从10000到10亿,查询的时间基本是一致的. 那么, 与直接在用户信息表查找相比, 这种过滤器+新增用户表查询的优势在哪?

shan_ghost

呵呵，不好意思。

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

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

还怕某人面子上过不去，赶紧续上两贴试图引开话题……



不过，有人显然是经不起批评的。别人指出他的错误，就成了 “强奸民意”“不知道说你无知, 还是说你野蛮”“带着争强好胜的心态来参与”（176楼）“歪曲别人原意, 歪曲用户需求,同时扭曲自已的心灵” 了。

这顶帽子太大，在下实在担当不起，只好尽力挣扎，为自己脱罪了～～


实在不好意思……俺越为自己辩白，阁下就越发难堪，于是越发暴跳如雷，继而发现别人“心理扭曲”了……

不过，据说如果透过扭曲的心灵看人，所有人都是扭曲的……不知道这句话是真是假……



另，讨好某人一下：
   bloom filter只是不允许删除，并不是不能插入新信息。
         
——倘若是个明白人，他肯定应该感谢在下帮他绕开了一个错误。不过现在，俺只但愿这句话不会刺激到他。

wwwsq

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

其实我觉得你也没细看, 别人的用法刚好相反, 是将黑名单放过滤器, 只要是垃圾邮箱,肯定被查出来. 不幸被误判的, 才会再找一次白名单(通常是放数据库里). 因此别人查库的可能性,只有0.01%的可能性,代价是很低的 ...

在注册新用户的时候，当然“已注册用户”就是“黑名单”了。因为“已注册用户”此时是不可用，需要被“新用户注册流程”所禁止的。

你能不能灵活一点，别人把垃圾邮箱当黑名单，你就一定也要用垃圾邮箱当黑名单？

同步和维护一张只有一万条记录的表，和同步维护一个有几亿条记录的数据集，成本是不一样的。

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

wwwsq

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

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

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

还怕某人面子上过 ...

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

zszyj

原帖由 wwwsq 于 2008-6-27 11:14 发表




在注册新用户的时候，当然“已注册用户”就是“黑名单”了。因为“已注册用户”此时是不可用，需要被“新用户注册流程”所禁止的。

你能不能灵活一点，别人把垃圾邮箱当黑名单，你就一定也要用垃圾邮 ...

你还是没有精确理解我前面提的问题.
"已注册用户ID"一部分在过滤器的"黑名单"中, 一部分是最近新增用户放数据库里, 时间成本是1次过滤器查找+1次数据库查找, 副作用时注册用户时增加1次新增用户表插入和定期的新增用户表清理. 这种方案, 与直接查找基本用户信息,时间成本是1次数据库,不添加任何副作用的方案相比,它的优势在哪?
别忘了一个前提,在数据库上,不同数量级的索引查找,时间基本是一致的.

shan_ghost

tips： 禁用CPU的一二级cache，您的系统性能就可以得到提升

zszyj

原帖由 wwwsq 于 2008-6-27 11:20 发表



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

别忘了,不实时刷新过滤器, 并发读的话, 是不用加锁的. 要实时刷新过滤器, 大量的并发读写, 是要加锁的, 如果真达到10000读+10000写, 加锁控制的代价, 并不是你们想的这么简单.
再者, 确实会存在你说的, 数据同步的一致性问题, 这就是将简单问题复杂化了.

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

wwwsq

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

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

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

shan_ghost

tips： 磁盘寻道不需要时间。
tips： 数据库支持ACID不需要使用任何锁。