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

wwwsq

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

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

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

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

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

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

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

zszyj

原帖由 wwwsq 于 2008-6-27 12:44 发表



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

第二，谁告诉你用户需要重新输入？注册的时候发现用户名重复，就让客户改下用户名就是了。

第三，注册检查通不过有很多可能的原因，用户名重复只 ...

低不低, 看网站的规模了, 小网站上注册,可能一辈子都遇不到.但全球性的大网站呢? 概率多少, 恐怕谁都不好说.至于你说的0.00001%，更是没有理论是实践的根据了．
是否只改名? 相信大家都遇到过好多这种经验, 除了大部分不用重输, 还是有不少要重输的, 用户名,密码(两次), 如果内容多了,要分几页, 恐怕整个过程都得重来一次.
至于1w vs 100w，这个更不靠谱．即使google真象你们以为的好样，将这种技术也应用到ＩＤ重复检查去了，但其成本可能是1w吗？　直接数据库查找就100w？先不说用户信息最后都是保存在库里的，　这个成本没有差异．　即使只算数据库成本，难道mysql要收钱吗？　即便是oracle,　在普通ＰＣ服务器上，能卖这么贵吗？
最后, 讨论到了这个地步, 已经不是技术问题, 而已经是客户对应用系统的"系统观"问题了. 取决于客户对系统的看法和要求, 我相信, 不管是哪个行业, 高要求的客户仍然是主流的, 不仅是银行或者电信行业.
对于技术问题, 我也不想再讨论下去了, 细节都已经很清楚，剩下只是自已选择的问题. 只等着真有人拿出堪称＂高手级＂的代码，让我开开眼界吧．

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

wwwsq

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

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

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

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

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

shan_ghost

对某些人的偏执和无知叹为观止


apache可以支持多少并发？

或者，基于apache的、可以支持5000并发连接的系统有多少？


多少有点常识的，应该不会不知道apache用的还是进程而不是线程吧？
（我记得是5个进程构成的进程池吧？）

那么，到底有多少人那么没文化，以为apache是为每个用户开了一个进程/线程呢？

您试试开5000个什么都不做的线程试试，看有几个版本的linux可以撑住不死。
照您这么说，整个互联网都是虚妄，从未存在过了？


没接触过这方面的东西很正常。

但一窍不通还敢大放厥词，阁下可真欠打。


另： 阁下的数据正证明了“锁”这个操作的消耗之小

并发200用户:
$time tt 200

real    0m3.551s
user    0m3.400s
sys     0m0.130s
$time tt1 200

real    0m6.034s
user    0m5.900s
sys     0m0.120s

根据你的代码，200 × 100000 = 2千万次加解锁操作，仅仅耗用了 6.034 - 3.551 = 2.483秒
有兴趣的可以算算一次加锁需要多少时间消耗。

拜托长点常识好不好，别总干这种打自己脸的事。


还有，您不觉得Linus Torvalds是在指着鼻子骂您吗？
就因为您这样“不够标准的程序员在使用而使情况更糟，以至于极容易产生彻头彻尾的垃圾（total and utter crap）”，甚至逼得Linus Torvalds先生抓狂，以至于：“任何喜欢用C++而不是C开发项目的程序员可能都是我希望踢出去的人，免得他们来搞乱我参与的项目”。

zszyj

原帖由 wwwsq 于 2008-6-27 12:58 发表



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

布隆过滤器过滤几百亿的垃圾邮件地址都没问题，何况过滤区区几亿的 ...

你又在逃避一个问题了．布隆过滤器 的概率，指的是已经进过滤器的ＩＤ，只是错判的概率．　并不包含你前面说的几天内的新增用户，对于大型网站，如果每天新增几万，漏判的概率会低吗？
布隆过滤器过滤几百亿的垃圾邮件？　消耗几十Ｇ的内存做这个小事情？　服务器的内存几十Ｇ，会比数据库硬盘的成本低？而且这么强大的服务器，成本是多少？一个服务器光做这个事情，　其它都不做了？　如果还做其它事，这台服务器又是什么规模，价格多高？
准确率，成本，效益．希望会有人选择你的方案吧．

wwwsq

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

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

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

真是无语言。

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

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

shan_ghost

tips： 作为一个特殊的hash实现，bloom filter的更新和查询一样，都是O（1）效率。

甭说1秒更新一次，实时都没问题。
当然，实时有很多定义。但和毫秒级需要访问磁盘的数据库相比，微秒级的bloom filter就是实时。

zszyj

我看某些人啊，　当＂打手＂合适，＂高手＂是没份了，骂不倒别人，总能动手打倒吧？
进程也好，线程也好，自已做出来瞧瞧吧．
apache５０００并发？　那得看什么机器上了.普通服务器，几百就不错了．
apache的并发接受请求, 与你说的并发访问同一块内存的加锁控制问题, 是一码事吗?
就算apache做到了，又与你何干，它是个简单算法吗？　是你做出来的吗？　扯这么远，还是没拿得出手的，哪怕一行代码，可笑哪！　丢人哪！

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

zszyj

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



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

真是无语言。

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

"假定我们存储一亿个电子邮件地址，我们先建立一个十六亿二进制（比特），即两亿字节的向量，然后将这十六亿个二进制全部设置为零。对于每一个电子邮件地址 X，我们用八个不同的随机数产生器（F1,F2, ...,F8） 产生八个信息指纹（f1, f2, ..., f8）。再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2, ...,g8。现在我们把这八个位置的二进制全部设置为一。当我们对这一亿个 email 地址都进行这样的处理后。一个针对这些 email 地址的布隆过滤器就建成了。"
这是引用原文的话，　１亿个邮件地址，需要两亿字节=200MB, 你说的几百亿邮件地址，　不是几十Ｇ的内存是什么？　你很懂啊，给我说说看？

另外，不反对你们实时刷新，　就是拿点实时刷新的代码来看看吧．

shan_ghost

呵呵，这就又受刺激了？


apache是5000并发开5000进程吗？
您见过哪个白痴做的东西，会为5000并发开5000个线程？

在下不才，半年前正巧做了个仿QQ的原型系统，支持AIO，10个线程组成服务线程池，测试通过了数千并发（代码没做限制，linux能支持多少socket连接字，俺就支持多少并发）。

并发这玩意儿，不动手做不会明白。
逻辑复杂如wow，500并发基本就是不可解决问题；可要是一个用户登陆就给它发个“hello”然后什么都不做的玩意儿，百万并发（只要linux支持那么多连接字）也是小case，甚至都用不着多线程。


阁下连这方面的常识都没有，就会拿车轱辘话瞎搅，能骗得了多久？