V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
牛客网
jasonqiao36
V2EX  ›  Python

如何对服务依赖进行排序?(多服务, 多依赖)

  •  1
     
  •   jasonqiao36 · 28 天前 · 775 次点击

    一个 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 程序表达排序的逻辑呢?

    第 1 条附言  ·  22 天前
    我使用拓扑排序, 已经解决了部分问题, 可以把第一组和第二组服务排出顺序.
    现在还有个问题, 如果第一组服务和第二组服务混在一起了, 如果将他们分成两组, 然后分别进行拓扑排序?
    第 2 条附言  ·  22 天前
    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)))
    
    
    6 条回复    2020-09-29 14:38:05 +08:00
    v2exblog
        1
    v2exblog   28 天前
    是一个树状结构的话, 直接可以遍历树,按层次启动服务。如果要是图结构,就比较麻烦了
    momocraft
        2
    momocraft   28 天前
    "拓扑排序"
    lithbitren
        3
    lithbitren   28 天前
    说起来,3.9 标准库好像有拓扑排序了
    Leigg
        4
    Leigg   28 天前 via Android
    你这都快成环形依赖了,完全是设计问题
    Leigg
        5
    Leigg   28 天前 via Android
    没仔细看,排序的目的是啥呢?
    jasonqiao36
        6
    jasonqiao36   22 天前
    @Leigg #5 服务发布的时候, 有依赖关系, 所以要给服务进行排序
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   4644 人在线   最高记录 5168   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 06:32 · PVG 14:32 · LAX 23:32 · JFK 02:32
    ♥ Do have faith in what you're doing.