1. 為什么一圈代碼會(huì)跑不完環(huán)檢測(cè)到底在解決什么問(wèn)題1.1 先講一次把我整懵的“卡死”經(jīng)歷前陣子我接到一個(gè)排查任務(wù)線上服務(wù)時(shí)不時(shí)出現(xiàn)請(qǐng)求超時(shí)日志里沒(méi)有任何報(bào)錯(cuò)只有某個(gè)接口的耗時(shí)曲線突然拉滿。翻代碼發(fā)現(xiàn)做權(quán)限校驗(yàn)時(shí)需要遞歸向上找“上級(jí)組織”有兩個(gè)組織節(jié)點(diǎn)被配成了互相指向?qū)Ψ?。這一遞歸進(jìn)去A找上級(jí)BB找上級(jí)A永遠(yuǎn)跳不出來(lái)直到線程池被耗盡。最后定位到原因時(shí)同事說(shuō)了句大白話“這不就是循環(huán)了嘛。”那個(gè)瞬間我才意識(shí)到環(huán)Cycle這個(gè)問(wèn)題在工程里出現(xiàn)的頻率遠(yuǎn)比想象中高依賴解析、任務(wù)編排、模塊加載、引用計(jì)數(shù)、狀態(tài)機(jī)遷移、死鎖檢測(cè)甚至正則表達(dá)式里的前向引用背后全是判環(huán)問(wèn)題。Cycle Finding說(shuō)直白點(diǎn)就是在一張圖里找出是否存在某個(gè)回路或者更進(jìn)一步把這條回路完整地挖出來(lái)。它不是一個(gè)只在算法書里出現(xiàn)的名詞而是很多線上故障的罪魁禍?zhǔn)住?.2 有向圖判環(huán)與無(wú)向圖判環(huán)壓根不是一回事很多人一開始容易犯的錯(cuò)就是把“圖里有環(huán)”這件事想得太簡(jiǎn)單。同樣是環(huán)在有向圖和無(wú)向圖里判定邏輯和算法選擇差異非常大。舉一個(gè)例子。無(wú)向圖里兩個(gè)節(jié)點(diǎn)之間只有一條邊三個(gè)節(jié)點(diǎn)兩兩相連就是三角形這在無(wú)向圖里是一個(gè)環(huán)。但在有向圖里如果邊是A指向B、B指向A這當(dāng)然算環(huán)而三條邊如果方向一致A→B→C→A也算環(huán)可如果方向不統(tǒng)一A→B→CC→A也可能構(gòu)成環(huán)。有向圖的環(huán)必須沿著邊的方向走能走回起點(diǎn)才算數(shù)所以判斷時(shí)要考慮方向性。無(wú)向圖的環(huán)則只要“連通性”上出現(xiàn)多余一條通路即可。這兩類問(wèn)題的算法完全不同鏈表場(chǎng)景里經(jīng)典的做法是快慢指針也就是Floyd判圈算法有向圖里更常用的是DFS顏色標(biāo)記和拓?fù)渑判驘o(wú)向圖里則常用并查集和DFS。實(shí)際工程里你得先回答一個(gè)前置問(wèn)題我要處理的圖是有向的還是無(wú)向的邊有沒(méi)有方向這個(gè)回答錯(cuò)了后面所有算法都白搭。2. 烏龜和兔子Floyd判圈算法里最反直覺的那步2.1 快慢指針的物理直覺Floyd判圈算法是我最早接觸的Cycle Finding方案很多人也叫它“龜兔賽跑”。核心思路非常樸素用兩個(gè)指針同時(shí)從起點(diǎn)出發(fā)一個(gè)每次走一步另一個(gè)每次走兩步。如果鏈表中存在環(huán)那么快指針最終一定會(huì)“追上”慢指針并且兩者在環(huán)內(nèi)相遇如果沒(méi)有環(huán)快指針會(huì)先走到終點(diǎn)問(wèn)題結(jié)束。為什么這樣能判環(huán)你可以想象兩個(gè)人在環(huán)形跑道上跑步速度快的人跑了兩圈之后和速度慢的人套圈相遇。鏈表里的“環(huán)”本質(zhì)上就是一條單向循環(huán)跑道快指針走兩步、慢指針走一步它們之間的相對(duì)速度是一步只要存在環(huán)它們的距離一定會(huì)逐步縮短到零也就是相遇。這個(gè)方案最值錢的地方在于只用兩個(gè)指針額外空間復(fù)雜度是O(1)不依賴哈希表去記錄訪問(wèn)過(guò)的節(jié)點(diǎn)。2.2 找到環(huán)的入口為什么第一次相遇點(diǎn)藏著答案判定環(huán)是否存在只是第一步很多場(chǎng)景下我們還想知道環(huán)的入口在哪。Floyd算法里另一個(gè)著名結(jié)論是在快慢指針第一次相遇時(shí)把其中一個(gè)指針重置到鏈表頭部然后兩個(gè)指針都改成每次走一步它們?cè)俅蜗嘤龅奈恢镁褪黔h(huán)的入口。這個(gè)結(jié)論看起來(lái)神神叨叨但推導(dǎo)并不復(fù)雜。設(shè)鏈表頭到環(huán)入口的距離為a入口到第一次相遇點(diǎn)的距離為b相遇點(diǎn)到入口的剩余距離為c那么環(huán)周長(zhǎng)就是bc。慢指針走了ab快指針走了ab k*(bc)其中k是快指針多繞的圈數(shù)。由于快指針?biāo)俣仁锹羔樀膬杀端杂衋bk*(bc) 2(ab)整理后得到 a k*(bc) - b。當(dāng)k1時(shí)a c。也就是說(shuō)當(dāng)一個(gè)指針從頭部出發(fā)走a步到達(dá)環(huán)入口時(shí)另一個(gè)指針從相遇點(diǎn)出發(fā)走c步也能到達(dá)環(huán)入口因?yàn)橄嘤鳇c(diǎn)到環(huán)入口的距離恰好也是c。這就解釋了為什么“重置一個(gè)指針后同速走必然在入口碰到”。實(shí)際編碼的時(shí)候只需要注意邊界條件鏈表為空、只有一個(gè)節(jié)點(diǎn)、沒(méi)有環(huán)這三種情況都要單獨(dú)處理。我在某頭中圖的實(shí)現(xiàn)里踩過(guò)一次空指針就是因?yàn)橥伺袛鄁ast.next可能為null。def detect_cycle_entry(head): slow, fast head, head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: break else: return None # 重置其中一個(gè)指針 slow head while slow ! fast: slow slow.next fast fast.next return slow2.3 使用范圍與邊界Floyd算法不是萬(wàn)能的Floyd算法的適用場(chǎng)景非常明確線性結(jié)構(gòu)可能存在尾部環(huán)典型就是單鏈表、迭代器的循環(huán)序列。但如果你面對(duì)的是一個(gè)真正的“圖”比如節(jié)點(diǎn)有多條出邊Floyd就完全不適用了。因?yàn)榭炻羔樢蕾嚨氖且粭l確定的“走下去”的路徑而圖結(jié)構(gòu)里同一個(gè)節(jié)點(diǎn)出發(fā)可能同時(shí)有多個(gè)選擇你無(wú)法定義“下一個(gè)節(jié)點(diǎn)”是誰(shuí)。還有一個(gè)容易忽略的點(diǎn)Floyd只能判斷有沒(méi)有環(huán)和找到入口如果要輸出完整的環(huán)路徑它就不夠用了。鏈表場(chǎng)景里你可以從入口沿著走一圈但圖的場(chǎng)景下還是得依賴DFS和路徑記錄。所以我現(xiàn)在的判斷標(biāo)準(zhǔn)是遇到鏈表或單路徑迭代問(wèn)題優(yōu)先想到Floyd遇到多分支的圖直接換算法別再硬套。3. 有向圖上的通用判環(huán)DFS三色標(biāo)記和Kahn拓?fù)渑判?.1 三色標(biāo)記從遞歸棧里找回兜底有向圖判環(huán)最直觀的解法是DFS。但普通的DFS加一個(gè)visited布爾數(shù)組是不夠的因?yàn)槟憧赡茉跓o(wú)環(huán)的情況下重復(fù)訪問(wèn)一個(gè)節(jié)點(diǎn)誤判成環(huán)。經(jīng)典的解決方案是給每個(gè)節(jié)點(diǎn)引入三種狀態(tài)0白色未訪問(wèn)1灰色正在當(dāng)前遞歸棧中訪問(wèn)2黑色訪問(wèn)完成確認(rèn)無(wú)環(huán)核心邏輯是DFS遍歷時(shí)如果遇到一個(gè)灰色節(jié)點(diǎn)說(shuō)明從當(dāng)前節(jié)點(diǎn)出發(fā)有一條路徑能走回它自己這就是環(huán)。如果是白色節(jié)點(diǎn)則正常遞歸如果是黑色節(jié)點(diǎn)直接跳過(guò)因?yàn)橐呀?jīng)處理過(guò)了。這個(gè)“灰色”狀態(tài)其實(shí)就是遞歸調(diào)用鏈路的記錄相當(dāng)于把系統(tǒng)棧顯式地搬到了狀態(tài)數(shù)組里。我見過(guò)不少初學(xué)者只用一個(gè)布爾visited結(jié)果在無(wú)環(huán)的有向圖里也會(huì)誤判成有環(huán)問(wèn)題就出在沒(méi)辦法區(qū)分“已經(jīng)處理完的節(jié)點(diǎn)”和“正在處理鏈路上的節(jié)點(diǎn)”。三色標(biāo)記花不了多少代碼量卻能避免這種經(jīng)典的邏輯漏洞。WHITE, GRAY, BLACK 0, 1, 2 def has_cycle(graph): state {node: WHITE for node in graph} def dfs(node): if state[node] GRAY: return True if state[node] BLACK: return False state[node] GRAY for neighbor in graph[node]: if dfs(neighbor): return True state[node] BLACK return False for node in graph: if state[node] WHITE: if dfs(node): return True return False這套實(shí)現(xiàn)的復(fù)雜度是O(VE)空間復(fù)雜度是O(V)因?yàn)橐~外存狀態(tài)。在節(jié)點(diǎn)數(shù)量很大的時(shí)候遞歸深度可能不夠用需要改成顯式棧。我自己在某項(xiàng)目里處理過(guò)幾萬(wàn)個(gè)節(jié)點(diǎn)的配置依賴圖Python默認(rèn)遞歸深度根本扛不住后來(lái)改成了迭代式DFS。3.2 Kahn算法依賴入度為0的節(jié)點(diǎn)不斷剝離如果要判有向圖是否有環(huán)還有一條更“工程化”的路拓?fù)渑判?。Kahn算法的思路特別務(wù)實(shí)一個(gè)無(wú)環(huán)有向圖一定能找到一個(gè)入度為0的節(jié)點(diǎn)把它拿掉之后剩下的圖仍然是無(wú)環(huán)的于是可以持續(xù)剝離直到所有節(jié)點(diǎn)都被處理。反過(guò)來(lái)如果存在環(huán)環(huán)內(nèi)所有節(jié)點(diǎn)的入度永遠(yuǎn)至少為1永遠(yuǎn)無(wú)法被剝離所以最終會(huì)剩下節(jié)點(diǎn)處理不完。算法步驟非常直接統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的入度。把所有入度為0的節(jié)點(diǎn)放進(jìn)隊(duì)列。依次彈出隊(duì)列節(jié)點(diǎn)把它的所有出邊去掉對(duì)應(yīng)鄰居入度減一。如果鄰居入度變?yōu)?繼續(xù)入隊(duì)。處理完隊(duì)列后檢查已處理節(jié)點(diǎn)數(shù)量如果小于總節(jié)點(diǎn)數(shù)說(shuō)明有環(huán)。Kahn算法的優(yōu)勢(shì)在于它不只是告訴你有沒(méi)有環(huán)還會(huì)順帶給你一個(gè)合法的拓?fù)湫蛄?。這在依賴解析、構(gòu)建順序、任務(wù)編排這類場(chǎng)景里特別有意義——你不但要知道依賴關(guān)系對(duì)不對(duì)還需要一個(gè)可執(zhí)行順序。如果發(fā)現(xiàn)有環(huán)剩下的未處理節(jié)點(diǎn)集合往往就近似環(huán)的成員能幫你縮小排查范圍。from collections import deque def has_cycle_kahn(graph): indegree {node: 0 for node in graph} for node in graph: for neighbor in graph[node]: indegree[neighbor] indegree.get(neighbor, 0) 1 queue deque([node for node in graph if indegree[node] 0]) visited_count 0 while queue: node queue.popleft() visited_count 1 for neighbor in graph[node]: indegree[neighbor] - 1 if indegree[neighbor] 0: queue.append(neighbor) return visited_count ! len(graph)細(xì)心的人會(huì)問(wèn)那如果我用DFS三色標(biāo)記已經(jīng)能判環(huán)了為什么還要學(xué)Kahn?因?yàn)閮烧叩男畔⒘坑胁顒e。DFS三色標(biāo)記更擅長(zhǎng)“快速回答是或否”Kahn更擅長(zhǎng)“告訴你可以怎么安排順序”。在一個(gè)超大依賴圖的場(chǎng)景里二者往往配合使用先用Kahn做拓?fù)渑判蚺挪粍?dòng)了再用DFS找出具體的環(huán)成員。3.3 兩種方法該選誰(shuí)取決于你要的答案形態(tài)我自己的選擇標(biāo)準(zhǔn)大概是這樣的需求場(chǎng)景推薦方案原因只需要判斷有沒(méi)有環(huán)DFS三色標(biāo)記代碼簡(jiǎn)單遞歸或迭代都能實(shí)現(xiàn)遍歷過(guò)程中能順便記錄路徑需要輸出完整環(huán)路徑DFS三色標(biāo)記路徑棧遞歸過(guò)程中能記錄當(dāng)前鏈路遇到灰節(jié)點(diǎn)時(shí)鏈路就是環(huán)需要合法的處理順序Kahn拓?fù)渑判蛑苯赢a(chǎn)出拓?fù)湫蜻€能識(shí)別哪些節(jié)點(diǎn)像環(huán)成員圖特別大遞歸不好寫Kahn或迭代式DFS避免系統(tǒng)棧溢出還能靈活控制內(nèi)存注意這里的“圖特別大”要看實(shí)際規(guī)模。幾十萬(wàn)節(jié)點(diǎn)的圖DFS三色標(biāo)記依然很快但千萬(wàn)級(jí)以上的圖Kahn因?yàn)橛昧岁?duì)列可以用增量方式處理配合外部存儲(chǔ)做分批加載工程上更好落地。4. 無(wú)向圖判環(huán)并查集這個(gè)被低估的思路4.1 并查集與“邊兩端已連通 → 有環(huán)”的核心推理無(wú)向圖的判環(huán)很多人第一反應(yīng)還是DFS但工程上我強(qiáng)烈推薦并查集。它的核心推理只有一句話在逐步加邊的過(guò)程中如果一條邊的兩個(gè)端點(diǎn)已經(jīng)屬于同一個(gè)連通集合那這條邊加進(jìn)來(lái)必然形成一個(gè)環(huán)。為什么想象一下無(wú)向圖里的環(huán)本質(zhì)上就是一條邊把兩個(gè)本來(lái)已經(jīng)通過(guò)其他路徑連通的點(diǎn)再次連接起來(lái)。比如三個(gè)點(diǎn)A、B、C原來(lái)有A-B、B-C兩條邊這時(shí)候A和C已經(jīng)連通了如果再來(lái)一條A-C的邊那A-C和A-B-C就構(gòu)成了一個(gè)環(huán)。并查集做的事情就是維護(hù)這種“連通性”關(guān)系。實(shí)現(xiàn)上并查集有兩大優(yōu)化路徑壓縮和按秩合并。路徑壓縮讓每個(gè)節(jié)點(diǎn)直接指向根節(jié)點(diǎn)后續(xù)查找?guī)缀跏荗(1)按秩合并則保證樹的深度始終較小。兩者配合整個(gè)算法的攤還復(fù)雜度接近O(1)處理百萬(wàn)級(jí)邊也無(wú)壓力。class DSU: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): rx, ry self.find(x), self.find(y) if rx ry: return False if self.rank[rx] self.rank[ry]: self.parent[rx] ry elif self.rank[rx] self.rank[ry]: self.parent[ry] rx else: self.parent[ry] rx self.rank[rx] 1 return True def has_cycle_undirected(n, edges): dsu DSU(n) for u, v in edges: if not dsu.union(u, v): return True return False4.2 對(duì)自環(huán)、重邊、大圖壓縮的實(shí)操處理并查集雖然好用但工程上會(huì)有一堆邊界情況。我自己踩過(guò)幾個(gè)坑寫出來(lái)供大家避雷。第一個(gè)是自環(huán)。一個(gè)點(diǎn)自己指向自己在無(wú)向圖里算環(huán)。但在并查集里union(x, x)執(zhí)行時(shí)會(huì)發(fā)現(xiàn)find(parent_x) parent_x直接返回False判定有環(huán)。這個(gè)行為是正確的但如果你懶省事用鄰接矩陣或者只檢查重邊就漏了。第二個(gè)是重邊。兩條完全相同的邊比如A-B出現(xiàn)兩次第一次加上時(shí)A和B連通第二次再加時(shí)find結(jié)果相同于是判定有環(huán)。這個(gè)邏輯也沒(méi)問(wèn)題但要注意題意有些業(yè)務(wù)場(chǎng)景里“兩條相同邊”不該算環(huán)比如網(wǎng)絡(luò)拓?fù)渲袃蓚€(gè)節(jié)點(diǎn)之間有多條物理鏈路。這時(shí)候就得先對(duì)邊去重再做判環(huán)。第三個(gè)是大圖的內(nèi)存。如果節(jié)點(diǎn)是稀疏的可以用字典來(lái)存儲(chǔ)parent而不是數(shù)組。我在某項(xiàng)目里處理的是字符串ID而不是序號(hào)直接開數(shù)組就傻眼了后來(lái)改成字典版并查集代碼量差不多但靈活很多。4.3 有向圖和無(wú)向圖判環(huán)的方法對(duì)比我整理了一張對(duì)照表方便大家用到時(shí)直接查對(duì)比維度有向圖無(wú)向圖核心算法DFS三色標(biāo)記、Kahn拓?fù)渑判駾FS、并查集時(shí)間復(fù)雜度O(VE)并查集接近O(1)均攤典型場(chǎng)景依賴解析、編譯順序、死鎖檢測(cè)網(wǎng)絡(luò)連通性、最小生成樹、地圖圍欄邊界細(xì)節(jié)同一條邊方向相反也算環(huán)自環(huán)和重邊要按業(yè)務(wù)定義處理能否輸出環(huán)路徑三色標(biāo)記可以Kahn不行并查集不行需要另存邊再回溯特別強(qiáng)調(diào)一點(diǎn)不要把有向圖的DFS三色標(biāo)記直接搬到無(wú)向圖上。無(wú)向圖里沒(méi)有“方向”的概念DFS時(shí)你從一個(gè)節(jié)點(diǎn)出發(fā)遇到已訪問(wèn)過(guò)的鄰居很可能只是因?yàn)樗悄銊倎?lái)的那個(gè)節(jié)點(diǎn)也就是回邊。不做“跳過(guò)父節(jié)點(diǎn)”的處理任何一個(gè)無(wú)環(huán)的無(wú)向圖都能讓你誤報(bào)有環(huán)。5. 工程上的坑輸出環(huán)路徑、流式數(shù)據(jù)與超大數(shù)據(jù)量5.1 輸出環(huán)路徑不只是判斷“有沒(méi)有”很多業(yè)務(wù)場(chǎng)景下判環(huán)只是第一步產(chǎn)品經(jīng)理緊接著就會(huì)問(wèn)環(huán)是誰(shuí)和誰(shuí)組成的你得把環(huán)路徑完整地打印出來(lái)才能定位到具體是哪些配置寫錯(cuò)了。在有向圖里用DFS三色標(biāo)記可以順便輸出環(huán)路徑。做法是在進(jìn)入遞歸時(shí)維護(hù)一個(gè)路徑棧節(jié)點(diǎn)入棧時(shí)標(biāo)記為灰色出棧時(shí)恢復(fù)為白色或標(biāo)記為黑色。如果發(fā)現(xiàn)某個(gè)鄰居已經(jīng)是灰色那么從棧里找到該鄰居的位置從那個(gè)位置到棧頂?shù)乃泄?jié)點(diǎn)就是一條完整環(huán)路徑。這里有個(gè)容易出錯(cuò)的地方遞歸函數(shù)里路徑棧的入棧和出棧必須配對(duì)。我見過(guò)有同事在return True之前忘了把當(dāng)前節(jié)點(diǎn)彈棧導(dǎo)致輸出了一大段不相關(guān)的路徑。更穩(wěn)妥的做法是在遞歸返回后再統(tǒng)一彈棧保證每個(gè)節(jié)點(diǎn)的入棧和出棧嚴(yán)格對(duì)稱?；氐綗o(wú)向圖的并查集它本身不維護(hù)路徑信息所以如果要輸出環(huán)路徑就得在并查集之外另存一份鄰接表判到環(huán)時(shí)再用DFS或BFS把路徑挖出來(lái)。這會(huì)增加額外復(fù)雜度但如果業(yè)務(wù)確實(shí)需要也別怕先想清楚流程再動(dòng)手。5.2 在線/流式場(chǎng)景下的環(huán)檢測(cè)還有一種讓人頭疼的場(chǎng)景是數(shù)據(jù)源源不斷進(jìn)來(lái)圖是在線增長(zhǎng)的。比如用戶動(dòng)態(tài)加好友、任務(wù)動(dòng)態(tài)插入新依賴你不能每次都重建整張圖重新判環(huán)那樣大圖根本扛不住。增量判環(huán)沒(méi)有銀彈。如果是無(wú)向圖并查集天然支持在線判定加一條邊就合并一次如果union失敗就說(shuō)明剛加的這條邊產(chǎn)生了環(huán)復(fù)雜度穩(wěn)定。如果是有向圖增量判環(huán)就麻煩得多新加一條邊u→v可能產(chǎn)生環(huán)當(dāng)且僅當(dāng)v已經(jīng)可以通過(guò)某些路徑到達(dá)u也就是需要做一次從v出發(fā)的可達(dá)性查詢。這個(gè)查詢快則O(VE)慢則更糟屬于沒(méi)有特別好辦法的問(wèn)題。我的實(shí)踐經(jīng)驗(yàn)是如果實(shí)在繞不開大圖的增量回溯可以考慮折中方案——定期批量重建。既然每次查詢都做全圖DFS成本太高那就在一個(gè)批次內(nèi)只做局部DFS控制遍歷深度超出閾值則標(biāo)記為“待重查”這樣能兼顧實(shí)時(shí)性和性能。5.3 大規(guī)模圖處理的兜底策略最后聊一下數(shù)據(jù)規(guī)模非常大時(shí)的處理。圖數(shù)據(jù)放不進(jìn)內(nèi)存怎么辦兩個(gè)思路。第一個(gè)是分區(qū)判環(huán)。把圖按強(qiáng)連通分量或連通塊劃分分塊內(nèi)判環(huán)、塊間判環(huán)分開處理。注意強(qiáng)連通分量本身是環(huán)檢測(cè)的天然聚合一個(gè)強(qiáng)連通分量要么是單點(diǎn)要么包含至少一個(gè)環(huán)。所以有向圖判環(huán)也可以先縮點(diǎn)再看縮點(diǎn)后的DAG是否有環(huán)。第二個(gè)是外存判環(huán)。用數(shù)據(jù)庫(kù)或文件存儲(chǔ)圖的邊關(guān)系按批次加載到內(nèi)存做部分處理Kahn算法天然適合這種分批方式先把能處理的入度為零的節(jié)點(diǎn)連續(xù)處理掉留下來(lái)的節(jié)點(diǎn)肯定屬于某個(gè)環(huán)。每處理一批就重新統(tǒng)計(jì)一次入度雖然IO開銷大了些但能處理遠(yuǎn)超內(nèi)存的數(shù)據(jù)量。還有一個(gè)小經(jīng)驗(yàn)在超大規(guī)模圖里不要頻繁使用遞歸盡量用迭代。并不是每次都會(huì)棧溢出但幾十萬(wàn)層的遞歸在大多數(shù)運(yùn)行時(shí)環(huán)境里都不太穩(wěn)妥。交替使用隊(duì)列和棧把顯式的訪問(wèn)狀態(tài)用數(shù)組管理起來(lái)性能穩(wěn)定得多。6. 回到開頭那個(gè)真實(shí)案例我是怎么定位和修復(fù)的6.1 從日志到依賴圖的層層排查回到文章開頭提到的線上卡死問(wèn)題。我當(dāng)時(shí)第一反應(yīng)是檢查是不是代碼里有死循環(huán)人肉讀代碼沒(méi)找到明顯問(wèn)題。后來(lái)把請(qǐng)求鏈路打出來(lái)發(fā)現(xiàn)每次都經(jīng)過(guò)同樣兩個(gè)節(jié)點(diǎn)才意識(shí)到可能是組織關(guān)系配置成了環(huán)。我做了個(gè)簡(jiǎn)單的模擬把組織上下級(jí)關(guān)系抽成有向圖節(jié)點(diǎn)是組織ID邊是“上級(jí)指向”。跑了一遍Kahn算法很快確認(rèn)存在環(huán)然后用DFS三色標(biāo)記挖出了那條環(huán)路徑A→B→A。定位到具體那兩個(gè)組織后修復(fù)就很直接了——調(diào)整錯(cuò)誤配置讓鏈路變成樹狀結(jié)構(gòu)。6.2 修復(fù)后的防御入口校驗(yàn) 定期巡檢修復(fù)一次不算完重點(diǎn)是防止再次發(fā)生。我后來(lái)在配置保存接口里加了一層校驗(yàn)每次修改組織關(guān)系時(shí)先對(duì)整張圖做一次Kahn判環(huán)不通過(guò)就拒絕保存。同時(shí)在數(shù)據(jù)入庫(kù)之前用并查集和DFS雙重校驗(yàn)保證無(wú)論如何都不會(huì)出現(xiàn)環(huán)配置。這套做法上線之后同類問(wèn)題再也沒(méi)有復(fù)現(xiàn)過(guò)。從中我得到一個(gè)經(jīng)驗(yàn)環(huán)檢測(cè)這類工具最理想的位置不是等到問(wèn)題爆發(fā)再去排查而是寫在數(shù)據(jù)輸入的邊界上。寧可每次多花幾百毫秒做校驗(yàn)也別讓一條壞數(shù)據(jù)流到線上導(dǎo)致整點(diǎn)級(jí)別的故障。6.3 個(gè)人體會(huì)判環(huán)題目刷再多不如跑到真實(shí)業(yè)務(wù)里一次坦白說(shuō)Cycle Finding在算法題里屬于入門偏上的難度Floyd、三色標(biāo)記、拓?fù)渑判?、并查集每個(gè)都有對(duì)應(yīng)的模板題。但真正讓我覺得“會(huì)了”的時(shí)刻不是背下代碼而是面對(duì)一個(gè)真實(shí)故障時(shí)能在五分鐘內(nèi)判斷出該用哪一種算法、該怎么改造成生產(chǎn)級(jí)的代碼。如果讓我給一個(gè)學(xué)習(xí)路徑上的建議先把無(wú)向圖的并查集和有向圖的Kahn寫熟這兩個(gè)代碼量少、邏輯直接、面試和工程里出鏡率最高然后補(bǔ)DFS三色標(biāo)記因?yàn)樗俏ㄒ荒茼樖州敵鐾暾h(huán)路徑的方案最后再啃Floyd把它當(dāng)成一個(gè)“鏈表專屬的優(yōu)化技巧”來(lái)學(xué)。反過(guò)來(lái)學(xué)也沒(méi)問(wèn)題但別把Floyd誤當(dāng)成全圖判環(huán)的通用解法。真正處理過(guò)的圖一多你會(huì)發(fā)現(xiàn)環(huán)檢測(cè)從來(lái)不是一個(gè)孤立的算法題它是圖論思維在工程世界里的縮影。判斷出環(huán)的位置找到環(huán)的成因阻止環(huán)的產(chǎn)生這套思路比任何單段代碼都值錢。