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

wskyygydx

呵，是啊，我有时候也纳闷，检测怎么那么快呢??

zszyj

原帖由 emacsnw 于 2008-6-27 09:58 发表


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

参考了一下你给的链接, 没看到它使用了bigtable框架, 而hbase确实就是一个完整的bigtable的开源实现, 而且虽然也表示未完整支持所有的关系型数据库功能,但基本上还是以此为基础的. 至于App Engine, 已经超出了bigtable/hbase的范围, 即使有关,也只是建立在bigtable基础上的更高层次的应用, 它提供了自已的访问接口, 因此它已经不是关系型数据库.但无论如何, App Engine是什么,这一身已经超出了bigtable/hbase是否关系型的范围了. 建立在bigtable/hbase的App Engine不是关系型, 不代表bigtable/hbase不是关系型. 正如关系型数据库也建立在文件系统基础上, 它不是文件系统, 但不能说文件系统就不再是文件系统了, 一样的道理.
当然,我觉得有点扯远了, 而且偏离了主题, bigtable本身是数据库无疑的, 这点争论下去也没有什么意义, 对吗?

shan_ghost

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

同志, 自打耳光吧!
这里说的是用于垃圾邮件黑名单, 确实是不需要动态刷新的. 它与用户名是否已存在的识别问题是一码事吗?
你看明白LZ的问题了吗?

见198楼我的帖子：

另： 我还真没发现有任何一个电子邮件系统允许用户改名或删除自己。

这是bloom filter真正发挥它的威力的一个重大前提。

另： 在下曾1年没上hotmail。账户还在，只是邮箱被清空了，空间被收回。重新激活（得到空间，当然邮件没了）且必须在1个月内再次登录才能回到正轨。
这个情况很少见，想必有类似经历的人不多。

另外，国内的免费邮箱，大多连邮箱清空都不做。几年不上，一切照旧——只有新浪还是网易邮箱的曾清过我的邮件，剩余流程同hotmail。

再看看218楼同学的帖子：

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

布隆过滤器并不是什么很难的技术，只是你愿不愿意去掌握和使用的问题。布隆过滤器也不是万能的。布隆过滤器常常是只读的使用，往往几个小时甚至几天才更新一次。布隆过滤器往往和黑白名单结合使用，而黑白名单常常是数据库。布隆过滤器擅长的是以极小的代价在瞬间给出一个基本的判断。

布隆过滤器可以瞬间作出100w次的判断，其中99.99%是确定性判断。剩下万分之一的不确定性判断，如果需要确定性结果，再交给其他模块（比如数据库）作确定性判断。

在判断新用户名是否可用这种情况下，不需要完全的同步，一个用户名被删除之后，完全可以过几天再允许别人再次注册。也就是说在判断用户名是否可用的时候，布隆过滤器可以几天更新一次，在这期间，布隆过滤器是不用修改更新的。
判断新用户名是否可用，也不需要完全确定性的判断，一个用户名我只要判断它是否“可能重复”就可以了。在极小概率下，即使新用户名实际上没被别人使用过，我也完全可以告诉用户说“此用户名已被使用”。


213楼阁下：
以后说话学学我, 多拿点数据出来. 别口讲无凭.
如果你希望别人认同你的观点: STL是数据库. 拜托找点证据，或者它自已的宣称也好．

219楼的阁下：
请坚持"布隆过滤器"论的, 还是好好研究一下它吧, 我前面提的几个问题:
1. 在10亿个元素的规模下, 你找到什么好的hash函数组, 能保证你说的99%的命中率? 拿出一组这样的函数来证实一下再说吧.



----------------------------------
好笑的是： 大家很早就已经告诉你Bloom filter了；我第五页的帖子甚至直接给出了关键词，用它搜索，第一篇就是google打您耳光的那篇文章。

不过，这种东西，显然阁下是没兴趣或者还没有能力去感兴趣的。

不感兴趣不要紧，好歹您也看看，弄明白我们说的究竟是什么啊。



见过脸皮厚的，但这么厚的着实罕见。
想必树叶子是别想刮红了。

加上之前指出阁下转的那个圈，仅在俺一人身上，您的车轱辘话已经发展出两大系列了。
莫非还非要把老衲累死，一一指出您的8大系列25个品牌46个品种的低价错误吗？

您不就会点数据库基础吗？就这就想当学霸了？我们不用数据库您就疼了？不管具体情况如何，每套算法每个设计都必须和顶级数据库较量一番？

何况俺早说了，好数据库贵。够用的东西造数十个的花费，连给它塞牙缝都不够
     ——恩，这时候您忘了曾经要求我们的ACID，去搬这方面完全不入流的数据库系统MySQL了……


老衲不得不告诉你： 多线程很简单，锁很简单并且也比数据库快了无数倍（无非是可能进入内核态，多耗费若干时钟周期而已；和磁盘所需的漫长的寻道时间没得比），不是您想象中的洪水猛兽。
在下N年前为铁老大写的东西（其中颇有一些涉及多线程、锁的东西），至今都没出过bug——包括预计工期2个月被我合理设计后1星期搞定的、有40多个功能点的、因为需求不够精确或规格变动而导致的所谓二期改造工程。

至于所谓事务，所谓原子……乃至所谓调度，会了，就是几行到十几行代码的问题
            ——老衲前面某个帖子关于分布式事务的介绍中有提过。

老衲我前不久还为某项目补窟窿，200多行代码实现了线程及其资源的自动管理功能（以及多线程环境下必不可少的所谓原子性保证等等实用噱头——说它是噱头，就是因为考虑清楚了，三两行代码即可解决；只是宣传起来，那几个词儿实在大气，漂亮）。
上午设计，下午完成；调了3天——至今已跑了近一年了，7×24小时。没发现任何问题。


会者不难，难者不会。
我们现在已经知道您不懂bloom filter、不懂cache、不懂针对实际的折中设计、不懂锁、不懂多线程、不懂并发、不懂A、C、I、D了，不需要您一再说明。
——当然，我知道您不会服气。但很不幸，您的表现恰恰证实了您不过是仅仅听说过数据库厂商的宣传而已。
——您是用户，不是程序员。

另：既然阁下不懂这些，能否站开一点，不要在不合适的场合推销您的数据库？
谢谢。
放心。讨论这些的人和您不同领域，不会和您有竞争的。

zszyj

原帖由 shan_ghost 于 2008-6-27 10:24 发表


见198楼我的帖子：

另： 我还真没发现有任何一个电子邮件系统允许用户改名或删除自己。

这是bloom filter真正发挥它的威力的一个重大前提。

另： 在下曾1年没上hotmail。账户还在，只是邮箱被清空 ...

写那么多字, 有什么用呢? 不就是歪曲别人原意, 歪曲用户需求,同时扭曲自已的心灵吗?
将用户需求从"是否重复"强行下降为"可能重复", 也许只有你能接受.
你的hotmail账户不删除,可我的确实已经不能登录了, 无可否认, hotmail刚推出那年,三个月不用自动删除的情况,不是虚构的吧? 即使不删除, 不断新增的情况呢? bloom filter允许你将1%的用户, 从不应该命中判断为命中, 这就是它允许的"假命中率". 但并没有允许, 本来应该命中的, 居然不被命中的情况吧? 你还是坚持"黑名单问题"="用户ID重复问题"吗? 你可以坚持你的观点, 但恐怕决定权在客户.
google开发的bloom filter实现里面, 它提供的8个信息指纹函数+8个hash函数号称达到了万分之一的"假命中率", 可是,这8组函数google能开发出来, 你能吗? 开源了吗? 你能确认它的实现就成本很低?
最后提醒一句, 技术人员要经得起别人的质疑和讨论, 别动不动就上升到暴力讨论的模式. 另外, 号称MYSQL的ACID不入流, 你远远还没有这种资格, 自已看看MYSQL4以后版本的特性再说吧. 贬低一个公认的优秀产品之前, 先掂量掂量自已的份量.
对你的评价,还是很客观的: 说起来天下无敌, 做起来有心无力.
你说的自已如何如何的厉害, 分布式事务, 多线程锁, 每个都几天搞定. 还是一句话,将你所谓轻易实现的这些代码,拿出手亮亮相吧.而且别忘了,你的这几天那几天"轻易"实现的东西, 别人可是不用一分钟搞定的.

最后, 我觉得阁下与你的讨论,没得到任何技术提升, 只看到负面情绪和攻击, 针对你的评论,不再回复.

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

wwwsq

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

不管做哪个系统, 技术方案都需要严谨, 经得起推敲, 做哪个行业都不重要.
这个世界上, 并没有任何一套方案, 可以通用于任何不同的需求, 正如前面提到的, 其实每个疑问都是很客观的.
再者, 不管是银行还是电信 ...

你没仔细分析需求。

在判断用户名是否可用的时候，我们不需要完全确定的结果。我们只要知道“肯定不会重复”与“99%可能会重复”就可以了。当99%可能会重复的时候，我们就告诉用户，换个用户名再注册。

shan_ghost

原帖由 wwwsq 于 2008-6-27 10:53 发表



你没仔细分析需求。

在判断用户名是否可用的时候，我们不需要完全确定的结果。我们只要知道“肯定不会重复”与“99%可能会重复”就可以了。当99%可能会重复的时候，我们就告诉用户，换个用户名再注册。

不是99%，而是99.99%。我引的Google的耳光文章有说明。

wwwsq

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

写那么多字, 有什么用呢? 不就是歪曲别人原意, 歪曲用户需求,同时扭曲自已的心灵吗?
将用户需求从"是否重复"强行下降为"可能重复", 也许只有你能接受.
你的hotmail账户不删除,可我的确实已经不能登录了, 无 ...

比如用户想注册“mynewname”，然后用过滤器检查发现没有重复，那就确定的告诉用户“这个用户名可用，肯定不会重复。”

比如用户想注册“mynewnameabc”，然后用过滤器检查发现可能重复，那就告诉用户，“这个用户名已经被人用了，请换一个用户名”。实际上，在极小的概率下，“mynewnameabc”可能还没被使用，只是有个“sdfadfsadfsadf”恰好和“mynewnameabc”的哈希值相同，没关系，在这种极小概率下，我们就让用户换个名字再注册。

zszyj

原帖由 wwwsq 于 2008-6-27 10:53 发表



你没仔细分析需求。

在判断用户名是否可用的时候，我们不需要完全确定的结果。我们只要知道“肯定不会重复”与“99%可能会重复”就可以了。当99%可能会重复的时候，我们就告诉用户，换个用户名再注册。

你还没看明白我说的话, 只要你不实时刷新, “肯定不会重复”是肯定实现不了的.,这就是我指出的问题,为什么"黑名单问题"<>"用户ID重复"问题.  是我没分析需求, 还是某人在故意弱化需求呢?

zszyj

原帖由 wwwsq 于 2008-6-27 10:57 发表




比如用户想注册“mynewname”，然后用过滤器检查发现没有重复，那就确定的告诉用户“这个用户名可用，肯定不会重复。”

比如用户想注册“mynewnameabc”，然后用过滤器检查发现可能重复，那就告诉用 ...

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

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

wwwsq

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

你还没看明白我说的话, 只要你不实时刷新, “肯定不会重复”是肯定实现不了的.,这就是我指出的问题,为什么"黑名单问题""用户ID重复"问题.  是我没分析需求, 还是某人在故意弱化需求呢?

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