任何一項(xiàng)服務(wù)后邊都有著無(wú)數(shù)子系統(tǒng)和組件的支撐逼纸,子系統(tǒng)之間也互相依賴關(guān)聯(lián)匈织,其中任意一個(gè)環(huán)節(jié)出現(xiàn)問(wèn)題都可能對(duì)上游鏈路產(chǎn)生影響蜒灰。
輸入每個(gè)系統(tǒng)的依賴關(guān)系盆均,調(diào)用對(duì)應(yīng)系統(tǒng)的耗時(shí)塞弊,用這些數(shù)據(jù)分析端到端鏈路的數(shù)目和鏈路上最長(zhǎng)的耗時(shí)。
【輸入】 搜集到的系統(tǒng)耗時(shí)和依賴列表
5 4 // 表示有5個(gè)系統(tǒng)和 4個(gè)依賴關(guān)系
3 // 調(diào)用1號(hào)系統(tǒng)耗時(shí) 3 ms
2 // 調(diào)用2號(hào)系統(tǒng)耗時(shí) 2 ms
10 // 調(diào)用3號(hào)系統(tǒng)耗時(shí) 10 ms
5 // 調(diào)用4號(hào)系統(tǒng)耗時(shí) 5 ms
7 // 調(diào)用5號(hào)系統(tǒng)耗時(shí) 7 ms
1 2 // 1號(hào)系統(tǒng)依賴2號(hào)系統(tǒng)
1 3 // 1號(hào)系統(tǒng)依賴3號(hào)系統(tǒng)
2 5 // 2號(hào)系統(tǒng)依賴5號(hào)系統(tǒng)
4 5 // 4號(hào)系統(tǒng)依賴5號(hào)系統(tǒng)
【輸出】 調(diào)用鏈路的數(shù)目 和最大的耗時(shí)泪姨, 這里有三條鏈路1->2->5游沿,1->3, 4->5肮砾,最大的耗時(shí)是1到3的鏈路 3+10 = 13诀黍,無(wú)需考慮環(huán)形依賴的存在。
3 13
- 思路仗处,可以將各個(gè)系統(tǒng)當(dāng)做圖的各個(gè)頂點(diǎn)眯勾,然后根據(jù)依賴關(guān)系(有向邊)構(gòu)造出圖,由于不考慮環(huán)形依賴婆誓,因此實(shí)際上得到的是一個(gè)森林吃环。然后遍歷這片森林,得到所有的路徑洋幻。