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

可恶的

要是有现有的东西可以用，就直接用现成的。
当现成的产品不符合和不满足自己需求时，就有必要自己修改了。
google有那个实力，所以google选择了开源产品。
反正还是开源最好，免去了重复造轮子的过程。
就好比zszyj说的一样，不开源的话，需要重新花大量人力物力和时间来构建新产品，而开源则可以在现有的上面修改。
关注，明天继续来看各位前辈的探讨。

zszyj

原帖由 carny 于 2008-6-26 17:21 发表




那只是用id 算出hash value, 跟據hash value , 去算出在那一台node上,的那筆record, 談不上transaction
請問你一旦某一筆 id field 會時常rename , delete , update ??

人家的问题提的没错, 你还是没解决别人的问题. 如果是用hash表解决:
1. 10000个请求同时读hash表,  即并发读问题(C); 所有机器请求都转发到一个服务器上去访问这个hash表, 有这么强的机器吗?
2. 与此同时, 还要有1000个请求并发插入新用户, 这涉及数据隔离(I)和并发读写问题(C); 普通的hash表能很好支持?
3. 每个hash表成功插入新用户的同时, 要保证在其它节点上的用户信息保存结果的一致性, 这是你说的不存在transaction的问题,其实还是存在的, 即原子性问题(A);如果hash插入成功,其它节点上的用户信息没成功,或者反之, 怎么办? rollback hash表? 有这功能吗?
4. 最后, hash表中的用户信息是易失信息, 最终仍然靠保存到硬盘,即数据持久性问题(D).

你看一下, 即使不考虑update, delete, 光select*10000+insert*1000,数据库需要解决的ACID的问题,在你这个hash上也一个不少,足够花上几个月时间解决这个问题.
另外,别忘了这可是一个包含上亿元素的hash表.
如果确实象你说的这么轻松一个hash表就解决所有问题的话, 那我们可是长见识了, 不妨将你的hash表贴出来让大家开开眼界. 顺便让哪位高手放到一个服务器上,让大家测试一把如何?

haiyan_qi

原帖由 zszyj 于 2008-6-26 17:47 发表

人家的问题提的没错, 你还是没解决别人的问题. 如果是用hash表解决:
1. 10000个请求同时读hash表,  即并发读问题(C); 所有机器请求都转发到一个服务器上去访问这个hash表, 有这么强的机器吗?
2. 与此同时,  ...

shan_ghost已经说过了这种名单侦测用的是bloom filter，不是一般的hash，你先了解一下bloom filter算法，这种算法理论上肯定是要比数据库所采用的数据结构要快的。既你所说的b-tree（数据库的索引并不都是b-tree结构的）。

zszyj

原帖由 haiyan_qi 于 2008-6-26 18:01 发表



shan_ghost已经说过了这种名单侦测用的是bloom filter，不是一般的hash，你先了解一下bloom filter算法，这种算法理论上肯定是要比数据库所采用的数据结构要快的。既你所说的b-tree（数据库的索引并不都是 ...

没人不承认它比数据库快. 但快只是一个方面, 前面提到的几个问题, 如何解决? 即使速度从0.1ms提高到0.001ms, 其它的并发读写控制, 数据一致性, 内存数据丢失后的恢复等,都不考虑了?

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

shan_ghost

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

发现有些人的观点无异是强奸民意, 希望他们先弄清楚几个概念:
1. 我从开始至今, 一直强调的是, 象用户名匹配之类按索引查找的简单应用, 属于管理类信息, 适合用数据库. 可有些人偏偏视而不见, 非要将"网页", ...

据说，unix派认为：凡是涉及输入和/或输出的，都可视为文件。
他们成功了。

许多年后，又有面向对象一派认为：凡可于其上执行任何操作的，都是对象。
他们似乎也成功了。

现在，又有人站出来说：凡涉及信息检索查找的，都是数据库——至少也是基于数据库的——不管它是叫big table还是LDAP。
http://wiki.chinaunix.net/index.php/LDAP

莫非我遇上了“泛数据库”达人？


想想其实也算有道理。
比如我就用hash做过内存数据库，还煞有介事地给它实现了select/insert/delete等功能，甚至还支持多进程/线程——当然，不支持多表联合查询。

所以说hash是个数据库，也不算不着边际。


恩，这么说，泛数据库派有没可能成功呢？




不过呢，有一点俺很疑惑：在下只是介绍了一个最为轻量级的bloom filter数据库，阁下恼火什么呢？

当然，这个bloom filter数据库现在还不支持SQL格式的select/insert/delete；为了降低消耗，它甚至都不保存实际字符串，而仅仅在数据库中存储了一个二进制位。

不过，既然阁下都泛数据库了，而且big table和hbase又是典型的数据库，为何说起gmail用数据库如何实现的话题，有人又蹦了？


另外嘛：算法也有数据库,而且有很高深的数据库. 说得对, 这也正是我的观点, 不知道我哪里说的话, 表示算法就不用数据库了? 恰恰是某些人认为使用算法就是轻视数据库,只有别人实现的才叫数据库, 这不是冤枉别人吧?

yangkwch

现在运营商上的七号信令监控系统应该可以达到每天上亿条记录吧。一次呼叫要出5-6条信令。只要有2000万次左右的呼叫就能达到这个数量级了。

shan_ghost

另外再说几个问题：

1、楼主的帖子说的是google的什么？俺不识字，谁能帮俺读一读？

2、100MHZ CPU+200M内存的机器上，MySQL能给我们什么样的惊喜呢？有没人测测看？
甭老拿N多个核的服务器+磁盘阵列上跑出的数据出来吓人……俺老板穷，已经被吓翻N次了。

3、有没有人需要一个单独的“用户名重复检验系统”？——当然，这需求有点搞笑……
如果有人要的话，给俺硬件，俺帮你做茶炉子。不信咱中国制造竞争不过那些服务器+MySQL。

4、有这么一篇文章，相信很多人都应该看过：《为何不用MySQL》
http://www.host01.com/article/da ... 065422294252011.htm

当MySQL成熟时，OpenACS团队很高兴对其进行距离更近的考察。但是，MySQL团队似乎并不理解真正的ACID能力的概念和重要性：MySQL Todo在一个很长的列表中提到了事务，其中包括了诸如睡眠进程占用CPU吗这样的问题。此外，MySQL手册声称MySQL将很快通过表锁的使用来实现原子操作，但却没有回滚。这是对术语原子的明目张胆的误用：原子操作意味着或者所有操作都完成，或者没有操作完成。如果没有回滚能力的话，在一组语句的中间发生的硬件或电力故障将破坏块的原子性。

回滚不只是一种便利的特性，它是可靠的数据存储的关键性基础。

有许多很好的理由使用MySQL，但对可靠的、顺从ACID的数据存储的需求却并非是其中之一。


---------------------------------
这东西是2005年的。我不清楚现在怎样。

但有一点是肯定的：MySQL并不真正关心ACID，它对ACID的支持不可能很快到位。
看来，某人或者必须去买oracle了——或者，来买我便宜的茶炉子和全套方案吧。



5、听说过分布式事务吗？

所谓分布式事务，是类似这样的一种问题：一组oracle+sql server+原始文件系统的混合系统，如何保证一个提交中所有的操作都成功呢？

一般来说，处理逻辑是：更新每个数据库；有错则roll back，事务失败；否则继续更新原始文件系统，如果出错，自己要写代码恢复原始文件系统的原貌（这一般要封装起来）并向数据库提交roll back指令；否则整个分布式事务成功。

除非你把整个gmail全部用数据库（集群）实现，否则这分布式事务如何实现，还是必须由你自己来写。

COM声称自己可以“大幅度降低编写分布式事务的技术难度”；但或许您就不得不卖掉oracle，改买windows server+ms sql server了。


由于bloom filter本身的简单性，只要实现一个简单的读/写锁，就可以保证每次操作都成功且不存在脏读脏写——何况，我的茶炉子里还放了10个模块跑热备份呢。

如果要实现分布式事务也很简单：先别通知bloom filter更新数据；如果其他模块都返回OK，那么commit它们，然后再通知bloom filter更新数据——这就是毫不含糊的分布式事务。

甚至于，基于这个模块的定位和它夸张的微秒级响应速度，用户接入服务器只需要到它建立一个链接即可，因此不必考虑任何关于锁的问题；只要网络不丢包，它就绝对可靠——不会有人以为一个系统的每个服务器都要支持并发吧？（难道还要我从时间片划分说起不成？）

shan_ghost

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

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


ps: 在下认识一位高人。他有句话很有意思：“有两种人让我不爽。一种是他的论点我不同意，但整篇文章全无破绽的；另一种是一篇文章到处都是错误的。后者让人不爽的原因是：当你指出他的某个关键缺陷时，他会跟你胡搅蛮缠，搅出更多的低级错误；你甚至都没有精力去跟上他犯错误的频率，而他却还以为那些错误已经骗过了你的眼睛。当你觉得太累，不想理他时，他会宣扬自己已经驳倒了你。”

这确是至理之言。
因此凡发现有人在辩论中不断转换立场，甚至偷偷摸摸地向我的论点投降、以至于让在下愕然发现不知什么时候那个滑头小子就已经在拿我自己的观点和我自己死磕时，在下会点明后立刻闭嘴。
另，凡下笔千言，离题万里；你越是驳，他越是跑题且错误亦渐多者，请恕在下无礼。

楼主的发言很明确，没有任何含糊之处。任何说的不是gmail的，请自省。

[ 本帖最后由 shan_ghost 于 2008-6-26 20:04 编辑 ]

zszyj

原帖由 shan_ghost 于 2008-6-26 19:17 发表
另： 我还真没发现有任何一个电子邮件系统允许用户改名或删除自己。

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


ps: 在下认识一位高人。他有句话很有意思：“有两种人让我不爽。一种是他的论点 ...

阁下如此混淆视听, 有意义吗? 对提高你自的水平有帮助吗?
1.  bigtable/hbase是否数据库, 需要争辨吗? 我说来不算, 它自已的网站说的具权威性吧, 自自看看去吧. http://hadoop.apache.org/hbase.吵架无益.

2. 老说Bloom Filter算法,你真懂这算法吗?
你不知道这个算法, 不允许删除元素? 世界上没有服务器删除用户ID? 你可能不知道但不代表全世界人不知道 hotmail 用户三个月没使用自动删除的事实吧?
你觉得在10亿个元素的情况下,Bloom Filter的"假命中率"能保持在1%以下? 它能在10000个并发插入的同时10000个并发查询时用线程锁能保持高的效率? 你真有过多线程并发读写锁控制经验吗, 你知道这么大量的锁竞争下的后果吗? 大言不惭啊.
3. 分布式事务, 也亏你懂一点点数据库理论, 可你知道即使是专家级的数据库高手,在真正大规模应用前敢使用它的吗? 造成锁冲突甚至死锁的机会有多大? 额外付出的机器资源消耗有多大? 为加你一个Bloom Filter表, 甚至要付出单纯一句数据库查询N倍的代价?
4. google的设备是"100MHZ CPU+200M内存的机器"吗?  "任何说的不是gmail的，请自省", 你自省了吗? 你这说的是google的设备?
5. MYSQL可能支持ACID不是很完美, 但无可否认, ACID是任何一个数据库所必须具备的特征吧? 实现得再不济,也要远比你那个放在内存的hash表好吧? 再者, hash表居然也被你说成数据库, 这就是你的真实水平?
6. 你的所谓什么"专业用户ID检测机", 我看, 省了吧,不要说6万, 6块钱也许有人考虑. 不过是我, 宁愿选择免费的mysql.
7. 不知道你认识的高人是谁, 但你没发现, 别人指的可就是你啊? "他会跟你胡搅蛮缠，搅出更多的低级错误", "你越是驳，他越是跑题且错误亦渐多者", 你看看这不正是你的写照吗?
你自已看看, 你说了这么多, 除了说怪话,反话, 有哪句话显示出半点技术含量? 有哪句话是有半点技术讨论的价值? 心胸问题,人品问题.
对你的言论, 根本不屑再理!

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

虎皮尖椒

受益匪浅。

个人的一点小看法:gmail的细节不太清楚，google本身不太可能采用db的做法。换句话说，google那个mysql集群中mysql的用法可能和大家平时做大规模应用的时候对db的使用方法完全不同。他们应该是采用的一种称为全文库的做法，和db的实现细节有出入。

ps:前面很多人提到了海量数据,不知道大家都从事什么行业,能够接触到这样规模的应用,除了搜索,都还有哪些行业?