PDF构建 Nutch：开源搜索
MIKE CAFARELLA 和 DOUG CUTTING，Nutch
编写开源搜索引擎的案例研究
搜索引擎对于互联网的使用至关重要，就像网络基础设施的任何其他部分一样，但它们与其他组件在两个重要方面有所不同。首先，它们的内部运作是秘密的，不像 DNS（域名系统）的运作那样公开。其次，它们掌握着政治和文化权力，因为用户越来越依赖它们来浏览在线内容。
当如此多的人依赖于内部运作严密的服务时，难免会担心出现无意的错误，更不用说滥用职权了。此外，搜索引擎算法保密意味着该领域的进一步发展变得不太可能。许多相关的研究被企业围墙所阻挡，有用的方法仍然在很大程度上不为人所知。
为了解决这些问题，我们启动了 Nutch 软件项目，这是一个开源搜索引擎，任何人都可以免费下载、修改和运行，既可以作为内部 intranet 搜索引擎，也可以作为公共 Web 搜索服务。正如您可能刚刚在 Anna Patterson 的“为什么编写自己的搜索引擎很难”一文中读到的那样，编写搜索引擎并非易事。因此，我们的文章侧重于 Nutch 的技术挑战，但我们当然希望 Nutch 将在技术和社会领域都提供改进。通过使更多人能够运行搜索引擎，并通过代码开源，我们希望搜索算法能够像其重要性所要求的那样透明。
技术挑战
设计搜索引擎的大部分挑战在于使其可扩展。编写一个可以下载少量页面的 Web 爬虫很简单，但编写一个可以定期下载 Web 上近 50 亿页面的爬虫则要困难得多。
此外，搜索引擎必须能够高效地处理查询。需求因网站的受欢迎程度而异：搜索引擎每秒可能接收到不到一次到数百次的搜索。
最后，与许多软件项目不同，搜索引擎可能具有很高的持续成本。它们可能需要大量硬件，消耗大量的互联网带宽和电力。我们将在下一节中更详细地讨论部署成本，但现在记住以下几个想法会很有帮助
• 搜索引擎一部分的成本随文档集合的大小而扩展。当 Nutch 搜索单个 intranet 时，集合可能非常小，但可能像 Web 本身一样大。
• 搜索引擎的另一部分随查询负载的大小而扩展。每个查询都需要一定的处理时间并消耗一些带宽。
• 考虑到这两个因素，我们设计了一个系统，可以轻松地将抓取和查询处理的工作分配到一组标准机器上。
图 1 显示了系统的组件。
WebDB。 WebDB 是一个持久化的自定义数据库，用于跟踪每个已知的页面和相关链接。它维护关于每个页面的少量事实，例如上次抓取的日期。WebDB 旨在长期存在，跨越数月的运行。
由于 WebDB 知道每个链接上次抓取的时间，它可以轻松生成一组抓取列表。这些列表包含我们有兴趣下载的每个 URL。WebDB 将整体工作负载分成几个列表，每个抓取器进程一个列表。URL 几乎是随机分布的；单个域的所有链接都由同一进程抓取，因此它可以遵守礼貌约束。
抓取器消耗抓取列表并开始从互联网下载。抓取器是“礼貌的”，这意味着它们不会用请求使单个站点过载，并且它们遵守 Robots Exclusion Protocol。（这允许网站所有者将站点的某些部分标记为对自动化客户端（如我们的抓取器）关闭。）否则，抓取器会盲目地沿着抓取列表前进，记下生成的下载文本。
抓取器输出 WebDB 更新和 Web 内容。更新告诉 WebDB 自上次抓取尝试以来出现或消失的页面。Web 内容用于生成用户将实际查询的可搜索索引。
请注意，WebDB-抓取周期被设计为永远重复，以维护 Web 图的最新图像。
索引和查询。一旦我们有了 Web 内容，Nutch 就可以准备好处理查询。索引器使用内容生成所有术语和所有页面的倒排索引。我们将文档集划分为一组索引段，每个索引段都馈送到单个搜索器进程。
因此，我们可以将当前索引段集分布在任意数量的搜索器进程上，从而使我们能够轻松地随着查询负载进行扩展。此外，我们可以将索引段复制到多台机器并在每台机器上运行搜索器；这样可以在一台或多台搜索器机器发生故障时实现更好的扩展行为和可靠性。
每个搜索器还利用早期的 Web 内容，因此它可以提供任何 Web 页面的缓存副本。
最后，Web 服务器池处理与用户的交互并联系搜索器以获取结果。每个 Web 服务器都与许多不同的搜索器交互，以了解整个文档集。通过这种方式，Web 服务器同时充当 HTTP 服务器和 Nutch 搜索客户端。
Web 服务器包含很少的状态，可以轻松复制以处理增加的负载。它们只需要被告知现有搜索器机器池即可。它们维护的唯一状态是任何时候可用的搜索器进程列表；如果给定段的搜索器失败，Web 服务器将查询另一个搜索器。
质量。 当然，生成高质量的结果是 Nutch 需要克服的最重要的障碍。如果它不能像商业引擎那样找到相关的页面，那么 Nutch 就没什么用处了。但是它怎么可能与庞大的、付费的工程团队竞争呢？
• 首先，我们认为高质量的搜索是一个缓慢移动的目标。通过一些质量衡量标准，最好的搜索引擎与其竞争对手之间的差距已经大大缩小。在对搜索结果进行了多年的集中关注之后，轶事证据表明，质量的提升越来越难找到。日常搜索用户会在各种引擎上找到许多新功能，但结果质量的真正差异几乎难以察觉。
• 其次，尽管许多搜索工作发生在企业围墙之内，但仍然有相当数量的公共学术工作。搜索引擎使用的许多技术都是 20 世纪 70 年代 IR（信息检索）研究人员发现的。有些人试图将 IR 与语言理解的进步联系起来。随着 Web 的出现，许多不同的团体尝试了链接驱动的方法。我们认为应该有更多的公共研究，但已经有足够多的可以借鉴。
• 第三，我们期望 Nutch 能够比任何其他引擎更快地吸收学术进步。我们认为研究人员和工程师会发现 Nutch 非常有吸引力。如果它成为研究人员进行实验的最简单平台，那么利用研究结果应该非常简单。
• 最后，我们将依靠开源项目的传统优势。来自更多地方的更多人应该参与 Nutch 的工作，这意味着更快的错误查找、更多的想法和更好的实现。从长远来看，由许多机构的研究支持的全球共享努力最终应该能够超越任何公司的私人努力。
一旦开源搜索解决方案与专有实现一样好或更好，公司就没有什么理由不使用开源版本了。它将更便宜，并且运行良好。
垃圾邮件。高的搜索排名对于网站所有者来说可能非常宝贵——以至于许多网站试图用专门设计的内容“垃圾邮件”搜索引擎，以提高其排名。与电子邮件垃圾邮件一样，垃圾邮件发送者可以受益，但代价是日常用户的沉重代价。
这在实践中是如何运作的？搜索引擎倾向于使用一组众所周知的准则来衡量页面与给定查询的相关性。例如，在所有其他条件相同的情况下，包含“parrot”一词 10 次的页面比只包含该词一次的页面更关于鹦鹉。来自其他网站的大量传入链接的页面比传入链接较少的页面更重要。
这意味着欺骗幼稚的搜索引擎可能相当容易。想确保每个鹦鹉爱好者都能找到您的页面吗？在您页面的某个位置重复“parrot”一词 600 次。想提高您页面的入站链接计数吗？付费给一种称为“链接工厂”的站点，以添加数千个指向您页面的链接。
当然，后果是搜索结果可能会被并非真正相关但已成功“欺骗”系统的站点所阻塞。好的搜索引擎不希望他们的结果变得毫无用处，因此他们会尽一切可能来检测这些垃圾邮件技巧。反过来，垃圾邮件发送者会修改他们的技巧以避免检测。结果是搜索引擎和垃圾邮件发送者之间的军备竞赛。
以下是一些众所周知的垃圾邮件技术，以及击败它们的方法
• 网站编写包含某些单词长篇重复的文档。搜索引擎通过消除连续出现超过一定次数的术语来应对。
• 网站使用相同的技巧，但将重复的术语与看起来不错的间隔文本穿插在一起。搜索引擎通过检查文档中单词的统计分布是否与典型的英语语言配置文件匹配来应对。如果偏差太大，则该站点被标记为垃圾邮件发送者。
• 无论查询如何，都希望获得高排名的网站在页面上放置虚假的“不可见”文本。假设该站点提供了一个关于电子产品的页面，所有内容都以白色背景呈现。同一个页面可能包含一篇关于 Britney Spears 的长篇文章，所有内容都以白色文本呈现。用户看不到它，但搜索引擎会看到。搜索引擎通过计算 HTML 的可见部分并丢弃其余部分，甚至通过惩罚使用任何不可见文本的页面来应对。
• 网站使用“User-Agent”标签来识别浏览器类型。如果浏览器是桌面软件，则网站返回常规内容。如果浏览器是搜索引擎的爬虫，则网站返回不同的内容，其中包含数千个“parrot”的重复项。搜索引擎通过惩罚为不同浏览器类型提供实质上不同内容的网站来对抗这种情况。
• 网站使用链接工厂来增加传入链接计数。搜索引擎通过查找统计上不寻常的链接结构来查找链接工厂。链接工厂在计算链接计数之前被丢弃。参与工厂的页面也可能受到惩罚。
其中一些方法可能依赖于保密性来发挥作用，因此有些人会问开源引擎如何可能处理垃圾邮件。随着代码的完全公开，搜索引擎难道不会输掉这场战斗吗？
的确，Nutch 代码不会保留任何秘密。但这些秘密无论如何都很脆弱——垃圾邮件发送者不会花很长时间来击败最新的防御措施。如果搜索必须依靠保密性来击败垃圾邮件，那么垃圾邮件发送者可能会获胜。
至少在电子邮件垃圾邮件领域，击败垃圾邮件发送者的简单方法的时代似乎已经结束。许多最新的击败电子邮件垃圾邮件的技术都是统计驱动的。使用这些方法，即使对源代码有深入的了解也可能对垃圾邮件发送者没有太大帮助。尽管人们可能不愿意在电子邮件上使用这种概率垃圾邮件检测器，因为担心删除一条好的消息，但 Web 信息的大量冗余意味着误报并非如此大的悲剧。
或者，答案可能在于与密码学的类比。人们花了很长时间才了解到最安全的密码系统是那些受到最多公众审查的密码系统，这是一种违反直觉的观念。大多数查看这些系统的人都有充分的动机，并且致力于改进它们而不是击败它们。他们在问题被利用之前就发现了问题。
这种类比可能存在缺陷，但在没有透明度的情况下无法对其进行测试。Nutch 目前是在实现某种形式的公众审查以击败搜索引擎垃圾邮件的最佳尝试。
部署/运营
可扩展性/成本效益。 Nutch 项目经常听到的一个反对意见是，搜索消耗的资源太多，以至于不适合成为一个好的开源项目。事实上，Web 搜索引擎可以用相当少的资金来运营。
关于索引大小的说明：Web 搜索引擎会声明其索引的大小，但这些大小并不直接可比。有些计算它们抓取的页面数量；有些计算可能返回的 URL 数量，即使它们尚未被抓取，而只是被另一个页面引用。此外，许多页面是重复的：给定站点可能会响应多个主机名，从而为其所有页面提供多个 URL。虽然越大几乎总是越好，但可能没有好多少。仅包含 1 亿页面的索引或许可以像 50 亿页面的索引一样满足 99% 的用户搜索。因此，如果您主要对具有成本效益的可用性感兴趣，您可能只会构建一个 1 亿页面的系统。但如果您对吹嘘的权利和满足罕见的、晦涩的搜索感兴趣，那么更大的索引可能是合理的。
在这里，我们将概述 Nutch 的运营成本。所有数字都旨在用于说明，因为硬件、软件和带宽的性能和成本都在不断变化。
Nutch 部署使用两类机器：后端机器，用于抓取、数据库、链接分析和索引任务；以及前端机器，用于执行搜索和提供搜索结果。
典型的后端机器是一个单处理器机箱，配备 1 GB RAM、RAID 控制器和八个硬盘驱动器。文件系统已镜像（RAID 级别 1），并提供 1 TB 的可靠存储。这样一台机器的组装成本约为 3,000 美元。
每 1 亿页需要一台这样的后端机器。因此，要维护 10 亿页面的索引，需要 10 台后端机器，硬件成本约为 30,000 美元。
典型的前端机器是一个单处理器机箱，配备 4 GB RAM 和一个硬盘驱动器。这样一台机器的组装成本约为 1,000 美元。
前端机器的查询处理能力各不相同，具体取决于每台机器必须搜索多少内容。例如，如果每台前端机器被分配搜索 2500 万页，那么每台机器每秒可以执行大约两次搜索。因此，一个 1 亿页面的索引可以用四台前端机器（4,000 美元）进行搜索，而一个 10 亿页面的索引需要 40 台前端机器（40,000 美元），但这样的配置仍然只能处理每秒两次搜索。在这种情况下，访问磁盘驻留索引是主要的瓶颈。
当主索引结构适合 RAM 时，查询处理更具成本效益。特别是，如果每台前端机器只需要处理 200 万页，那么每台机器每秒可以处理大约 50 次搜索。在这种配置中，一个 1 亿页面的索引需要 50 台前端机器（50,000 美元），而一个 10 亿页面的索引需要 500 台机器（500,000 美元）。这是第一种情况每次查询成本的一半。这里的瓶颈主要是 CPU。进一步的搜索软件优化可以使这种配置更具成本效益。
请注意，随着流量的增加，前端硬件很快成为主要的硬件成本。
到目前为止，我们只讨论了原始硬件成本。此外，还有托管成本。这些成本主要包括电力（硬件直接消耗的电力和冷却硬件所需的空调消耗的电力）、带宽和其他成本（机架、网络设备、设施租赁等）。电力在这些成本中占主导地位，并且这些成本加起来很容易超过原始硬件成本。例如，您可能会将硬件成本分摊到三年，因此 100,000 美元的硬件每月不到 3,000 美元；但 100 台机器的电力、空间和带宽很容易超过这个成本。由于托管成本甚至比硬件价格更不稳定，因此我们假设托管成本大约与三年摊销的硬件成本相同。因此，一个完整的系统每月的成本可能在 800 美元到 30,000 美元之间，具体取决于在 1 亿页上每秒两次搜索的性能，到在 10 亿页上每秒 50 页的性能。
关于带宽消耗的说明：如果我们假设 Web 页面平均约为 10 KB，并且每个页面每月必须重新抓取一次，那么每月抓取 10 亿页面大约需要 40 Mbps（兆位每秒）的入站带宽。带宽成本通常是对称的，因此如果您购买了 40 Mbps 的入站带宽，您也购买了 40 Mbps 的出站带宽。如果我们进一步假设搜索结果页面也约为 10 KB，那么，在搜索流量超过每秒 400 次搜索之前，在 10 亿页面的系统中，爬虫的需求主导带宽；之后，搜索主导。
总而言之，虽然 Google 和 Yahoo 的运营成本可能确实很高，但许多 Web 搜索引擎可能不会服务于那么多流量，也不需要搜索那么多页面。在一个部署了大量搜索引擎的世界中，绝大多数将服务于小众受众。这些成本也在研究小组、政府部门以及中小型企业的承受范围之内。
一个更棘手的节省成本的来源是自动化大多数系统管理任务。我们认为在这方面还有很大的提升空间，而 Nutch 尚未开始。目前尚不清楚如何将开源编程风格用于与部署如此紧密相关的事物，但我们需要这样做。
谁应该运行基于 Nutch 的 Web 搜索引擎？ Nutch.org 致力于使 Nutch 软件对每个人都更好。这可能意味着运行一个小型演示站点或为学术研究提供搜索服务，但我们不打算运行一个目标搜索站点。运行这样的服务会将 Nutch 置于与其用户的竞争之中。相反，我们希望主要由其他机构来运行 Nutch 软件。
政府、大学和非营利组织是 Nutch 的绝佳候选者。这些组织通常具有营利性公司没有的特殊义务（例如，老年人组织可能希望提供具有特殊可用性重点的搜索），因此拥有 Nutch 的源代码是一个巨大的优势。此外，这些团体通常没有大量现金用于解决方案。
我们目前还没有关于谁在运行 Nutch 的大量数据。据我们所知，最活跃的 Nutch 用户是大学和学术研究小组。有些人将 Nutch 用作课程的一部分，有些人使用它是因为他们的研究依赖于对他们可以控制的索引页面的访问。其他人正在拆解系统，提取似乎有用的元素。期望研究人员立即反馈更新还为时过早，但我们希望这种情况很快就会到来。
我们希望看到的尤其是一种非营利组织是 PSE（公共搜索引擎），这是一个与任何商业搜索引擎一样好用的搜索站点，但在没有广告或商业参与的情况下运营。这些引擎将有助于兑现 Nutch 使搜索结果对用户更透明的承诺。相反，如果营利性引擎为了商业利益而调整排名，它们将更容易被发现。
PSE 可能会像公共广播频道一样，通过用户、公司或基金会的捐款获得资金。值得注意的是，PSE 不需要处理很大比例的搜索查询就能获得成功。它们的存在将有助于确保搜索用户始终有一个好的替代方案（今天不存在的替代方案）。
那么营利性公司呢？我们认为许多公司都希望运行小型搜索引擎供内部使用或在其公共网站上使用。对于这些公司中的大多数来说，搜索将只是他们必须处理的另一项任务，而不是他们的主要关注点。
Nutch 还应该使小型搜索技术公司更具创造力，就像其他开源项目扩大了小型团队可以完成的工作一样。
我们希望 Nutch 通过提供免费的开源 Web 搜索软件，将有助于促进 Web 搜索的透明度，并增进公众对 Web 搜索算法的了解。
MIKE CAFARELLA 于 1998 年至 2002 年在硅谷初创公司 Marimba Corporation 和 Tellme Networks 担任软件工程师。2002 年，他开始从事 Nutch 项目，并一直持续至今。2003 年，他在华盛顿大学开始攻读计算机科学博士学位课程。他于 1996 年毕业于布朗大学。1997 年，他在英国富布赖特奖学金期间获得了爱丁堡大学的硕士学位。
DOUG CUTTING 从事搜索技术工作超过 15 年。这包括在 Xerox PARC 工作五年，在苹果公司的高级技术集团工作三年，以及在 Excite 工作四年多。1998 年，他编写了 Lucene (http://jakarta.apache.org/lucene/)，这是一个开源搜索库，后来成为 Apache Jakarta 项目的一部分。2002 年，他启动了 Nutch (http://www.nutch.org/)，一个开源 Web 搜索应用程序。
© 2004 1542-7730/04/0400
最初发表于 Queue vol. 2, no. 2—
在 数字图书馆 中评论本文
更多相关文章
Latanya Sweeney - 在线广告投放中的歧视
在线广告中暗示逮捕记录的广告是否比搜索黑人名字的广告更频繁地出现？什么是黑人名字或白人名字？广告必须不利地影响一个种族群体多少次才能被认为是歧视？在线活动是否如此普遍，以至于计算机科学家必须考虑技术设计中的结构性种族主义等社会后果？如果是这样，这种技术应该如何构建？让我们对在线广告投放进行科学的深入研究以找到答案。
Ryan Barrows, Jim Traverso - 将搜索视为不可或缺的一部分
大多数公司必须利用他们的数据来获得竞争优势。知识工作者可用的数据量在过去几年中急剧增长，虽然其中很大一部分存在于大型数据库中，但重要的子集仅以非结构化或半结构化数据的形式存在。如果没有正确的系统，这将导致信噪比持续恶化，从而为试图快速查找信息的忙碌用户制造障碍。三种企业搜索解决方案有助于改进知识发现。
Ramana Rao - 从信息检索到搜索，以及更远
自从 Vannevar Bush 的开创性文章《诚如所思》描绘了学者在机器的帮助下的形象以来，已经过去了将近 60 年，“一种个人在其中存储他所有的书籍、记录和通信的设备，并且是机械化的，因此可以以极快的速度和灵活性进行查阅。”
Anna Patterson - 为什么编写自己的搜索引擎很难
一定有 4,000 名程序员在他们的地下室里敲打键盘，试图构建下一个“世界上最具可扩展性”的搜索引擎。这种情况只发生过几次。从来没有一个大型团队完成过；总是有一到四个人完成了核心工作，然后大型团队才开始构建精细化和生产基础设施。为什么这么难？我们将深入探讨编写搜索引擎时需要考虑的各种问题。本文旨在为那些正在考虑为其网站或 intranet 进行此项工作的个人或小组提供帮助。
© 保留所有权利。