如何有效地存储和从缓存中读回层次结构

Question

我的情况是，我目前正在 SQL 数据库中存储一个层次结构，该数据库很快接近 15000 个节点（5000 个边）。该层次结构根据用户在树中的位置定义我的安全模型，授予对下面项目的访问权限。因此，当用户请求所有受保护项目的列表时，我使用 CTE 在数据库中递归它（并展平所有项目），这开始显示其年龄（缓慢）。

层次结构并不经常更改，因此我尝试将其移至 RAM（redis）中。请记住，我有许多子系统需要它来进行安全调用，并且需要 UI 来构建用于 CRUD 操作的树。

第一次尝试

我的第一次尝试是将关系存储为键值对 （这就是它在数据库中的存储方式）

       E
     /   \
    F     G
   / \   /  \
  H  I  J    K

mapped to:
    E - [F, G]
    F - [H, I]
    G - [J, K]

因此，当我想要 E 及其所有后代时，我使用键递归地获取它的子节点及其子节点，并且它允许我从任何节点开始向下移动。该解决方案提供了良好的速度提升，但对于 15,000 个节点，在代码中重建我的树大约需要 5000 次缓存命中（最糟糕的情况......从 E 开始。性能基于起始节点位置，导致超级用户看到最差表现）。这仍然相当快，但似乎很闲聊。我喜欢这样一个事实：我可以随时将节点从键列表中弹出来删除它，而无需重建整个缓存。在 UI 上按需可视化地构建一棵树也非常快。

第二次尝试

我的另一个想法是从数据库中获取层次结构，构建树并将其存储在 RAM（redis）中，然后将整个内容从内存中取出（大约 2 MB）尺寸，序列化）。这让我对 redis 进行了一次调用（不那么啰嗦）来拉出整个树，找到用户的父节点，然后向下获取所有子项。这些调用很频繁，并且在网络层向下传递 2 MB 显得很大。这也意味着我无法轻松添加/删除项目，而不需要拉下树并编辑并将其全部推回。此外，通过 HTTP 构建的按需树意味着每个请求必须拉低 2MB 才能获得直接子级（使用第一个解决方案时非常小）。

---

那么您认为哪种解决方案是更好的方法（从长远来看，随着它的不断增长）。两者都无疑更快并且减轻了数据库的一些负载。或者他们是我没有想到的更好的方法来实现这一目标？

谢谢

Answer 1

让我提供一个想法...

使用分层版本控制。当图中的节点被修改时，会增加其版本（数据库中的一个简单的 int 字段），但也会增加其所有祖先的版本。

• 当第一次从数据库获取子树时，将其缓存到RAM中。 （您可以通过递归 CTE 来优化它，并在单个数据库往返中完成它。）
• 但是，下次您需要检索相同的子树时，仅检索根。然后将缓存的版本与刚刚从数据库中获取的版本进行比较。
  • 如果它们匹配，那就太好了，您可以停止提取并重新使用缓存。
  • 如果没有，请获取子级并重复该过程，并随时刷新缓存。

最终结果是，通常情况下，您会很早就剔除提取，通常只在一个节点之后，您甚至不需要缓存整个图。修改费用昂贵，但这应该不是问题，因为它们很少见。

顺便说一句，类似的原理会在相反的方向发挥作用 - 即当您从叶子开始并需要找到到根的路径时。您需要以相反的方向更新版本控制层次结构，但其余部分应该以非常相似的方式工作。您甚至可以组合使用两个方向。

--- 编辑 ---

如果您的数据库和 ADO.NET 驱动程序支持它，则可能值得研究服务器通知，例如 MS SQL Server 的 SqlDependency 或 OracleDependency。

本质上，您指示 DBMS 监视更改并在更改发生时通知您。这非常适合以有效的方式使客户端缓存保持最新状态。

Answer 2

如果层次结构不经常更改，您可以计算每个节点下面的整个项目列表（而不仅仅是直接子节点）。
这样，您将需要更多的 RAM，但对于任何用户来说，它的工作速度都快如闪电，因为您将能够在单次读取中读取后代节点的整个列表。

对于您的示例（我将使用 JSON 格式）：

E - {"direct" : [F, G], "all" : [F, G, H, I, J, K]}
F - {"direct" : [H, I], "all" : [H, I]}
G - {"direct" : [J, K], "all" : [J, K]}

好吧，对于超级用户，您仍然需要为每个请求传输大量数据，但我没有看到任何方法可以减少数据量。

Answer 3

我们做这样的事情。我们将树读入内存，将其存储在应用程序缓存中，然后从内存中访问它。由于我们几乎从不进行更改，并且更改不必立即反映在 Web 应用程序中，因此我们甚至不必费心去检测它们，只需让缓存老化并刷新即可。它对我们来说非常有效。