12

2020-02-18 更新

我再次遇到了这个问题，虽然接受的答案保持不变，但我想分享我现在如何优化它（再次不使用第三方库或工具 - 即从头开始重新发明轮子，就像原始问题中提到的那样） .

为了简化和优化这个系统，我将在域逻辑层上使用Trie（前缀树）而不是“倒排索引映射”，并完全摒弃“表查询” SQL 表的不良做法。我将举例说明：

  • 假设该应用程序的一些用户已经在数据库中添加了几个对象：w、wo、woo、wood 和 woodx。
  • 这些对象（字符串/标签）将由内存中的 Trie 表示，每个 Trie 节点将包含该对象在树中所在级别的数据库发布 ID（Think Associative Array）。
  • 当用户查询一个词时，我们在 Trie 中搜索该词并在途中累积所有相关的 ID，从搜索的词开始向下移动（即按顺序从那里遍历）。我们从这些 ID 中检索所有需要的对象数据（无论是来自缓存还是数据库）。

这是一张图片来说明： 特里

  • 接下来，如果用户向数据库中添加一个新词，例如“ woodxe ”，则 Trie 会相应更新。
  • 当用户查询“ woodx ”时，会发生与之前相同的过程，并且会累积一个新的ID（“ woodxe ”的发布ID）
  • 英语词典中有一个以特定字母序列开头的有限单词列表，因此向下移动并获取所有子节点仍然是一个 O(1) 复杂度的有限过程。例如，如果您在 Trie 上以“wood”开头，则在英语词典中以“wood”为前缀的子节点列表是一个有限常数。无论您将所有这些子节点返回给用户、定义限制（延迟加载/分页）还是仅显示前 10 个点击，都是个人架构偏好。

这是一张图片来说明（检查绿色添加的内容） 特里 - 续

  • 当用户的查询是多字串时，例如：“木家具”，每个字都被单独解析/添加到 Trie 中，并且每个字都有相应的匹配 ID 列表。

*Trie* 如何改进以前的架构？

  • “表查询”很麻烦、不好的做法，而且开销很大，而且与数据库成正比增长；现在已删除。
  • 我们拥有的“倒排索引映射”产生了额外的内存开销，并且无法通过新词轻松扩展（如上面的“woodx”示例）。有人可能会争辩说，查询一个 Hashmap 是 O(1)，但是在内存中有几个大的 hashmap 实际上会在一定程度上减慢速度，并且被认为是糟糕的工程设计。
  • trie 的搜索复杂度为 O(m)，其中 m 是提供的字母表中的字符数。由于用户查询的是纯粹使用英文字母的单词，因此最大的子树将等于可用的最大英文单词（常数，即 O(1)）。此外，如前所述，英语词典中以定义的单词前缀开头的子节点的数量也是一个常数，因此遍历所有组合是 O(1)。所以总的来说这是一个 O(1) 操作。
    • 所以查询 Trie = Get key from Hashmap = O(1) 一样快。
    • 最重要的是，在这个系统中尝试的好处是：
      • 比在内存中运行多个倒排索引哈希映射的内存开销更小
      • 集中查询树
      • 易于扩展，添加到数据库的新词只需要在内存中的现有 Trie 中添加几个新节点。即，不再有数据库增长和搜索查询数量增加的问题（可扩展性噩梦）。

2015-10-15 更新

早在 2012 年，我正在构建一个个人在线应用程序，实际上我想重新发明轮子，因为我天生好奇，为了学习目的并提高我的算法和架构技能。我本可以使用 apache lucene 和其他的，但是正如我所提到的，我决定构建自己的迷你搜索引擎。

问题：那么，除了使用可用的服务（如 elasticsearch、lucene 等）之外，真的没有办法增强这种架构吗？

原始问题

我正在开发一个 Web 应用程序，用户在其中搜索特定的标题（例如：book x、book y 等），这些数据位于关系数据库 (MySQL) 中。

我遵循的原则是，从数据库中获取的每条记录都缓存在内存中，这样应用程序对数据库的调用就更少了。

我开发了自己的迷你搜索引擎，具有以下架构：
架构图
这是它的工作原理：

  • a) 用户搜索记录名称
  • b）系统检查查询以什么字符开头，检查是否有查询：获取记录。如果不存在，则添加它并使用两种方式从数据库中获取所有匹配记录：
    • 表“查询”（这是一种历史表）中已经存在的任一查询，因此根据 ID 获取记录（快速性能）
    • 或者，否则使用Mysql LIKE %% 语句来获取记录/ID（然后将用户使用的查询连同它映射到的 ID 一起保存在历史表查询中）。
      -->然后它将记录及其ID添加到 缓存中，并且仅将ID添加到倒排索引映射中。
  • c) 结果返回到 UI

该系统工作正常，但是我有两个主要问题，我找不到一个好的解决方案（过去一个月一直在尝试）：

第一个问题：
如果您检查点 (b) ，没有找到查询“历史”并且它必须使用Like %%语句的情况：当查询匹配数据库中的大量记录（而不是一个或二）：

  • 从 Mysql 获取记录需要一些时间（这就是我在特定列上使用 INDEXES 的原因）
  • 然后是时候保存查询历史了
  • 然后是时候向缓存和倒排索引图添加记录/ID

第二个问题：
应用程序允许用户自己添加新记录，其他登录到应用程序的用户可以立即使用这些记录。
然而，为了实现这一点，必须更新倒排索引映射和表“查询”，以便在任何旧查询与新词匹配的情况下。例如，如果要添加新记录“woodX”，旧查询“wood”仍然会映射到它。因此，为了将查询“wood”重新连接到这个新记录，这就是我现在正在做的事情：

  • 新记录“woodX”被添加到“记录”表中
  • 然后我运行一个Like %%语句来查看表“查询”中哪个已经存在的查询映射到该记录（例如“wood”），然后将此查询与新记录 id 添加为新行： [ wood, new ID]。
  • 然后在内存中，更新倒排索引 Map 的“wood”键的值（即列表），将新的记录 ID 添加到这个列表中

--> 因此，现在如果远程用户搜索“wood”，它将从内存中获取：wood 和 woodX

这里的问题也是时间消耗。将所有查询历史（在表查询中）与新添加的单词匹配需要很长时间（匹配的查询越多，时间越长）。那么内存中的更新也需要很多时间。

我正在考虑解决这个时间问题，首先将所需的结果返回给用户，然后让应用程序使用所需的数据发布一个ajax调用以实现所有这些更新任务。但我不确定这是一种不好的做法还是一种不专业的做事方式？
所以在过去的一个月里（再多一点），我试图为这个架构考虑最好的优化/修改/更新，但我不是文档检索领域的专家（实际上它是我构建的第一个迷你搜索引擎）。

对于我应该做些什么来实现这种架构，我将不胜感激任何反馈或指导。
提前致谢。

PS：

  • 它是一个使用 servlet 的 j2ee 应用程序。
  • 我正在使用 MySQL innodb（因此我不能使用全文搜索选项）
4

4 回答 4

2

我不得不说，我认为你的设计不太适合这个问题。你现在看到的问题就是这样的后果。除此之外，您当前的解决方案无法扩展。

这是一个可能的解决方案：

  1. 重新设计您的数据库，使其仅包含权威数据，但不包含派生数据。所以所有缓存条目都必须从 MySQL 中消失。

  2. 仅在应用程序内存中的请求期间保留数据。这使您的应用程序设计更加简单（想想竞争条件），并使您能够扩展到合理数量的客户端。

  3. 引入缓存层。我强烈建议使用已建立的产品，而不是自己构建。这使您摆脱了应用程序中所有自定义构建的缓存逻辑，甚至可以更好地完成工作。

您可以查看 Redis 或 Memcached 的缓存层。我认为 LRU 策略应该适合这里。根据您的查询变得多么复杂，像 Lucene 这样的专用索引搜索机制也可能有意义。

于 2015-10-15T11:45:01.807 回答
2

我强烈推荐 Sphinx 搜索服务器，它在全文搜索中得到了最佳优化。访问http://sphinxsearch.com/。

它旨在与 MySQL 一起使用，因此它是您当前工作空间的补充。

于 2015-10-15T16:53:49.047 回答
2

我不假装有解决方案，但这是我的想法。首先，我喜欢你的耗时查询 LIKE%% ：我会在 MySQL 中执行一个仅限于几个答案的查询，比如十几个，然后将其返回给用户，然后等待用户是否想要更多匹配的记录，或者启动在后台进行完整查询，具体取决于您将来搜索的索引需求。

更一般地说，我认为将所有内容存储在内存中可能会导致有一天内存消耗过多。虽然搜索引擎在将所有内容保存在内存中时会变得越来越快，但您必须在添加或更新数据时使所有这些缓存保持最新，这肯定会花费越来越多的时间。

这就是为什么我认为我一天在“开源论坛软件”（我不记得它的名字）中看到的解决方案对于帖子中的文本搜索来说还不错：每次插入数据时，一个名为“Words”的表" 跟踪每个现有单词，另一个表（比如说“WordsLinks”）记录每个单词和它出现的帖子之间的链接。这种解决方案有一些缺点：

  • 数据库中的每次插入、删除、更新都要慢很多
  • 搜索引擎的数据选择必须预先考虑：如果您选择保留您从未保留的两个字母单词，那么对于已经记录的数据来说已经太迟了，除非您启动完整的数据重新处理。
  • 您必须注意 DELETE 以及 UPDATE 和 INSERT

但我认为有一些很大的优势：

  • 计算时间可能与“内存解决方案”（最终）相同，但它是在每个数据库的 Create/Update/Delete 中划分的，而不是在查询时。
  • 寻找一个完整的词，或者“以”开头的词是瞬时的：当被索引时，在“词”表中搜索是二分法的。并且“WordLinks”表查询速度非常快，无论是使用索引。
  • 同时查找多个单词可能很简单：为每个找到的单词收集一组“WordLinks”，并对它们执行交集以仅保留所有这些组共有的“数据库 ID”。例如单词“tree”和“leaf”，第一个可以给出表格记录{1,4,6}，第二个可以给出{1,3,6,9}。因此，对于交集，只保留公共部分很简单：{1, 6}。
  • 单列表中的“Like %%”可能比不同表的不同字段中的许多“Like %%”更快。每个数据库引擎都处理一些缓存：“Words”表可能足够小，可以保存在内存中
  • 我认为如果数据变得庞大，性能和内存问题的风险很小。
  • 由于每次搜索都很快，您甚至可以查找同义词。例如，如果用户没有找到“以太网”的任何内容，则搜索“网络”。
  • 您可以应用规则，例如拆分骆驼大小写单词以从“woodX”生成例如 3 个单词“wood”、“X”、“woodX”。每个“词”的存储和查找都非常轻巧，因此您可以做很多事情。

我认为您需要的解决方案可能是多种方法的混合：例如，您可以保持轻量级的 UPDATE、INSERT、DELETE，并从 TRIGGER 启动“Words”和“WordsLinks”馈送。

只是为了轶事，我看到我公司开发的一个软件，它决定将“一切”（！）保留在内存中。它使我们向客户推荐购买具有 64GB RAM 的服务器。有点贵。它解释了为什么当我看到最终可能导致内存填充的解决方案时，我会非常谨慎。

于 2015-10-14T12:53:23.580 回答
1

我确信这可以在 MySQL 中实现，但仅使用现有的面向搜索的数据库（如Elasticsearch ）会少很多努力。它使用 Lucene 库来实现倒排索引，拥有丰富的文档，支持水平缩放，相当简单的查询语言等等。我想要做到这一点已经做了很多工作，处理缓存、竞争条件、错误、性能问题等将是更多的工作，以使解决方案成为“生产级”。

于 2015-10-15T17:17:55.767 回答