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

Question

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

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

第一次尝试

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

       E     /   \    F     G   / \   /  \  H  I  J    Kmapped to:    E - [F, G]    F - [H, I]    G - [J, K]

所以当我想要 E 和它的所有后代时，我使用键递归地得到它的 child 和他们的 child ，它允许我从任何节点开始向下移动。这个解决方案提供了很好的速度提升，但是有 15,000 个节点，大约需要 5000 次缓存命中来重建我的代码树(更糟糕的情况......从 E 开始。性能基于起始节点位置，导致 super 用户看到最差表现)。这仍然很快，但似乎很健谈。我喜欢这样一个事实，即我可以随时通过将节点从键列表中弹出来删除节点，而无需重建整个缓存。在 UI 上可视化地按需构建树也非常快。

第二次尝试

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

---

那么您认为哪种解决方案是更好的方法(随着它的持续增长而长期发展)。两者都非常快并且减轻了数据库的一些负载。或者他们是我没有想到的更好的方法来实现这一点？

谢谢

Answer 1

让我提供一个想法...

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

• 第一次从数据库中获取子树时，将其缓存到内存中。 (您可以通过递归 CTE 优化它并在单个数据库往返中完成。)
• 但是，下次您需要检索相同的子树时，只需检索根即可。然后将缓存的版本与您刚刚从数据库中获取的版本进行比较。
  • 如果它们匹配，很好，您可以停止获取并重新使用缓存。
  • 如果他们不这样做，请获取子项并重复该过程，同时刷新缓存。

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

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

--- 编辑 ---

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

本质上，您指示 DBMS 监视更改并在更改发生时通知您。这是让您的客户端缓存以高效方式保持最新状态的理想选择。