PDF为什么编写自己的搜索引擎如此困难
ANNA PATTERSON，斯坦福大学
无论大小、专有还是开源、Web 还是 intranet，这都是一项艰巨的任务。
肯定有 4,000 名程序员在他们的地下室里敲代码，试图构建下一个“世界上最具可扩展性”的搜索引擎。这种情况只发生过几次。从来没有一个大型团队完成过；总是由一到四个人完成核心工作，然后大型团队加入进来构建细化功能和生产基础设施。为什么这么难？我们将深入探讨编写搜索引擎时要考虑的各种问题。本文旨在为那些正在考虑为其网站或 intranet 进行这项工作的个人或小团体而写。这很有趣，但要提醒一句：这不仅困难，而且您还需要两种稀缺的商品——时间和耐心。
超短搜索引擎概述
好的，让我们开始吧。让我们编写一个搜索引擎。
一个爬虫程序从那个讨厌的 Web 上获取网页，并将它们放到您漂亮的磁盘上。您需要很多磁盘。
然后您需要索引这些页面——例如，哪个页面包含哪些词。这将告诉您在 www.superbowl.com 页面上找到了 Janet Jackson。通常，索引发生在您的爬虫程序转储这些网页的本地磁盘上。嘿，为什么要移动它们呢？
在大多数架构中，现在您需要合并这些索引，以便您有一个地方可以找到所有提及 Janet Jackson 超级碗表演的页面。当您合并所有这些小索引时，最终索引将非常大，以至于无法放在一台机器上。这意味着您必须以某种方式合并这些小索引，以便将最终的大索引拆分到多台机器上。
现在您准备好服务查询了吗？错了。现在您构建运行时系统，该系统获取用户的查询，从正确的机器中检索索引中的结果，并根据查询重新对它们进行排名。所有这一切，都是在人们在桌子上敲着手指等待的时候——希望有很多人，并且希望没有足够的时间让他们敲多久。
资源
人们经常谈论构建搜索引擎所需的数千台机器。这听起来很可怕。然而，所有搜索引擎的起步都更多地是依靠思考和设计，而不是机器。因此，让我们看看哪些是事实，哪些是谬论。
带宽。传说风险资本家曾经为年轻的企业家购买硬盘，以证明他们的想法是可行的。现在磁盘很便宜——但新的瓶颈是带宽。通常这需要资本。您首先需要此带宽才能从 Web 获取页面。“CPU 能力”或您使用的机器的内存实际上并不重要。重要的是您拥有（可以负担得起）和可以使用的带宽，因为爬取不是 CPU 的任务——爬取是一个带宽怪物。
有很多方法可以解决这个问题，但最有用的是意识到无论如何您在六个月内都无法让索引器和服务器正常工作（如果可以工作的话），所以慢慢爬取并随着您的进行索引您拥有的内容。错误将在后面的阶段出现，因此缺少页面不会是阻碍您的事情；相反，这将是那些讨厌的错误拖慢您的速度。因此，以您可以负担得起的任何速率（低至 1 兆字节 DSL）持续爬取，剩下的事情会自行解决。当您拥有一个可以在您拥有的页面上运行并且可以跟上您的超慢爬取的搜索引擎时，也许您将有能力通过筹集资金来负担得起大带宽。
通常在托管设施（或机房）中可以找到大带宽。如果您的公司规模超小，我想警告您不要这样做。将带宽连接到办公室！如果您有一个小型团队，您最负担不起的是人们整天在高速公路上奔波前往机房。这是我建议在开发阶段使用小带宽的另一个重要原因。您负担不起一个人花半天时间去更换磁盘的损失。避免机房的另一个原因是它非常昂贵。只需将一堆机器扔到您的桌子底下，并将其视为空间加热器即可。
CPU 问题。 人们整天争论应该为搜索引擎的哪个阶段使用哪种类型的 CPU。大多数人认为，理想的情况是为爬取获得笨 CPU，为索引和服务器获得快速 CPU。这是为什么呢？
您不需要太多思考即可进行爬取；您需要带宽，因此任何旧 CPU 都可以。对于索引，您正在进行大量的 I/O 和大量的思考/分析页面，因此越大越好。在服务时，您将需要根据查询重新对 URL 进行排名，因此再次，越大越好。
但是，由于您自己编写搜索引擎，因此它必须是万能的。大多数值得称赞的索引算法都可能会占用任何 CPU。因此，同样的建议适用：没关系，买您能负担得起的；您编写的错误会比便宜的 CPU 更拖慢您的速度。但是，如果您必须在当地的 Fry's 或 CompUSA 寻找 CPU，则更多的板载缓存将是索引算法的关键，因为更多的页面将保留在板载上。
如果您的算法没有占用 Pentium 4，那么请重新考虑构建更好的搜索引擎的游戏计划，因为您的搜索引擎不会是获胜的那个。
磁盘问题。 SCSI 更快，但 IDE 更大（也更便宜）。如果您自己编写搜索引擎，请使用 IDE。这将以多种方式省钱。您可以获得更大的磁盘，因此一台机器可以轻松容纳 1 TB 的 IDE 磁盘，但 SCSI 并非如此。其次，SCSI 磁盘要贵得多——对于车库里的四个人来说也不是一个好主意。
在运行时，您将受到磁盘的限制。您有两个任务：从磁盘上获取索引条目，并根据相关性对这些条目重新排名。对于从磁盘上获取索引条目，您可能会认为磁盘越快越好。但是用户不会看到您从 SCSI 的磁盘传输速率中获得的性能提升，因为需要大量实践搜索引擎的最终游戏（运行时架构）才能使这种差异成为问题。相反，使用并行性和多个廉价磁盘来实现这种加速。这仍然可以为您节省购买更少机器的钱，并让您练习搜索引擎架构的关键工具——并行性。
啊，但是 SCSI 是热插拔的，您说。克服它。请记住，没有机房。您负担不起，也不想要它。因此，如果您担心磁盘故障，因为您从垃圾箱中挑选了磁盘，那么我的建议是不要将盖子拧到机器上，也不要为每个磁盘使用四个螺钉。这使得 IDE 非常容易维修，但肯定不是热插拔的。
存储文件。 旧式文件系统曾经对文件大小有限制——其中一些文件系统有 2 GB 的限制。这些文件系统也曾经存在在一个目录中存储大量文件的 issue。由于这些原因，普遍的观点是将一堆 URL 爬取下来并将其塞到一个大文件（直到限制）中，然后再开始下一个文件。即使当前操作系统没有像以前那样多的文件数量限制，将大量页面放入一个文件中仍然是一个好主意。将它们塞进去——直到您的操作系统良好性能的限制。
为什么？当索引或放置爬取时，一个大的连续文件可以节省大量的磁盘寻道——文件越少越好。即使您的磁盘传输速率很高，磁盘寻道也会让您崩溃。您负担不起寻道到文件以处理网页的时间。现在的网页平均大小约为每页 10 KB（我是一个老古董，我记得它们是 2 KB 的时候，其他人记得它们是 1 KB 的时候）。当我们在谈论数百万甚至数十亿个网页时，您不想寻道到磁盘来读取 10 KB。从本质上讲，这将几乎使您的处理时间加倍，并烧毁您从垃圾箱中捡来的磁盘。
虽然您可能认为将每个网页存储在一个文件中在概念上更干净，但这将成为管理上的痛苦——并且还会减慢您的处理速度。
网络。 对于房地产，他们说“位置、位置、位置”。好吧，我通过惨痛的教训学到的一个好的搜索引擎规则是：不要使用 NFS。不要使用 NFS。不要使用 NFS（网络文件系统）。对于一个无法放在一台机器上的索引（您的索引可能无法放在一台机器上），NFS 似乎是一个好主意。它看起来像是完美的解决方案。如果您将索引放在多台机器上，那么 NFS 会让它看起来好像您的索引在一台机器上。听起来不错？这样您就不必自己做或学习任何网络知识。错了！无论如何，您都必须为服务架构做真正的分布式系统工作，所以请克服它，现在就完成这项工作。
当前的 NFS 实现无法承受运行时系统或索引阶段的惩罚，除非使用“昂贵”的专用硬件。
在索引阶段，当您尝试进行大量网络写入时，您会得到损坏的索引。询问 Linux 中 NFS 的贡献者，他们会告诉您同样的事情：尚未准备好迎接严重的惩罚。
接下来，在运行时系统中使用 NFS，您将获得不具有容错能力的机器。如果其中一台 NFS 机器出现故障，则其余机器都会卡住。不好。
要编写/获取的软件
爬虫程序。如果您不使用开源爬虫程序，我的建议是使用超简单的多步骤爬虫程序。这是一个非常重要的建议，可以缩短您几个月的开发时间，因此，如果您忽略了其他一切，请不要忽略这一点。
如果您想自己构建爬虫程序，那么首先获取您想要用作爬虫程序种子的 URL 列表（这些需要是探索 Web 的良好起点——dmoz、Yahoo...）。然后编写任何简单的程序来获取它们。例如，(dolist (y URL 列表) GET y) 基本上就是您所需要的全部。
当您获取这些页面时，分析页面中的传出链接，为您简单的爬虫程序创建一个新列表，然后获取这些链接。您问，重复项怎么办？Linux 上的 Sort | uniq 将为您执行此操作；否则，我认为您可以处理它。这解决了重复 URL 的问题，但重复内容呢？我的建议：在服务时找到它们。
爬虫程序真正困难的问题是执行动态重复消除——消除重复的 URL 和重复的内容。使用我描述的系统，我们避免了获得博士论文，而是获得了一些您可以交给您最小的兄弟姐妹的代码。
索引。 接下来，您需要处理这些页面并构建索引。这很棘手。俗话说，只是不要做错任何事。一步走错，数十亿页将需要太长时间才能处理，而您的 1 MB DSL 爬取线路将显得很快。
关于要索引的不同内容，有一个主要的学习领域。不要获得博士学位；只需索引单词。单词是人们搜索的内容；他们不搜索 N-Gram 或字母或 PTrees 或流中的位置，因此任何其他方法，除了最简单的方法外，都会让您看起来很聪明。但是，嘿，编写您自己的搜索引擎已经够难了。将您拥有的聪明才智留给排名吧。
另外两条关键建议：首先，只需索引您需要服务您的搜索结果类型和执行您的排名类型的数据。不要记录一切，也不要记录所有细枝末节——将这些留到您走向超商业化时再做。首要任务是让一些像样的东西上线。更正——首先让一些东西上线。找出哪里出了问题并修复它。
其次，不要迷恋“索引格式”。神圣的“索引格式”不是搜索引擎的终点，它只是开始。它是一个查看结果的工具，因此请更改它并经常更改它。使用它，您和您的团队将成为能够快速改进搜索结果的赢家。
您为什么要向索引中添加内容？也许您刚刚决定保留索引词是否在标题中会是一个好主意。所以现在您需要一个空间来注释这个事实。您可能有其他想法意味着向索引添加更多数据。
假设您在漫长的黑暗中工作到自豪的一天，当您输入搜索 bug 时，出现了提及 Britney Spears 但没有 bug 的页面。各种各样的事情都会发生。跳舞吧——您快要完成了。继续修复即可。
最后一条建议：在开发阶段，保持基于磁盘的索引架构。您没有获得大量流量，您希望在将哪些项目放入索引方面具有灵活性，并且最重要的是您希望拥有一个快乐的团队。一个快乐的团队不会为位争吵。一个快乐的团队不会看到谁的新功能已包含在内，谁的功能已被排除在外，因为没有足够的内存。购买磁盘，使用功能，并享受乐趣。
动态与静态排名。 最初不要做网页排名。实际上根本不要做。对于这个观察，我冒着被仇恨邮件淹没的风险，但尽管如此，还是不要做网页排名。如果您车库里的四个家伙在没有网页排名的情况下无法让一些像样的东西上线，那么您将无法在有网页排名的情况下获得任何像样的东西。使用源代码，卢克——即 HTML 源代码。
网页排名是对全局性质的漫长分析，将导致您购买更多机器并陷入这个复杂的步骤——排名中的这一个因素。首先利用您可以想到的其他一切：单词是否在标题中？它是否加粗？等等。花时间思考您可以利用的任何东西并尝试一下。
这又将使您获得自由，并使您开发一种适合添加内容和尝试内容的架构。这将在以后变得非常宝贵。
服务。 运行时系统很难。算法很难。搜索引擎最难的部分是您必须同时做这两件事。它们必须协同工作，并且两个部分都绝对至关重要。
在服务时，您必须从索引中获取结果，按照它们与查询的相关性对它们进行排序，并将它们粘贴到漂亮的网页中并返回它们。
如果听起来很容易，那么您还没有编写过搜索引擎。请记住，首先，有些查询包含多个单词。这意味着您必须求出这两个单词的索引条目的交集。我的建议是以某种规范的 URL 编号顺序预先排序它们，以便您可以将两个 (n) 个索引条目视为两个堆栈并弹出，直到顶部相等，在这种情况下，您赢得奖品——URL 在两个索引条目中。这些类型的计算必须在查询时运行，并且需要快速运行，因此请认真思考您将如何进行交集。
下一个问题，查询时排名。现在您有了 URL 列表，您必须根据您的相关性算法对它们进行排名。这必须很快。人们正在等待。
在运行时最快的事情是预先排名，然后根据您的索引结构的预先排名部分进行排序。这通常会导致通用的（读取不是最佳的）排名算法。当您进行排名时，您需要考虑实际的查询。因此，您需要在索引中包含一些数据，以帮助考虑查询并在运行时快速重新排名您的先验排名。
对于基本的运行时架构，您会发现无数人愿意争论执行它的“适当”方法。在实践中，有两种基本的基于磁盘的方法和其他基于内存的方法。由于我们正在廉价地进行此操作，因此我们将仅介绍基本的基于磁盘的方法。
第一种主要方法是：在本地索引文件后——您的爬虫程序将它们存放在那里——将小索引留在那里。是的，什么都不做。这意味着在运行时，您要求所有拥有适当查询答案的机器尽快回复您。只要您愿意，就敲着手指，然后将这些小列表收集到一个大列表中，并对该列表进行相关性排序。
另一种方法是预先将特定单词的所有结果收集到一个大列表中。然后，当查询到达时，转到相应的机器，获取列表，然后根据相关性排序。在不显示太多偏见的情况下，从光明的一面看：对于罕见的查询或晦涩的词语，这些是等效的。
没有出错的余地
当您查看所有这些步骤和所有复杂性时，此过程充满了可能出错的事情。编写搜索引擎最困难的部分是您将处理数十亿个 URL 并服务数百万甚至数十亿个查询。这没有太多出错的余地。一个超线性算法应用于错误大小的项目列表，您就完蛋了。一个锁在另一个锁内，您就完蛋了。不会有未探索的代码路径。您代码中所有那些打印出“这永远不会发生”之类的错误的注释都会发生。
当您认为您完成时，仍然有负载均衡、缓存、DNS 服务器、广告服务、图像服务器、更新架构，以及（以熟悉的曲调开始）磁带驱动器中的磁带盒。哦，如果您想听听已经完成这项工作的人的意见，请阅读 Mike Cafarella 和 Doug Cutting 的文章“Nutch：开源 Web 搜索”，在本期第 54 页。
可悲的是，在编写您自己的搜索引擎时，最大的问题是时间耗尽。现实生活常常会干扰并迫使您结束您的探索。在这种情况下，振作起来；一旦搜索错误缠上您，您就会回来的。问题并没有变得更容易，它需要任何人都能聚集的所有经验。
ANNA PATTERSON ([email protected]) 编写了两个搜索引擎。最近，她通过在 Internet Archive 的 Recall.Archive.org 上索引 300 亿个网页，编写了世界上最大的索引。1998 年，她在 Xift 与人合著了一个搜索引擎，她在那里是创始人之一。她获得了伊利诺伊大学厄巴纳-香槟分校的计算机科学博士学位，并且曾在斯坦福大学担任研究科学家，在那里她从事现象级数据挖掘工作。她还是三个学龄前儿童的母亲，他们有时让她进行黑客攻击。
© 2004 1542-7730/04/0400 $5.00
最初发表于 Queue vol. 2, no. 2—
在 数字图书馆 中评论本文
更多相关文章
Latanya Sweeney - 在线广告投放中的歧视
在线广告是否更常出现在搜索带有黑人名字而非白人名字的记录中？什么是黑人名字或白人名字？一个种族群体的不利广告必须出现多少次才能被视为歧视？在线活动是否如此普遍，以至于计算机科学家必须考虑技术设计中的结构性种族主义等社会后果？如果是这样，这种技术该如何构建？让我们深入研究在线广告投放，以找到答案。
Ryan Barrows, Jim Traverso - 将搜索视为不可或缺的一部分
大多数公司必须利用他们的数据来获得竞争优势。知识工作者可用的数据量在过去几年中急剧增长，虽然其中很大一部分存在于大型数据库中，但重要的子集仅以非结构化或半结构化数据的形式存在。如果没有正确的系统，这会导致信噪比持续恶化，为试图快速查找信息的繁忙用户制造障碍。三种企业搜索解决方案有助于改善知识发现。
Ramana Rao - 从信息检索到搜索，以及更远
自从范内瓦·布什的开创性文章《诚如所思》描绘了学者在机器帮助下的形象以来，已经过去了将近 60 年，“一种个人在其中存储他所有的书籍、记录和通信的设备，并且它是机械化的，因此可以以极快的速度和灵活性进行查阅。”
Mike Cafarella, Doug Cutting - 构建 Nutch：开源搜索
搜索引擎对于互联网的使用至关重要，就像网络基础设施的任何其他部分一样，但它们在两个重要方面与其他组件不同。首先，它们的内部运作是秘密的，不像 DNS（域名系统）的运作那样。其次，它们掌握着政治和文化权力，因为用户越来越依赖它们来导航在线内容。
© 保留所有权利。