物化路径 - materialize-project-hierarchy

bp materialize-project-hierarchy

为了有效地管理分层多租户数据，现有的邻接列表范式是不够的：需要递归来遍历树。物化路径概念允许您在单个请求操作中找到节点的所有祖先、后代和子节点。

问题描述

假设项目层次结构如下

+------------------------+
|           A            |
|                        |
|        /      \        |
|                        |
|       /        \       |
|                        |
|      B          C      |
|                        |
|    /   \       /  \    |
|                        |
|   /     \     /    \   |
|                        |
|  D       E   F      G  |
+------------------------+

  • 请求项目的全部父级、祖父级等等，需要递归：后端请求的数量等于树的深度；

  • 请求整个项目的“家族”需要递归：要获取子树节点，需要从子子树递归地构建它；

  • 删除项目 A 将导致树的遍历，伴随着逐层删除：首先找到所有子树级别，然后按从叶到根的顺序删除所需的节点。

提议的变更

可以通过在模型中存储整个项目世系而不是简单的父级链接来避免递归。

例如

DELIMITER = '->'
project.pedigree = A.id + DELIMITER + B.id + .. + DELIMITER + D.id

因此，每个项目都存储了它的世系，这使得可以发现所有需要检查的项目，并且所有后代项目都将拥有以祖先世系开头的世系。

此更改建议添加到 Resource SQL 驱动程序，因为整个 HMT 都是以这种方式实现的

  • 在 Resource 模型中添加 pedigree 列

  • 更改以下驱动程序方法的逻辑以使用物化路径：* _get_children：将被移除 * list_projects_in_subtree：所有具有以相应列值项目世系开头的项目 * list_project_parents：世系已经包含所有 ID 的祖先链，并且可以使用一个批量请求接收所有相应的项目引用。 * is_leaf_project：检查以相应列值项目世系开头的项目是否不存在

为了使物化路径工作，后端必须能够执行前缀通配符搜索或存储和索引数组字段。因此，pedigree 列可以是包含分隔符分隔的项目 ID 的文本字段，也可以是它们的数组。

备选方案

先序树遍历 提供了一个有趣的模式，允许使用紧凑的字段，但许多树操作涉及完整的树重排序，或者至少使用 SQL 后端中未使用的索引执行比较运算符。 想法是按照以下规则在每个节点中存储 left 和 right 整数标记：任何后代节点都具有 left 和 right 在当前节点的 left 和 right 之间。（current.left < descendant.left < descendant.right < current.right）

邻接列表 提供了一种最灵活的方式来描述任何图，但它在 SQL 后端中将导致一个大小高达 N*(N-1)/2 的两列索引表，这将导致修改操作性能不佳。

邻接矩阵 是执行特殊图论计算的完美工具，需要专门的软件才能有效。

对于小型部署，缓存项目结构可能是一个更容易的答案，当可扩展性成为问题时，缓存系统本身可能成为一个复杂的问题，并带有它自身的问题。

安全影响

无

通知影响

无

其他最终用户影响

无

性能影响

树结构上的操作可以在单个查询中完成，而无需递归。例如：* 要删除子树，需要删除以项目世系开头的项目；* 要获取父 ID，无需使用后端 - 整个世系已经存储在模型中；* 要将子树移动到另一个节点，所有移动节点的 pedigree 都必须更新，以便用新的父 ID 替换旧的父 ID。

算法比较

Get parent chain for D using ``parent_id``:
  1. Request parent for D -> B
  2. Request parent for B -> A

  Total: 2 requests (the deeper the tree the more requests are needed)

Get parent chain for D using ``pedigree``:
  1. Disassemble ``pedigree`` -> A.id/B.id/D.id
  2. Request the content for A, B

  Total: 1 request (independent of tree depth)

Get children of a node using ``parent_id``:
  1. Request all nodes with ``parent_id`` == node.id

  Total: 1 request, 1 filter by index

Get children of a node using ``pedigree``:
  1. Request all nodes with ``pedigree`` starting with node.pedigree,
  size of node.pedigree + size of node.id + size of delimiter

  Total: 1 request, 1 filter by index, 1 sequence scan filter

Get sub-tree of a node using ``parent_id``:
  1. For each node request all nodes with ``parent_id`` == node.id

  Total: 7 requests (1 for every node in sub-tree)
  BFS yields 2 requests here: 1 request per level of the tree.

Get sub-tree of a node using ``pedigree``:
  1. Request all nodes with ``pedigree`` starting with node.pedigree

  Total: 1 request (independent of tree depth)

Delete the sub-tree of the node using ``parent_id``::
  1. Traverse the tree to find leaf nodes
  2. Go up deleting them

  Total: 1 request per node on traversal + 1 per node on deletion
  May be optimised using BFS to iterate through levels and deleting groups
  of siblings.

Delete the sub-tree of the node using ``pedigree``::
  1. Delete everything with ``pedigree`` starting with node ``pedigree``

  Total: 1 request (independent of tree depth)

Move the sub-tree using ``parent_id``::
  1. update sub-tree top node's ``parent_id`` field with the new parent id

  Total: 1 request updating 1 node (independent of tree depth)

Move the sub-tree using ``pedigree``::
  1. update ``pedigree`` of all nodes with ``pedigree`` starting with the old
  parent ``pedigree`` replacing it with the new parent ``pedigree``

  Total: 1 request updating all moved nodes

其他部署者影响

树的深度限制可以增加（如果未完全删除）：唯一的限制是世系列的容量。

开发人员影响

另一个好处是简化了 HMT 情况下的令牌验证。通过令牌的项目过滤撤销事件

  1. 请求令牌项目的世系

  2. 请求是否存在世系中包含项目 ID 的撤销事件

示例

User's U role R on project A was revoked. Client authenticated as user U has
a token scoped to project D. Request to check if token is revoked: revocation
event with user U, specified role, project in [A, B, D] exists.

结构存储可能让开发人员在使用起来感觉有点复杂。

实现

负责人

谁在编写代码？或者这是一个蓝图，您正在将其抛出以查看谁会接受它？

如果有多个人正在进行实现，请指定主要作者和联系人。

主要负责人

amakarov

其他贡献者

rodrigodsousa raildo

工作项

数据库迁移：* 在资源模型中添加 pedigree 列 * 使用 parent_id 计算实际世系，填充每个项目的 pedigree 列。 * 在 pedigree 上创建 btree 索引。 * 删除 parent_id 及其索引。

依赖项

  • 在 Keystone 或其他项目中包含对规范和/或蓝图的具体引用，该项目依赖于或与该项目相关。

  • 如果这需要 Keystone 当前未使用的另一个项目的功能（例如，当我们之前只需要 v1 时使用的 glance v2 API），请记录这一事实。

  • 此功能是否需要任何新的库依赖项或未包含在 OpenStack 中的代码？或者它是否依赖于库的特定版本？

文档影响

无

参考资料