悠悠博客 (讨论区存档) — 技术永无止尽，未来事在人为

这种比较本来就很快的吧。

[quote]原帖由 [i]emacsnw[/i] 于 2008-6-22 10:37 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8636043&ptid=1166775][img]http://bbs.chinaunix.net/images/common/back.gif[/img][/url]
这种比较本来就很快的吧。 [/quote]

那为什么别的网站做不到呢？
再说有将近上亿（保守估计）的用户名，你得去匹配吧！字符的比较有那么快吗？
那你说说如果让你来做，你会怎么去做？

[quote]原帖由 [i]zhangzhh05[/i] 于 2008-6-21 18:46 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8636083&ptid=1166775][img]http://bbs.chinaunix.net/images/common/back.gif[/img][/url]


那为什么别的网站做不到呢？
再说有将近上亿（保守估计）的用户名，你得去匹配吧！字符的比较有那么快吗？
那你说说如果让你来做，你会怎么去做？ [/quote]

查找树啊。

[quote]原帖由 [i]zhangzhh05[/i] 于 2008-6-22 10:46 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8636083&ptid=1166775][img]http://bbs.chinaunix.net/images/common/back.gif[/img][/url]


那为什么别的网站做不到呢？
再说有将近上亿（保守估计）的用户名，你得去匹配吧！字符的比较有那么快吗？
那你说说如果让你来做，你会怎么去做？ [/quote]
:)
没那么神秘!
每一个节点(机器)上当然要采用合适的算法. 然后.
每个节点上都存有部分数据,当查询ask到来时,多个节点一起匹配这个用户名, 速度自然快了.

如果做了索引，这个数据量放在数据库中去查也很快的。

有没有让你一个一个的strcmp

[quote]原帖由 [i]cugb_cat[/i] 于 2008-6-22 11:54 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8636309&ptid=1166775][img]http://bbs.chinaunix.net/images/common/back.gif[/img][/url]
如果做了索引，这个数据量放在数据库中去查也很快的。 [/quote]

:) 赞同,方法的确很多.

在一定的数据量的前提下,一个用户的速度好处理(数据库和内存都有解决办法),当数据量过大或很大并发ask来时, 就要多节点一起匹配才能保证服务的实时性了.
这也就是google等采用多节点的原因了(实际上数据何止上亿)!

还有一点：
理论上来讲，在利用了 ajax 技术的网站上，
这种检测在用户输入时就已经可以开始了。
手指的速度比机器和网络的速度慢了若干个数量级呢。

[quote]原帖由 [i]flw[/i] 于 2008-6-22 13:08 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8636503&ptid=1166775][img]http://bbs.chinaunix.net/images/common/back.gif[/img][/url]
还有一点：
理论上来讲，在利用了 ajax 技术的网站上，
这种检测在用户输入时就已经可以开始了。
手指的速度比机器和网络的速度慢了若干个数量级呢。 [/quote]

:) 这也是一个有效的补充.

谢谢各位

google 的技术是挺牛的.

:em03: 喜欢Google.

有人做过上亿用户吗？ 有上1kw个用户吗？

分开节点，会有很多问题。 各个节点的及时更新，和状态处理是很麻烦的。

google 的确是nb 的。

qq 原来有道面提 就是考如何快速从1亿个客户里面搜索出相要的数据。

从qq 里面查询的状态来看， 好像不是很好。 他们应该没完全解决这个问题。

[quote]原帖由 [i]zhangzhh05[/i] 于 2008-6-22 09:24 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8635794&ptid=1166775][img]http://bbs.chinaunix.net/images/common/back.gif[/img][/url]
前几天在注册Gmail邮箱时，在我输入用户名，检测是否被占用时，我没有感觉到一点点延迟，结果就出来了。
Google在全球有上亿的Gmail用户吧，这个检测速度也太快了，而且还没算上网络的延迟。比其它的门户网站都 ... [/quote]
不要说1亿,即使是10亿行记录, 在数据库里按索引查找的话, 所花时间也不会超过1ms, 检测用户名明显就是按索引查找的, 因此也不会想得太神秘.
至于google网页显示速度快,那是因为它的WEB页面都是用CGI来生成的, 无论如何按生成网页的速度快, C肯定会远快于JAVA和.net
其实googlec真正的功夫，是体现在搜索上，那才真正是几千个节点上的海量数据并行搜索，比查找用户名之类的简单操作难度提高了不止上万倍．

[quote]原帖由 [i]zszyj[/i] 于 2008-6-23 11:50 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8641144&ptid=1166775][img]http://bbs.chinaunix.net/images/common/back.gif[/img][/url]

不要说1亿,即使是10亿行记录, 在数据库里按索引查找的话, 所花时间也不会超过1ms, 检测用户名明显就是按索引查找的, 因此也不会想得太神秘.[/quote]
知其然不知其所以然。
[quote]至于google网页显示速度快,那是因为它的WEB页面都是用CGI来生成的 ... [/quote]
是CGI就快吗？

下面这个是李开复写的"算法的力量"中的一部分, 讲了关于google的一些东西.
[QUOTE]
网络时代的算法
     有人也许会说：“今天计算机这么快，算法还重要吗?”其实永远不会有太快的计算机，因为我们总会想出新的应用。虽然在摩尔定律的作用下，计算机的计算能力每年都在飞快增长，价格也在不断下降。可我们不要忘记，需要处理的信息量更是呈指数级的增长。现在每人每天都会创造出大量数据（照片，视频，语音，文本等等）。日益先进的记录和存储手段使我们每个人的信息量都在爆炸式的增长。互联网的信息流量和日志容量也在飞快增长。在科学研究方面，随着研究手段的进步，数据量更是达到了前所未有的程度。无论是三维图形、海量数据处理、机器学习、语音识别，都需要极大的计算量。在网络时代，越来越多的挑战需要靠卓越的算法来解决。

     再举另一个网络时代的例子。在互联网和手机搜索上，如果要找附近的咖啡店，那么搜索引擎该怎么处理这个请求呢?

     最简单的办法就是把整个城市的咖啡馆都找出来,然后计算出它们的所在位置与你之间的距离,再进行排序,然后返回最近的结果。但该如何计算距离呢？图论里有不少算法可以解决这个问题。

     这么做也许是最直观的，但绝对不是最迅速的。如果一个城市只有为数不多的咖啡馆,那这么做应该没什么问题,反正计算量不大。但如果一个城市里有很多咖啡馆,又有很多用户都需要类似的搜索,那么服务器所承受的压力就大多了。在这种情况下,我们该怎样优化算法呢?

     首先，我们可以把整个城市的咖啡馆做一次“预处理”。比如，把一个城市分成若干个“格子(grid)”,然后根据用户所在的位置把他放到某一个格子里，只对格子里的咖啡馆进行距离排序。

     问题又来了，如果格子大小一样，那么绝大多数结果都可能出现在市中心的一个格子里，而郊区的格子里只有极少的结果。在这种情况下，我们应该把市中心多分出几个格子。更进一步，格子应该是一个“树结构”，最顶层是一个大格——整个城市，然后逐层下降，格子越来越小，这样有利于用户进行精确搜索——如果在最底层的格子里搜索结果不多，用户可以逐级上升，放大搜索范围。

     上述算法对咖啡馆的例子很实用，但是它具有通用性吗？答案是否定的。把咖啡馆抽象一下，它是一个点”，如果要搜索一个“面”该怎么办呢？比如，用户想去一个水库玩，而一个水库有好几个入口，那么哪一个离用户最近呢？这个时候，上述“树结构”就要改成“r-tree”,因为树中间的每一个节点都是一个范围，一个有边界的范围（参考：[url]http://www.cs.umd.edu/~hjs/rtrees/index.html[/url]）。

     通过这个小例子，我们看到，应用程序的要求千变万化，很多时候需要把一个复杂的问题分解成若干简单的小问题，然后再选用合适的算法和数据结构。

     上面的例子在Google里就要算是小case了！每天Google的网站要处理十亿个以上的搜索，GMail要储存几千万用户的2G邮箱，Google Earth要让数十万用户同时在整个地球上遨游，并将合适的图片经过互联网提交给每个用户。如果没有好的算法，这些应用都无法成为现实。

     在这些的应用中，哪怕是最基本的问题都会给传统的计算带来很大的挑战。例如，每天都有十亿以上的用户访问Google的网站，使用Google的服务，也产生很多很多的日志（Log）。因为Log每分每秒都在飞速增加，我们必须有聪明的办法来进行处理。我曾经在面试中问过关于如何对log进行一些分析处理的问题，有很多面试者的回答虽然在逻辑上正确，但在实际应用中是几乎不可行的。按照他们的算法，即便用上几万台机器，我们的处理速度都跟不上数据产生的速度。

     那么Google是如何解决这些问题的呢？

     首先，在网络时代，就算有最好的算法，也要能在并行计算的环境下执行。在Google的数据中心，我们使用的是超大的并行计算机。但传统的并行算法运行时，效率会在增加机器数量后迅速降低，也就是说，十台机器如果有五倍的效果，增加到一千台时也许就只有几十倍的效果。这种事倍功半的代价是没有哪家公司可以负担得起的。而且，在许多并行算法中，只要一个结点犯错误，所有计算都会前功尽弃。

     那么Google是如何开发出既有效率又能容错的并行计算的呢？

     Google最资深的计算机科学家Jeff Dean认识到， Google 所需的绝大部分数据处理都可以归结为一个简单的并行算法：Map and Reduce（[url]http://labs.google.com/papers/mapreduce.html[/url]）。 这个算法能够在很多种计算中达到相当高的效率，而且是可扩展的（也就是说，一千台机器就算不能达到一千倍的效果，至少也可以达到几百倍的效果）。Map and Reduce的另外一大特色是它可以利用大批廉价的机器组成功能强大的server farm。最后，它的容错性能异常出色，就算一个server farm里面的机器down掉一半，整个farm依然能够运行。正是因为这个天才的认识,才有了Map and Reduce算法。借助该算法，Google几乎能无限地增加计算量，与日新月异的互联网应用一同成长
[/QUOTE]

[quote]原帖由 [i]benjiam[/i] 于 2008-6-22 23:10 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8638528&ptid=1166775][img]http://bbs.chinaunix.net/images/common/back.gif[/img][/url]
有人做过上亿用户吗？ 有上1kw个用户吗？

分开节点，会有很多问题。 各个节点的及时更新，和状态处理是很麻烦的。

google 的确是nb 的。

qq 原来有道面提 就是考如何快速从1亿个客户里面搜索出相要的数 ... [/quote]

或许这些问题我们能想出解决的方法，觉的也是正确的，可在实际中环境中能不能用，或者能不能非常高效，那就不是我们能想到的，没有实践检验，做成成功的产品，一切都在我们的想像之中，想的都是应该就那么快！

[quote]不要说1亿,即使是10亿行记录, 在数据库里按索引查找的话, 所花时间也不会超过1ms, 检测用户名明显就是按索引查找的, 因此也不会想得太神秘.
至于google网页显示速度快,那是因为它的WEB页面都是用CGI来生成的, 无论如何按生成网页的速度快, C肯定会远快于JAVA和.net
其实googlec真正的功夫，是体现在搜索上，那才真正是几千个节点上的海量数据并行搜索，比查找用户名之类的简单操作难度提高了不止上万倍．[/quote]

我不知道数据库在10亿行记录中找一条有多快，但我知道大型的数据库不是一年两年就开发出来的，从数据库理论提出到现在都多这多年，数据库才发展到现在这个阶段，如果那东西没什么技术含量的话，还用的到今天人们还是在大量的研究吗？
再说就算是用数据库，Google的数据库据说是用的是开源的，在其基础上也进行了修改（因为这事，Google被指责违反了开源的宗旨），但不管怎么说，我们谁有能力去开发大型的商用化的数据库，谁又有能力去在别的数据库的基础去修改，以满足自己的需求！
必须承认人家的算法优秀！

[quote]原帖由 [i]nbroot[/i] 于 2008-6-23 12:19 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8641308&ptid=1166775][img]http://bbs.chinaunix.net/images/common/back.gif[/img][/url]

知其然不知其所以然。

是CGI就快吗？ [/quote]
"不知其所以然的"是你, 只不过你以为别人不知罢了.
CGI快不快,你自已测去吧, 没人想和你争论这种无聊问题.

[quote]原帖由 [i]zhangzhh05[/i] 于 2008-6-23 13:21 发表 [url=http://bbs.chinaunix.net/redirect.php?goto=findpost&pid=8641781&ptid=1166775][img]http://bbs.chinaunix.net/images/common/back.gif[/img][/url]


或许这些问题我们能想出解决的方法，觉的也是正确的，可在实际中环境中能不能用，或者能不能非常高效，那就不是我们能想到的，没有实践检验，做成成功的产品，一切都在我们的想像之中，想的都是应该就那么快 ... [/quote]
google 算法优秀, 没人不承认, 但我说的是, 算法优秀,并不体现在查找一个用户名的这种小问题上,而是体现在其内容搜索上. 如果仅仅是查找用户名, 大家自已在一个10亿行记录的数据库上查找一下就明白了. b-tree已经达到非常令人满意的速度, 时间绝不超过1ms.