7

如何为庞大的标签系统（如digg或delicious）设计数据存储？

已经有关于它的讨论，但它是关于集中式数据库的。由于数据应该会增长，因此我们迟早需要将数据划分为多个分片。那么，问题就变成了：如何为分区标记系统设计数据存储？

标记系统基本上有3个表：

Item (item_id, item_content)

Tag (tag_id, tag_title)

TagMapping(map_id, tag_id, item_id)

如果表存储在一个数据库实例中，这对于查找给定标签的所有项目和查找给定项目的所有标签都很好。如果我们需要将数据分区到多个数据库实例中，那就没那么容易了。

对于表Item，我们可以用它的 key item_id对它的内容进行分区。对于表Tag，我们可以用它的 key tag_id来划分它的内容。例如，我们要将表Tag划分为 K 个数据库。我们可以简单地选择数字（tag_id % K）数据库来存储给定的标签。

但是，如何对表TagMapping进行分区？

TagMapping表表示多对多关系。我只能想象有重复。也就是说，TagMappping的相同内容有两个副本。一个用tag_id分区，另一个用item_id分区。在为给定项目查找标签的场景中，我们使用带有tag_id的分区。如果要查找给定标签的项目，我们使用带有item_id的分区。

结果，存在数据冗余。并且，应用程序级别应该保持所有表的一致性。看起来很难。

有没有更好的解决方案来解决这个多对多分区问题？

4

3 回答 3

4

我怀疑是否有一种方法可以优化所有可能的使用场景。如您所说，该表支持两种主要方案TagMapping：查找给定项目的标签，以及查找具有给定标签的项目。TagMapping我认为对于每个可能感兴趣的场景，您将如何使用该表存在一些差异。我只能根据典型的标记应用程序做出合理的假设，如果这太离谱了，请原谅我！

查找给定项目的标签

A1。您将一次显示给定项目的所有标签

A2。您将确保一个项目的所有标签都是唯一的

查找给定标签的项目

B1。您将需要一次给定标签的一些项目（以填充搜索结果页面）

B2。您可能允许用户指定多个标签，因此您需要找到一些匹配多个标签的项目

B3。您将通过某种受欢迎程度对给定标签（或标签）的项目进行排序

鉴于上述情况，我认为一个好的方法是TagMapping逐项分区。这样，给定项目的所有标签都在一个分区上。分区可以更细化，因为项目可能远多于标签，并且每个项目只有少数标签。这使得检索变得容易 (A1)，并且可以在单个分区 (A2) 内强制执行唯一性。此外，该单个分区可以告诉您一个项目是否匹配多个标签 (B2)。

由于您一次只需要给定标签（或标签）的一些项目 (B1)，因此您可以按某种顺序一次查询一个分区，直到您有足够多的记录来填充一页结果。您需要查询多少个分区取决于您有多少个分区、您想要显示多少个结果以及标签的使用频率。每个分区在 tag_id 上都有自己的索引，以有效地回答此查询。

您选择分区的顺序很重要，因为它会影响搜索结果的分组方式。如果排序不重要（即 B3 无关紧要），请随机选择分区，以免您的分区太热。如果排序很重要，您可以构造项目 id，以便它对与结果排序顺序相关的信息进行编码。然后适当的分区方案将注意这种编码。例如，如果结果是按受欢迎程度排序的 URL，那么您可以将顺序项目 ID 与该 URL（或任何类似的）的 Google Page Rank 分数结合起来。分区方案必须确保给定分区内的所有项目都具有相同的分数。查询将按分数选择分区，以确保首先返回更受欢迎的项目 (B3)。明显地，这仅允许一种排序，并且所涉及的属性应该是恒定的，因为它们现在是键的一部分并确定记录的分区。但这并不是一个真正的新限制，因为无论如何要支持各种排序或对易失性属性进行排序并不容易。

于 2010-04-24T04:47:07.727 回答
1

规则是您按要查询的字段进行分区。否则，您将不得不查看所有分区。您确定只需要通过 tag_id 查询 Tag 表吗？我相信不会，您还需要按标签标题查询。这对于 Item 表来说并不那么明显，但是当其他用户为其分配标签时，您可能还想通过 URL 之类的查询来查找 item_id。

但请注意，Tag 和 Item 表具有不可变的标题和 URL。这意味着您可以使用以下技术：

  1. 从标题（用于标签）或 URL（用于项目）中选择分区。
  2. 选择此分区的序列以生成 id。

您要么使用 partition-localID 对作为全局标识符，要么使用不重叠的数字集。无论如何，现在您可以从 id 和 title/URL 字段计算分区。事先不知道分区的数量或担心它将来可能会改变？创建更多它们并加入组，以便您将来可以重新组合它们。

当然，你不能对 TagMapping 表做同样的事情，所以你必须复制。您需要通过 map_id、tag_id、item_id 来查询它，对吗？因此，即使没有分区，您也必须通过创建 3 个索引来复制数据。所以不同之处在于您对每个索引使用不同的分区（按不同的字段）。我认为没有理由担心。

于 2010-04-23T11:47:33.587 回答
1

您的查询很可能与用户或主题相关。这意味着您应该在一个地方拥有与这些信息相关的所有信息。

您在谈论 DB 的分布，通常这主要是同步问题。通常大约 90% 的工作可以在复制数据库上完成读取。问题是如何更新一个数据库并在不影响性能的情况下与所有其他数据库保持一致。这取决于您的方案详细信息。

另一种可能性是像你问的那样对所有数据进行分区而不重叠。您可能会按用户 ID 或主题 ID 进行分区。如果您按主题 ID 进行分区，一个数据库可以引用所有主题，并且只需告诉哪个专用数据库保存数据。然后，您可以查询正确的。由于您按 ID 进行分区，因此与该主题相关的所有信息都可能位于该专用数据库中。您还可以按语言或国家/地区划分国际网站。

最后但并非最不重要的一点是，您最终可能会混合使用这两种数据：一些不重叠的数据和一些重叠（复制）的数据。首先找到通常的操作，然后找到如何在一个数据库上以最少可能的查询进行操作。

PS：不要忘记缓存，它会比分布式数据库节省更多。

于 2010-04-26T10:22:57.467 回答