1

In our Ruby on Rails project we have a lot of categorization criteria for recipes, such as cook method, occasion etc. Every recipe belongs to one or several of these categories. When someone starts browsing for recipes, he/she can narrow down to a set of particular categories. Then we need to calculate the number of recipes in all categories accessible from this set ("accessible" means there are recipes in that category that also belong to selected categories). This is similar to how Amazon search works: someone enters 'Software' and there is a menu on the left which says "Books (200)", "Movies (300)" etc, so user can go deeper by clicking on these links.

Right now we've implemented it roughly like that:

  1. Build a set of selected categories from URL;
  2. Perform a query that fetches category ids from all recipes that fall into currently selected criteria;
  3. Build the index which maps all category ids to counts of recipes, and render only those that have non-zero counters;
  4. Store this index in memcached for 24 hours, so we only calculate it once per day for a particular page.

My concern is that if there is a cache miss, building index can take a lot of time. Maybe you have any suggestions how to solve this problem or improve current solution?

4

3 回答 3

1

您所描述的是一个非常糟糕的组合问题：对于每个选定的类别，迭代每个配方，然后迭代该配方的类别，然后返回该类别的配方计数。即使使用优化的 SQL，您也在谈论嵌套子选择，从逻辑上讲，这不能在小于指数的时间内完成。（这意味着当你得到很多食谱时这会很痛苦。）并且可能的组合数量等于（类别）^2，缓存也变得越来越不切实际。

你确定你必须这样做吗？顺便说一句，您对亚马逊的看法是错误的；他们没有像这样的“交叉类别视图”。它们显示搜索命中数，使用搜索索引很容易。在搜索框中输入“软件”不是将软件视为一个类别；它把它当作一个关键字。

如果没有人要求此功能，我建议简化它。在您的类别过滤器视图中，只显示所有匹配的食谱。在每个食谱页面上，您可以显示该食谱所在的所有类别的侧边栏列表，如果您愿意，可以将这些类别计算在内。（它可以很容易地作为一个属性缓存在 Categories 模型中，并在您打开配方时通过预先加载来检索。）

如果您出于某种原因必须这样做——当权者认为用户确实希望看到他们没有过滤的类别的错误印象下要求它——那么至少使用 SQL 来做。嵌套子选择确实会造成伤害并且会占用数据库的内存，但它们会比在 Ruby 中更快。此外，还有一些 Rails 插件会改变缓存的行为，以便您在当前命中显示过期结果，然后为下一次命中重新生成缓存。

但我会认真建议跟踪点击并确定是否有人在投入更多工作之前使用它。

于 2009-10-19T16:04:00.887 回答
0

每天索引不是很干净。为什么不索引它，当你插入或更新数据集时？

插入数据集（如食谱）

  • 启动一个线程，将内容添加到索引中

  • 如果线程（高负载！）发生超时（如 1 秒），请停止它

日常的：

  • 将当前索引保存到磁盘

  • 更新整个索引

  • 如果失败，从磁盘恢复保存的索引

  • 否则将索引读取到内存缓存

于 2009-07-26T20:13:36.653 回答
0

您没有对类别/产品的数量进行任何估计，但我会假设它们有很多:)

如果我想要表现，这是我的方法：（我知道，这很疯狂:)）

  • 对于每个类别，在 memcache 中保留一个位向量，意思是：如果 id n 的产品属于该类别，则第 n 位为 1

让我举个例子：如果产品 1、7、9 和 10 属于 A 类，1、6、9 属于 B 类，而 1、9、11 属于 C，那么：

  • A 是 01000001 01100000
  • B 是 01000010 01000000
  • C是01000000 01010000

当你想计算这些集合的交集时，只需在你的集合之间进行按位与，你就会得到你的结果。

结果是：

  • 结果 = A 和 B 和 C = 01000000 01000000

如果您想为每个类别计算，只需制作另一个类别和结果

评论：

  • 不要忘记在更改数据库中的某些内容时重新计算这些向量
  • 如果您打算与很多类别相交，这非常快
  • 对于每个类别，您必须存储一个大于 TOTAL_NR_OF_PRODUCTS/8 的向量
于 2009-07-26T20:32:12.573 回答