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

本文关键字：缓存 读取 层次结构 有效地 存储 | 更新日期: 2023-09-27 18:15:00

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

层次结构不经常改变，所以我试图将其移动到RAM (redis)。请记住，我有许多子系统需要它来进行安全调用，而UI需要它来构建CRUD操作树。

第一次尝试

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

<>之前E/'福克/'/'我喜欢。映射到:E - [f, g]F - [h, i]G - [j, k]之前

所以当我想要E和它的所有后代时，我递归地得到它的子节点和它们的子节点，它允许我从任何节点开始向下移动。这个解决方案提供了很好的速度提高，但有15,000个节点，它大约需要5000次缓存点击来重建我的代码树(更糟糕的情况……性能是基于开始节点的位置，导致超级用户看到最差的性能)。这仍然是相当快的，但似乎喋喋不休。我喜欢这样一个事实，即我可以在任何时候通过将节点从键列表中弹出来删除节点，而无需重新构建整个缓存。这也可以快速地在UI上根据需要创建树。

第二次尝试

我的另一个想法是从数据库中获取层次结构，构建树并将其存储在RAM (redis)中，然后将整个东西从内存中取出(它的大小约为2 MB，序列化)。这给了我一个单独的调用(不是聊天)到redis拉出整个树，定位用户的父节点，并下降到获得所有的子项目。这些调用很频繁，在网络层传递2mb似乎很大。这也意味着我不能轻松地添加/删除项目，而不拉下树并编辑并将其全部推回去。此外，通过HTTP构建按需树意味着每个请求必须拉下2MB才能获得直接子节点(使用第一种解决方案非常小)。

那么你认为哪个解决方案是更好的方法(长期来看，因为它继续增长)。两者都更快，并减轻了数据库的一些负载。或者他们有更好的方法来实现这一点，我没有想到?

谢谢

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

让我提供一个想法…

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

  • 第一次从数据库获取子树时，将其缓存到RAM。(您可以通过递归CTE对其进行优化，并在单个数据库往返中完成)
  • 但是，下次需要检索同一个子树时，只检索根。然后将缓存的版本与刚从数据库中获取的版本进行比较。
    • 如果它们匹配，很好，你可以停止抓取并重新使用缓存。
    • 如果没有，取出子进程并重复此过程，并在运行时刷新缓存。

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

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

—EDIT—

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

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

如果层次结构不经常更改，您可以计算下面每个节点的整个项目列表(而不仅仅是直接子节点)。这种方式将需要更多的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]}

对于超级用户，每个请求仍然需要传输大量数据，但我不认为有任何方法可以使它更少。

我们这样做。我们将树读入内存，将其存储在应用程序缓存中，然后从内存访问它。由于我们的更改几乎从来没有，也不需要立即反映在web应用程序中，我们甚至不需要费心去检测它们，只需让缓存老化并刷新即可。

相关文章：