在分布式系统中存储预先输入建议的字典树的最佳方式是什么？

Question

我一直在阅读一些有关尝试的内容，以及它们如何成为提前设计的良好结构。除了 trie 之外，您通常还有节点的键/值对和预先计算的 top-n 建议，以缩短响应时间。

通常，根据我收集的信息，最好将它们保留在内存中以便快速搜索，例如这个问题中建议的内容：拼字游戏单词查找器：构建特里树，存储特里树，使用特里树？。但是，如果您的 Trie 太大并且您必须以某种方式对其进行分片怎么办？ （例如，也许是一个大型电子商务网站）。

预先计算建议的键/值对显然可以在键/值存储中实现（保存在内存中，如 memcached/redis 或数据库中，并根据需要水平调用），但是最好的方法是什么如果内存放不下，是否存储一个 trie？是否应该这样做，或者分布式系统应该在内存中保存部分 trie，同时复制它以使其不会丢失？

或者，可以使用搜索服务（例如 Solr 或 Elasticsearch）来生成搜索建议/自动完成，但我不确定性能是否达到此特定用例的标准。 Trie 的优点是您可以根据其结构预先计算 top-N 建议，让搜索服务来处理网站上的实际搜索。

我知道有现成的解决方案，但我最感兴趣的是学习如何重新发明轮子，或者如果有人想提出这个主题，至少可以了解一下最佳实践.

你有什么想法？

编辑：我也看到了这篇文章：https://medium.com/@prefixyteam/how-we-built-prefixy-a-scalable-prefix-search-service-for-powering-autocomplete-c20f98e2eff1，基本上涵盖使用 Redis 作为跳跃列表的主要数据存储，并使用 mongodb 作为 LRU 前缀。似乎是一个不错的方法，但我仍然想了解是否有其他可行/更好的方法。

Answer 1

我正在阅读 Alex Yu 的《系统设计访谈：内部人士指南》，他简要介绍了这个主题。

特里数据库。 Trie DB 是持久性存储。有两种选项可用于存储数据：

1. 文档存储：由于每周都会构建一个新的 trie，因此我们可以定期对其进行快照，将其序列化，并将序列化的数据存储在数据库中。像 MongoDB [4] 这样的文档存储非常适合序列化数据。
2. 键值存储：特里树可以通过应用以下逻辑以哈希表形式[4]表示：
   • 特里树中的每个前缀都映射到哈希表中的一个键。
   • 每个 trie 节点上的数据都映射到哈希表中的一个值。
   图 13-10 显示了 trie 和哈希表之间的映射。

每个前缀节点上的数字代表搜索该特定前缀/单词的频率。

然后，他建议可能通过按每个字母表（或字母表组，如 a-m、n-z）对数据进行分片来扩展存储。但这会使数据分布不均匀，因为以“a”开头的单词比以“z”开头的单词多。

因此，他建议使用某种类型的分片管理器，它可以跟踪查询频率并根据该频率分配分片。因此，如果“s”的查询量是“z”和“x”的总和的两倍，则可以使用两个分片，一个用于“s”，另一个用于“z”和“x”。

Answer 2

我们可以维护一个单一的字母表起始特里树，并在每次命中时保存/更新频率节点， 与此同时，我们可以创建一个可以进行最频繁搜索并训练机器学习模型的作业。对于并排选取常用的，现在对于搜索参数都可以实现自动完成，同时可以给用户更好的建议。