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

benjiam

原帖由 shan_ghost 于 2008-6-26 23:06 发表



一般来说，糊涂蛋总是希望天下没有人能比它懂得更多——我都不懂，你怎么可能懂？


另：俺有个同事用C++写了套基础类库出来，支持VB式RAD开发。
按阁下的逻辑，是不是可以说一切可以支持RAD开发的都 ...

big table 是关系数据库的 马甲,  那么我们是不是可以认为stl 的vector   list deque 也是个db,
那数据库也就是一个带高级接口的文件系统。
google 快是因为cgi .
google 的服务器数量级别不靠谱
mysql 比oracle 强。  看来taobao ebay 移动 联通的 dba 都是些水货 dba, 选型都这么失败。

将你的可装入10亿元素，　"能支持10000并发写同时10000并发读,且具备分布式事务支持功能"的broom filter算法
这种事情是单靠算法解决的吗？ 算法解决的什么？ 这要求 是靠一个系统来完成。还 10年的系分说出如此没有职业素养的可笑论题。

借用一下

您除了select，还说出过第二句有点技术含量的话么？

zszyj

原帖由 benjiam 于 2008-6-26 23:57 发表


big table 是关系数据库的 马甲,  那么我们是不是可以认为stl 的vector   list deque 也是个db,
那数据库也就是一个带高级接口的文件系统。
google 快是因为cgi .
google 的服务器数量级别不靠谱
mysq ...

又一只会呕气的小学生, 是不是数据库,你看我前面的链接去吧. 不是我说的, 是它自已说的, stl是不是数据库? 你找本数据库原理看看吧, 小学生的水平, 再告诉你多了你还是不懂事.
"google 快是因为cgi"? 你以为这偷换概念很高明? 用户检查返回快, 原因是索引查找快+CGI显示返回页面速度快, 这原意没看懂? 这与google快是一个概念吗?
mysql测试结果比oracle快, 是公开测试的结果, 你自已上网搜搜吧, 我没必要为mysql打广告. 选型不是只有速度的问题, 从商务上考虑的问题多得很,包括功能特性,稳定性,服务.这些事情说多了你也不懂.
"这种事情是单靠算法解决的吗", 你这话不该对我说, 应对某人说的, 你自已翻翻贴子看看再说吧. 我承认自已是做不出来, 只能依靠成熟技术解决. 不过, 某人说一个简单算法+多线程锁+分布式事务就能轻松解决, 强人哪? 我可以怀疑,但没资格质疑他人的能力,所以才让他show出来. 你也不用老叫,  叫得凶不代表你有底气.
省省吧, 找些有意义的话题再说.

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

zszyj

原帖由 benjiam 于 2008-6-26 23:57 发表


big table 是关系数据库的 马甲,  那么我们是不是可以认为stl 的vector   list deque 也是个db,
那数据库也就是一个带高级接口的文件系统。
google 快是因为cgi .
google 的服务器数量级别不靠谱
mysq ...

有空顺便看看公开测试的结果吧:
http://www.cgidir.com/news/news/060904MySQLAward.html
http://developer.e800.com.cn/art ... 157439419127_1.html
以后说话学学我, 多拿点数据出来. 别口讲无凭.
如果你希望别人认同你的观点: STL是数据库. 拜托找点证据，或者它自已的宣称也好．

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

bbpet

原帖由 zszyj 于 2008-6-27 00:34 发表

有空顺便看看公开测试的结果吧:
http://www.cgidir.com/news/news/060904MySQLAward.html
http://developer.e800.com.cn/art ... 157439419127_1.html
以后说话学学我, 多拿点数据出来. 别口讲无 ...

这个，不是吧，出乎意料的弱，是不是没弄好啊……

同样为开源数据库的PostgreSQL则位列13名，每分钟只能处理120份订单

yuhe27913

原帖由 flw 于 2008-6-22 13:08 发表
还有一点：
理论上来讲，在利用了 ajax 技术的网站上，
这种检测在用户输入时就已经可以开始了。
手指的速度比机器和网络的速度慢了若干个数量级呢。

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

heiyeluren

路过。。。大家继续。。。

emacsnw

原帖由 benjiam 于 2008-6-26 07:57 发表


big table 是关系数据库的 马甲,  那么我们是不是可以认为stl 的vector   list deque 也是个db,
那数据库也就是一个带高级接口的文件系统。
google 快是因为cgi .
google 的服务器数量级别不靠谱
mysq ...

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

wwwsq

原帖由 zszyj 于 2008-6-26 22:35 发表

我看啊, 还是由那位"高手"写出一个"能支持10000并发写同时10000并发读,且具备分布式事务支持功能"的broom filter,让大家开开眼界的. 我等是没有这种本事的.

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

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

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

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

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

zszyj

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

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

请坚持"布隆过滤器"论的, 还是好好研究一下它吧, 我前面提的几个问题:
1. 在10亿个元素的规模下, 你找到什么好的hash函数组, 能保证你说的99%的命中率? 拿出一组这样的函数来证实一下再说吧.
2. 众所周知, 布隆过滤器适合一次性装载然后只读方式访问的静态数据, 不合适频繁更新, 更绝对不能删除.典型的应用案例是网站的cache, 可以快速检测内容是否命中, 如高速的音乐点播等网站. 这样的算法, 适合不断刷新,甚至不断删除的用户ID管理吗? 说什么要几天重装一次, 说什么用户检测结果只要接近准确就行, 这有点强辞夺理吧? 想想看, 在数据库上,即使10亿行, 也能在0.1ms的速度上得到结果,而且绝对准确, 不需要人去维护它,每隔几天重装.如果是你, 会选哪个方案?另外, 你自已也提到, 还要配合数据库的黑白名单一起使用, 那么说最后还是至少要查一次数据库,既然如此, 还需要这个干嘛,我直接查一次数据库就解决问题了, 前面已经测试过, 0.1ms的级别, 数据规模从几百到数十亿, 查询时间基本一样.不得不承认,在精确查找方面,数据库的索引算法,的确已经很优秀.
3. 你说的不难, 那么请你想想, 如果你承认同时并发读写必须加锁的事实的话, 那么请你讲讲, 如何解决"并发10000读同时并发10000写"的加锁问题. 可以告诉你的是, 多线程锁绝对是行不通的,几百并发的规模还凑合. 数据库最复杂的处理技术之一,就是它的I和C两项, 并发访问控制和数据隔离度控制. 恐怕你的布隆过滤器需要加上这个并发访问控制的算法时,其算法复杂度已经不是你们口头上所说的"简单的算法了".
4. 前面提到的,数据一致性保证问题, 我已经告诉我你们分布式事务是高代价的. 请你讲讲,你又有什么好的方案?算了,这点要求太高,可以忽略. 但还是需要明白一点, 如果全数据库管理,是不需要面对这个难题的.
布隆过滤器应用在cache访问查找的场合,确实是不用考虑上述任何问题, 而且是绝大部分网站的通用技术, 但自已好好想想, 适合用于用户ID查找吗? 如果仍然坚持的话, 麻烦拿出一个实际算法源码, 哪怕是一个设计方案也行, 让大伙都瞧瞧可好?
直到目前为止, 虽然只能说数据库是实现用户ID管理和识别的一个可实现方案,不一定是最值方案, 但我一点看不出布隆过滤器是一个可实现方案,更不要说是最佳方案了.只要你拿出的技术设计说明解决了前面四点, 不, 只要前三点问题,大家才会承认它是一个可实现方案.
另外, 还是希望大家保持这种技术讨论的方式, 别老说反话,怪话. 听着觉得幼稚.

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

zszyj

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



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

确实是关系型数据库. bigtable框架的开源实现是hbase, 我前面给出个链接. 是不是关系型数据库, 请大家考虑几点:
1. 通过二维表(table)表示所有的对象和联系的数据库概念视图的DBMS, 除了关系型,还有什么? 关系型数据库的核心概念就是关系,什么叫关系, 就是table. 层次型和网络型, 有table这个概念吗?
2. 除了关系型数据库, 层次型和网络型哪个能支持SQL. SQL是建立在关系模型理论基础之上的.
另外, 即使是OODB, 也仅仅是RDB的扩展, 并没有上升到新数据库模式的层次,否则发明者必获图灵奖.目前为上, 除了三大数据库模式,尚未出现革命性的新数据库模式理论.
再说了,只要懂点数据库原理, 上上hbase网站, 认真研究一下其数据库的物理视图和概念视图,以及其操作命令, 就不难得出结论,它是不是关系型数据库. 自已多下功夫吧, 希望有人能得出新的研究结论.