如何对服务依赖进行排序？（多服务， 多依赖）

[jasonqiao36]

一个 java 工程， 可能依赖多个其他的 java 服务，在进行发布的时候， 需要考虑依赖关系。

例如有 a~g, x~z 两组服务， 他们的依赖关系如下：

第一组：
x <--  y  // x 依赖 y

z <--  y  // z 依赖 y


第二组：

a <--  b     //a 依赖 b

c <--  b     // c 依赖 b

b <--  e, f  // b 依赖 e, f 两个服务。下面的服务关系类同， 不再写注释了。

g <--  b

a <--  e

最终排序为：

第一组：
y, [x, z]  // y 是第一批次。x 和 z 都属于第二批次，xz 不分先后

第二组：
[e, f],  b , [a, c, g] // e, f 属于第一批次，b 属于第二批次，a,c,g 属于第三批次

如何用 python 程序表达排序的逻辑呢？

我使用拓扑排序, 已经解决了部分问题, 可以把第一组和第二组服务排出顺序.
现在还有个问题, 如果第一组服务和第二组服务混在一起了, 如果将他们分成两组, 然后分别进行拓扑排序?

from functools import reduce as _reduce


class CircularDependencyError(ValueError):
    def __init__(self, data):
        s = "Circular dependencies exist among these items: {{{}}}".format(
            ", ".join(
                "{!r}:{!r}".format(key, value) for key, value in sorted(data.items())
            )
        )
        super(CircularDependencyError, self).__init__(s)
        self.data = data


def toposort(data):
    if len(data) == 0:
        return

    # Copy the input so as to leave it unmodified.
    data = data.copy()

    # Ignore self dependencies.
    for k, v in data.items():
        v.discard(k)
    # Find all items that don't depend on anything.
    extra_items_in_deps = _reduce(set.union, data.values()) - set(data.keys())
    # Add empty dependences where needed.
    data.update({item: set() for item in extra_items_in_deps})
    while True:
        ordered = set(item for item, dep in data.items() if len(dep) == 0)
        if not ordered:
            break
        yield ordered
        data = {
            item: (dep - ordered) for item, dep in data.items() if item not in ordered
        }
    if len(data) != 0:
        raise CircularDependencyError(data)


if __name__ == "__main__":
    group1 = {"A": {"B", "E"}, "C": {"B"}, "B": {"E", "F"}, "G": {"B"}}
    print(list(toposort(group1)))

    group2 = {"X": {"Y"}, "Z": {"Y"}}
    print(list(toposort(group2)))

    # 如果一开始给的数据, 是group1和2合并在一起的
    # 如何把数据分成两个组, 并且分别做拓扑排序
    init_data = {**group1, **group2}
    print(list(toposort(init_data)))

[0x0208v0]

是一个树状结构的话， 直接可以遍历树，按层次启动服务。如果要是图结构，就比较麻烦了

[momocraft]

"拓扑排序"

[lithbitren]

说起来，3.9 标准库好像有拓扑排序了

[Leigg]

你这都快成环形依赖了，完全是设计问题

[Leigg]

没仔细看，排序的目的是啥呢？

[jasonqiao36]

@Leigg #5 服务发布的时候, 有依赖关系, 所以要给服务进行排序