http://www.cnblogs.com/zhengsyao/p/erlang_race_condition_in_digraph.html
雖然 Erlang 的廣告說得非常好，functional、share-nothing、消息傳遞，blah blah 的，好像用 Erlang 寫并發(fā)程序就高枕無憂了，但是由于 Erlang 信奉高度實(shí)用主義的哲學(xué)，所以 Erlang 中有各種各樣的后門，使得 Erlang 是一個(gè)不那么 pure 的 functional 語言，而且也是允許 share something 的。

比如說，ETS 就是一個(gè)大后門。ETS 本是為實(shí)現(xiàn) Mnesia 數(shù)據(jù)庫而實(shí)現(xiàn)的一個(gè)“基于哈希表的無結(jié)構(gòu)化 term 存儲(chǔ)”，但是 ETS 太好用了，能滿足高性能的字典需求，而且還可以全局訪問，完全擺脫 Erlang 設(shè)置的 share nothing、immutable variable 之類的 functional 束縛，所以很多程序會(huì)喜歡使用 ETS。

Erlang 的（為了避免錯(cuò)誤而設(shè)置的）種種約束在這些使用了這些后門的情況下也會(huì)喪失威力。這不，我在標(biāo)準(zhǔn)庫的 digraph 模塊中就發(fā)現(xiàn)了一個(gè)潛在的 bug。下面先說一下使用 ETS 造成并發(fā) bug 的模式，然后再看 digraph 中的這個(gè)潛在 bug。

Erlang 中有很多這樣的代碼：V2 = do_something(V1)，如果 V1 和 V2 是同樣類型的復(fù)雜數(shù)據(jù)結(jié)構(gòu)，根據(jù) Erlang 的語義，do_something 對 V1 只是讀操作，然后生成新的字段，最后創(chuàng)建出新的 V2 返回，V1 應(yīng)該是不動(dòng)的。這樣其他進(jìn)程也可以放心地訪問 V1，至少 V1 的狀態(tài)在系統(tǒng)中是一致的（consistent）。如果 V1 中使用了 ETS，并且 do_something 對 ETS 做操作了，那么這個(gè)函數(shù)就產(chǎn)生副作用了，以上的一致性可能就無法保證了，例如假設(shè) V1 是這樣的數(shù)據(jù)結(jié)構(gòu)：

-record(some_struct, {tab1 =  ets:tab(),
                      tab2 =  ets:tab(),
                      var1 =  integer()}).

這個(gè)數(shù)據(jù)結(jié)構(gòu)中有兩個(gè) ETS 表，說明這個(gè)數(shù)據(jù)結(jié)構(gòu)的狀態(tài)是由兩個(gè) ETS 表的狀態(tài)決定的。雖然 Erlang 運(yùn)行時(shí)能保證單個(gè) ETS 表的并發(fā)訪問，但是多個(gè)表的一致性還需要程序自己來維護(hù)，因此這個(gè)數(shù)據(jù)結(jié)構(gòu)在多進(jìn)程訪問的情況下就會(huì)出現(xiàn)競爭條件。下面我們看看 digraph 模塊中的潛在 bug。

digraph 模塊是用來表示有向圖（directed graph）的。有向圖就是在一個(gè)圖中，要考慮邊（edge）中頂點(diǎn)（vertex）的順序。有向圖的數(shù)據(jù)結(jié)構(gòu)中要保存頂點(diǎn)的集合以及邊的集合。某個(gè)頂點(diǎn)的鄰居（neighbour）指的是和這個(gè)頂點(diǎn)相連的頂點(diǎn)，由于有向圖是有方向的，所以一個(gè)頂點(diǎn)會(huì)有入鄰居（in-neighbour）和出鄰居（out-neighbour），前者指的是有邊射入當(dāng)前頂點(diǎn)的頂點(diǎn)，后者指的是當(dāng)前頂點(diǎn)有邊射出到的頂點(diǎn)。好了這是基本概念。下面我們看 digraph 模塊使用的數(shù)據(jù)結(jié)構(gòu)：

1 -record(digraph, {vtab = notable :: ets:tab(),
2                   etab = notable :: ets:tab(),
3                   ntab = notable :: ets:tab(),
4                   cyclic = true  :: boolean()}).

digraph 記錄體中連續(xù) 3 個(gè) ETS 表，看上去就有不好的事情可能發(fā)生。vtab 是頂點(diǎn)的表，etab 是邊的表，ntab 維護(hù)了鄰居的關(guān)系。digraph 模塊對 digraph 數(shù)據(jù)結(jié)構(gòu)并發(fā)訪問做了控制，允許設(shè)置兩種模式：protected 和 private。前者只允許 digraph 的所有者進(jìn)程修改，但是其他進(jìn)程都可以訪問；后者只允許所有者進(jìn)程修改和訪問，其他進(jìn)程不能訪問（其實(shí)就是設(shè)置了 ETS 表的訪問權(quán)限）。

下面創(chuàng)建一個(gè)簡單的有向圖，創(chuàng)建幾個(gè)節(jié)點(diǎn)和邊：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

5> DG = digraph:new().        {digraph,28692,32789,36886,true} 6> digraph:add_vertex(DG, v1). v1 省略... 11> digraph:add_edge(DG, v1, v2). ['$e'|0] 省略... 16> digraph:in_neighbours(DG, v1). [] 17> digraph:in_neighbours(DG, v2). [v1] 省略... 21> digraph:out_neighbours(DG, v1). [v5,v4,v3,v2]

命令 5> 創(chuàng)建了新的 digraph，輸出的 DG 值中包含了幾個(gè) ETS id，然后添加頂點(diǎn)和邊。v1 頂點(diǎn)的入鄰居沒有，出鄰居包括 v2、v3、v4 和 v5。下面展示了這幾個(gè) ETS 表中的項(xiàng)：

vertices 表中是頂點(diǎn)，edges 表中是邊，neighbour 表中保存了 in 和 out 的關(guān)系。其實(shí) neighbour 表中的內(nèi)容可以從 edges 表中推導(dǎo)出來，但是這個(gè)表在這里可以做一個(gè)緩存作用，迅速查出一個(gè)節(jié)點(diǎn)的鄰居關(guān)系，而不用掃描 edges 表。

從這里我們應(yīng)該可以嗅到 bug 的味道了：edges 表和 neighbour 表有映射關(guān)系，如果修改一個(gè)表，那么另一個(gè)表也需要修改，否則就會(huì)出現(xiàn)數(shù)據(jù)不一致（inconsistent）的情況。我們來看插入邊的代碼：

 1 add_edge(G, V1, V2) ->
 2     do_add_edge({new_edge_id(G), V1, V2, []}, G).
 3 
 4 do_add_edge({E, V1, V2, Label}, G) ->
 5     case ets:member(G#digraph.vtab, V1) of
 6         false -> {error, {bad_vertex, V1}};
 7         true  ->
 8             case ets:member(G#digraph.vtab, V2) of
 9                 false -> {error, {bad_vertex, V2}};
10                 true ->
11                     case other_edge_exists(G, E, V1, V2) of
12                         true -> {error, {bad_edge, [V1, V2]}};
13                         false when G#digraph.cyclic =:= false ->
14                             acyclic_add_edge(E, V1, V2, Label, G);
15                         false ->
16                             do_insert_edge(E, V1, V2, Label, G)
17                     end
18             end
19     end.
20 
21 do_insert_edge(E, V1, V2, Label, #digraph{ntab=NT, etab=ET}) ->
22     ets:insert(NT, [{{out, V1}, E}, {{in, V2}, E}]),
23     ets:insert(ET, {E, V1, V2, Label}),
24     E.

diagraph:add_edge/3 是發(fā)布的接口，do_add_edge/2 做一些頂點(diǎn)是否存在的判斷，檢查是否能添加邊，最后 do_insert_edge/5 真正負(fù)責(zé)把邊插入相應(yīng)的 ETS 表。可以看出，第 22 行插入鄰居表，第 23 行插入邊表。

這里就可能出現(xiàn)問題了：根據(jù) Erlang 調(diào)度器的規(guī)則，第 22 行執(zhí)行完成之后，由于 ets:insert/2 是一個(gè) BIF 調(diào)用，因此進(jìn)程有可能會(huì)被搶占。如果此時(shí)進(jìn)程被搶占，那么 digraph 就處于一個(gè) inconsistent 狀態(tài)了。如下圖所示：

假設(shè)這個(gè) digraph 是 protected，那么其他進(jìn)程是可以訪問的。如果其他進(jìn)程需要 joint 訪問這兩個(gè)表的話，有可能就會(huì)出問題。果然，訪問鄰居的接口 digraph:in_neighbours/2 就是這樣一個(gè)函數(shù)，下面來看代碼：

 1 in_neighbours(G, V) ->
 2     ET = G#digraph.etab,
 3     NT = G#digraph.ntab,
 4     collect_elems(ets:lookup(NT, {in, V}), ET, 2).
 5 
 6 collect_elems(Keys, Table, Index) ->
 7     collect_elems(Keys, Table, Index, []).
 8 
 9 collect_elems([{_,Key}|Keys], Table, Index, Acc) ->
10     collect_elems(Keys, Table, Index,
11           [ets:lookup_element(Table, Key, Index)|Acc]);
12 collect_elems([], _, _, Acc) -> Acc.

in_neighbours/2 先提取出兩個(gè)表 ET 和 NT，分別是邊表和鄰居表，然后調(diào)用 collect_elems/3，相當(dāng)于做一個(gè) joint 查詢。第 4 行首先查詢鄰居表 ets:lookup(NT, {in, V})，也就是在鄰居表中查詢節(jié)點(diǎn) V 入邊。查到邊之后，collect_elems/4 的第 11 行再從邊表中去查這條邊的頂點(diǎn)。那么如果出現(xiàn)上圖中的情況，在添加邊的時(shí)候在鄰居表中插入完成之后進(jìn)程被切出，那么 edges 表中的第 4 行還不存在，而 neighbours 表中圈出的那兩行是存在的。那么 collect_elems/4 執(zhí)行到 11 行的 ets:lookup_element 就會(huì)拋出異常。

以上就是在標(biāo)準(zhǔn)庫的 digraph 模塊中發(fā)生競爭條件的一個(gè)例子。對于這個(gè)具體的問題來說，把 do_insert_edge/5 中那兩行 insert 換一下位置就好了，先插入邊表，再插入鄰居表，畢竟后面的表可以由前面的表推導(dǎo)出來，所以在訪問的時(shí)候先訪問后面的表在訪問前面的表不會(huì)出現(xiàn)查不到的情況，盡管本質(zhì)上看數(shù)據(jù)還是有可能不一致。所以雖然可以修掉這個(gè) bug，但是這種風(fēng)格還是有風(fēng)險(xiǎn)的，比如說有 3 個(gè)或更多的表需要一致的情況。其實(shí) digraph 模塊這種風(fēng)格：創(chuàng)建一個(gè)數(shù)據(jù)結(jié)構(gòu)，得到一個(gè)句柄，然后大家都可以修改和訪問的風(fēng)格不是非常“Erlangic”。應(yīng)該是像這樣的設(shè)計(jì)：DG = digraph:new(), DG1 = digraph:add_vertex(DG, v1)... 。也就是說，每次修改之后就產(chǎn)生一個(gè)新的變量。當(dāng)然，這樣在內(nèi)部就不能用 ETS 來實(shí)現(xiàn)了，因?yàn)槊看涡薷牡氖?ETS 表，而 DG 變量綁定的 #digraph{} 里面的表 id 字段的值又沒變，所以 DG 和 DG1 的值實(shí)際還是一樣的，只是表示的意義不同了，可怕的副作用啊。

至于這是不是 bug，可能有人會(huì)爭論了：至少 ETS 查詢會(huì)拋 badarg 啊，然后這個(gè)異常會(huì)傳播到 in_neighours/2 的調(diào)用者啊，所以在調(diào)用的時(shí)候要捕捉異常啊。可是 digraph 文檔又沒說會(huì)拋異常，看源碼的時(shí)候，也沒有語法結(jié)構(gòu)注明一個(gè)函數(shù)會(huì)拋什么異常，那我怎么知道什么時(shí)候要捉異常呢？就算我養(yǎng)成調(diào)什么函數(shù)都捉異常的習(xí)慣，可是我捉到了異常又怎么知道是怎么回事呢？特別是這種并發(fā)相關(guān)的問題，下次復(fù)現(xiàn)的幾率又像中獎(jiǎng)一樣。所以 Erlang 這門語言真是讓人又愛又恨啊。

不過不爭論語言本身了，言歸正傳，本文的結(jié)論就是：在使用 ETS 的時(shí)候要注意 ETS 是全局共享的內(nèi)存，要注意數(shù)據(jù)一致性的問題。

erlang 參數(shù)傳遞時(shí)是賦值or引用？
請教一個(gè)基礎(chǔ)問題，erlang 參數(shù)傳遞時(shí)是賦值or引用？
找不到方法測試。
求教了。

答：
erlang 中怎么會(huì)有引用這種說法，變量都是拷貝過去的。

問：
無法實(shí)現(xiàn)引用，是么？
我在寫的東西要傳一個(gè)大狀態(tài)。
所以疑惑了一下。

答：
erlang 所有的變量都只能在函數(shù)中傳遞，沒有全局變量這一說。
你傳遞狀態(tài)是通過改變函數(shù)參數(shù)實(shí)現(xiàn)的


問：
我不是很清楚當(dāng)參數(shù)很大時(shí)，進(jìn)行拷貝的效率如何.
能給我解惑一下么？

答
越大效率越低
另外是原子atom ，erlang 的垃圾回收機(jī)制是不回收的，除非運(yùn)行結(jié)束。

問：
試想gen_server中call(_From,Status,Args)被調(diào)用時(shí)，Status就被改變了。這是不是意味著這里的Status是被引用傳遞進(jìn)去的呢
我有闡述清楚么？


答：
不會(huì)
Status 
的值
不會(huì)被函數(shù)改變
函數(shù)得到的只是一個(gè)新的參數(shù)邦定
綁定

簡單的說
erlang 的參數(shù)都是拷貝方式的


廣州-手  14:54:35
對，這就是內(nèi)存共享。

返源
不見得多少，你的每一個(gè)函數(shù)結(jié)束就會(huì)回收當(dāng)中的內(nèi)存。
不存在引用

廣州-手   14:53:52
沒有引用的參數(shù)傳遞 不知會(huì)吃掉我程序的性能

上海-PHP-返源   14:54:34
如果有引用就有副作用
就沒辦法獨(dú)自運(yùn)行

廣州-手   14:54:10
不知會(huì)吃掉多少性能。
但是我的status是一條很長的記錄。

廣州-手 )  14:55:23
稍稍有點(diǎn)擔(dān)憂。暫時(shí)還不能測試。
廣州-手   14:56:23
你剛說的參數(shù) 愈大效率越低，是怎么回事？
上海-PHP-返源   14:57:02
記錄是單獨(dú)存儲(chǔ)的
不過你傳遞的時(shí)候還是拷貝

廣州-手   14:56:47
恩。


上海-PHP-返源    14:57:40
但這里具體內(nèi)部實(shí)現(xiàn)有很多方案
譬如你不寫，只是取，我就可以共用內(nèi)存。

廣州-手    14:58:03
怎么實(shí)現(xiàn)，求指導(dǎo)。

上海-PHP-返源    14:58:56
這個(gè)跟你實(shí)現(xiàn)沒關(guān)系哈，我說的erlang 內(nèi)部。
總之你減少參數(shù)的大小
有利提高速度

廣州-手   14:58:57
這個(gè)意思是erlang的自動(dòng)優(yōu)化么？

上海-PHP-返源    14:59:40