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

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

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

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

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

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

digraph 模塊是用來表示有向圖（directed graph）的。有向圖就是在一個圖中，要考慮邊（edge）中頂點（vertex）的順序。有向圖的數(shù)據(jù)結(jié)構(gòu)中要保存頂點的集合以及邊的集合。某個頂點的鄰居（neighbour）指的是和這個頂點相連的頂點，由于有向圖是有方向的，所以一個頂點會有入鄰居（in-neighbour）和出鄰居（out-neighbour），前者指的是有邊射入當前頂點的頂點，后者指的是當前頂點有邊射出到的頂點。好了這是基本概念。下面我們看 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 個 ETS 表，看上去就有不好的事情可能發(fā)生。vtab 是頂點的表，etab 是邊的表，ntab 維護了鄰居的關(guān)系。digraph 模塊對 digraph 數(shù)據(jù)結(jié)構(gòu)并發(fā)訪問做了控制，允許設(shè)置兩種模式：protected 和 private。前者只允許 digraph 的所有者進程修改，但是其他進程都可以訪問；后者只允許所有者進程修改和訪問，其他進程不能訪問（其實就是設(shè)置了 ETS 表的訪問權(quán)限）。

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

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 值中包含了幾個 ETS id，然后添加頂點和邊。v1 頂點的入鄰居沒有，出鄰居包括 v2、v3、v4 和 v5。下面展示了這幾個 ETS 表中的項：

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

從這里我們應該可以嗅到 bug 的味道了：edges 表和 neighbour 表有映射關(guān)系，如果修改一個表，那么另一個表也需要修改，否則就會出現(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 做一些頂點是否存在的判斷，檢查是否能添加邊，最后 do_insert_edge/5 真正負責把邊插入相應的 ETS 表。可以看出，第 22 行插入鄰居表，第 23 行插入邊表。

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

假設(shè)這個 digraph 是 protected，那么其他進程是可以訪問的。如果其他進程需要 joint 訪問這兩個表的話，有可能就會出問題。果然，訪問鄰居的接口 digraph:in_neighbours/2 就是這樣一個函數(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 先提取出兩個表 ET 和 NT，分別是邊表和鄰居表，然后調(diào)用 collect_elems/3，相當于做一個 joint 查詢。第 4 行首先查詢鄰居表 ets:lookup(NT, {in, V})，也就是在鄰居表中查詢節(jié)點 V 入邊。查到邊之后，collect_elems/4 的第 11 行再從邊表中去查這條邊的頂點。那么如果出現(xiàn)上圖中的情況，在添加邊的時候在鄰居表中插入完成之后進程被切出，那么 edges 表中的第 4 行還不存在，而 neighbours 表中圈出的那兩行是存在的。那么 collect_elems/4 執(zhí)行到 11 行的 ets:lookup_element 就會拋出異常。

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

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

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

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

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

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

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


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

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

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


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

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


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

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

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

上海-PHP-返源   14:54:34
如果有引用就有副作用
就沒辦法獨自運行

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

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

廣州-手   14:56:47
恩。


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

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

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

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

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