# 第9章 雜項
| 翻譯: | 連城 |
|-----|-----|
本章包含:
- 末尾調用優化——一種令尾遞歸程序得以在常數空間內執行的優化技術。
- 引用——提供確保在所有節點上都唯一的名稱。
- 代碼替換——在嵌入式實時系統中必須做到代碼的**運行時**替換,即是說,系統不能停機。
- 端口——提供和外部世界通訊的機制。
- 二進制數據——用于操作無類型內存區域的內建數據類型。
- 進程字典——用于破壞性地存取進程全局數據。[[*]](#)
- 網絡內核——網絡內核用于協調分布式Erlang系統中的所有網絡操作。
- 散列——一種將項式映射到唯一的整數用以實現高效的表查詢操作的方法。
- 效率——我們將討論如何編寫高效的Erlang程序。
| [[*]](#) | 譯者注:此處的“破壞性”指的是進程字典可被修改,從而破壞了Erlang函數式語法的變量不變性。 |
|-----|-----|
### 末尾調用優化
Erlang支持**末尾調用優化**,從而使得函數得以在固定大小的空間內執行。存儲持久數據的主要手法是將之存儲于由服務器進程操縱的結構中(典型實例參見第??節)。為了令這種手法得以正常工作,服務器必須利用末尾調用優化。
如果不這么做,服務器最終將會耗盡內存空間從而無法正常工作。
### 尾遞歸
我們通過展示同一個函數的兩種不同風格的寫法來引入**尾遞歸**的概念,其中一種寫法是尾遞歸的形式。考察定義如下的length函數:
~~~
length([_|T]) ->
1 + length(T);
length([]) ->
0.
~~~
我們不妨對legth([a,b,c])求值。length的第一個子句將問題歸結為對1+length([b,c])求值。不幸的是,+運算無法**立即**執行,而是得**延遲**到length([b,c])求值完畢為止。系統必須**記住**這個+運算并在后續的某個階段(此時已知length([b,c])的值)系統**回溯**至該執行這個+運算時再實際執行運算。
**未決**的運算被保存于局部數據區。這塊區域的包含至少K*N個位置(其中K是一個常數,代表對length進行一次全新求值所需空間的大小,N是未決的運算數量)。
現在我們再寫一個等價的求列表長度的函數,其中使用了一個累加器(參見第??節)。該函數僅占用固定大小的空間(為避免混淆,我們將之記為length1):
~~~
length1(L) ->
length1(L, 0).
length1([_|T], N) ->
length1(T, 1 + N);
length1([], N) ->
N.
~~~
要求length1([a,b,c]),我們首先求length1([a,b,c],0)。再歸結為length1([b,c],1+0)。現在+運算可以**立即**執行了(因為所有**參數**都已知)。于是,計算length1([a,b,c])的函數求值過程為:
~~~
length1([a, b, c])
length1([a, b, c], 0)
length1([b, c], 1 + 0)
length1([b, c], 1)
length1([c], 1 + 1)
length1([c], 2)
length1([], 1 + 2)
length1([], 3)
3
~~~
**尾遞歸函數**就是在遞歸調用前不累計任何未決運算的函數。如果函數子句中函數體的最后一個表達式是對自身的調用或者是個常數,那么它就是尾遞歸子句。如果一個函數的所有子句都是尾遞歸子句,那么它就是一個尾遞歸函數。
例如:
~~~
rev(X) -> rev(X, []).
rev([], X) -> X;
rev([H|T], X) -> rev(T, [H|T]).
~~~
該函數就是尾遞歸函數,但:
~~~
append([], X) -> X;
append([H|T], X) -> [H | append(T,X)].
~~~
就不是尾遞歸函數,因為第二個子句的最后一個表達式([H|append(T,X)]中的|)既不是對append的調用,也不是常數。
### 末尾調用優化
尾遞歸是更泛化的**末尾調用優化**(Last Call Optimisation,LCO)的一個特例。末尾調用優化可應用于任何函數子句最后一個表達式為函數調用的情況。
例如:
~~~
g(X) ->
...
h(X).
h(X) ->
...
i(X).
i(X) ->
g(X).
~~~
上述代碼定義了一組三個相互遞歸的函數。LCO使得對g(X)的求值可以在常數空間內完成。
仔細翻閱本書的所有服務程序示例代碼會發現,這些程序都可以在常數空間[[1]](#)內執行。
### 引用
**引用**是全局唯一的對象。BIF make_ref()返回全局唯一的對象,該對象與系統中以及所有其他(可能存在的)運行著的節點中的所有對象都不相等。針對引用的唯一運算就是相等比較。
例如,我們可以在客戶端—服務器模型中采用如下的接口函數:
~~~
request(Server, Req) ->
Server ! {R = make_ref(), self(), Req},
receive
{Server, R, Reply} ->
Reply
end.
~~~
request(Server,Req)向名稱為Server的服務器發送請求Req;請求中包含一個唯一引用R。在接收服務器返回的應答時會校驗是否存在該唯一引用R。與服務器端的這種“端對端”的通訊方法可用于確認請求是否已被處理。
### 代碼替換
在嵌入式實時系統中,我們希望在不停機的情況下進行代碼升級。比如我們希望在不影響服務的情況下修復某臺大型交換機中的軟件錯誤。
在運營過程中進行代碼替換是“軟”實時控制系統的普遍需求,這些系統往往運營時間很長,代碼體積也很大。而在特殊處理器上運行或燒錄在ROM里的硬實時系統則往往沒有這種需求。
### 代碼替換實例
考察程序9.1。
我們首先編譯并加載code_replace的代碼。然后我們啟動程序,并向創建出來的進程發送消息hello、global和process。
程序9.1
~~~
-module(code_replace).
-export([test/0, loop/1]).
test() ->
register(global, spawn(code_replace, loop, [0])).
loop(N) ->
receive
X ->
io:format('N = ~w Vsn A received ~w~n', [N, X])
end,
code_replace:loop(N+1).
~~~
最后我們再次編輯程序,將版本號從A改為B,重新編譯、加載程序,并向進程發送消息hello。
會話結果如下:
~~~
%%% start by compiling and loading the code
%%% (this is done by c:c)
> c:c(code_replace).
...
> code_replace:test().
true
> global ! hello.
N = 0 Vsn A received hello
hello
> global ! global.
N = 1 Vsn A received global
global
> global ! process.
N = 2 Vsn A received process
%%% edit the file code_replace.erl
%%% recompile and load
> c:c(code_replace).
....
> global ! hello.
N = 3 Vsn B received hello
~~~
這里我們看到,在loop/1的執行過程中,雖然我們重新編譯、加載了它的代碼,但作為loop/1的參數的局部變量N的值仍被保留了下來。
注意服務器循環的代碼是以如下形式編寫的:
~~~
-module(xyz).
loop(Arg1, ..., ArgN) ->
receive
...
end,
xyz:loop(NewArg1, ..., NewArgN).
~~~
這與下面這樣的寫法有細微的差異:
~~~
-module(xyz).
loop(Arg1, ..., ArgN) ->
receive
...
end,
loop(NewArg1, ..., NewArgN).
~~~
第一種情況中調用xyz:loop(...)意味著總是使用模塊xyz中**最新**的loop版本。第二種情況中(不顯式指定模塊名)則只調用**當前執行模塊**中的loop版本。
顯式使用模塊限定名(module:func)使得module:func**動態**鏈接至運行時代碼。對于使用完整模塊限定名的調用,系統**每次**都會使用最新版本的可用代碼進行函數求值。模塊中本地函數的地址解析在編譯期完成——它們是**靜態**的,不能在運行時改變。
上述會話示例中c:c(File)編譯并加載File中的代碼。在第??節對此有詳細討論。
### 端口
端口提供了與外部世界通訊的基本機制。用Erlang編寫的應用程序往往需要與Erlang系統之外的對象交互。還有一些現存的軟件包,例如窗口系統、數據庫系統,或是使用C、Modula2等其他語言的程序,在使用它們構建復雜系統時,也往往需要給它們提供Erlang接口。
從程序員的視角來看,我們希望能夠以處理普通Erlang程序的方式來處理Erlang系統外的所有活動。為了創造這樣的效果,我們需要將Erlang系統外的對象偽裝成普通的Erlang進程。**端口**(Port),一種為Erlang系統和外部世界提供面向字節的通訊信道的抽象設施,就是為此而設計的。
執行open_port(PortName,PortSettings)可以創建一個端口,其行為與進程類似。執行open_port的進程稱為該端口的**連接進程**。需要發送給端口的消息都應發送至連接進程。外部對象可以通過向與之關聯的端口寫入字節序列的方式向Erlang系統發送消息,端口將給連接進程發送一條包含該字節序列的消息。
系統中的任意進程都可以與一個端口建立鏈接,端口和Erlang進程間的EXIT信號導致的行為與普通進程的情況完全一致。端口只理解**三種**消息:
~~~
Port ! {PidC, {command, Data}}
Port ! {PidC, {connect, Data}}
Port ! {PidC, close}
~~~
PidC**必須**是一個連接進程的Pid。這些消息的含義如下:
{command,Data}
> 將Data描述的字節序列發送給外部對象。Data可以是單個二進制對象,也可以是一個元素為0..255范圍內的整數的非扁平列表[[2]](#)。沒有響應。
close
> 關閉端口。端口將向連接進程回復一條{Port,closed}消息。
{connect,Pid1}
> 將端口的連接進程換位Pid1。端口將向先前的連接進程發送一條{Port,connected}消息。
此外,連接進程還可以通過以下方式接收數據消息:
~~~
receive
{Port, {data, Data}} ->
... an external object has sent data to Erlang ...
...
end
~~~
在這一節中,我們將描述兩個使用端口的程序:第一個是在Erlang工作空間**內部**的Erlang進程;第二個是在Erlang**外部**執行的C程序。
### 打開端口
打開端口時可以進行多種設置。BIF open_port(PortName,PortSettings可用于打開端口。PortName可以是:
{spawn,Command}
> 啟動名為Command的**外部**程序或驅動。Erlang驅動在附錄E中有所描述。若沒有找到名為Command的驅動,則將在Erlang工作空間的外部運行名為Command的外部程序。
Atom
> Atom將被認作是外部資源的名稱。這樣將在Erlang系統和由該原子式命名的資源之間建立一條透明的連接。連接的行為取決于資源的類型。如果Atom表示一個文件,則一條包含文件全部內容的消息會被發送給Erlang系統;向該端口寫入發送消息便可向文件寫入數據。
{fd,In,Out}
> 令Erlang進程得以訪問任意由Erlang打開的文件描述符。文件描述符In可作為標準輸入而Out可作為標準輸出。該功能很少使用:只有Erlang操作系統的幾種服務(shell和user)需要使用。注意該功能與僅限于UNIX系統。
PortSettings是端口設置的列表。有效的設置有:
{packet,N}
> 消息的長度將以大端字節序附在消息內容之前的N個字節內。N的有效取值為1、2或4。
stream
> 輸出的消息不附帶消息長度──Erlang進程和外部對象間必須使用某種私有協議。
use_stdio
> 僅對{spawn,Command}形式的端口有效。令產生的(UNIX)進程使用標準輸入輸出(即文件標識符0和1)與Erlang通訊。
nouse_stdio
> 與上述相反。使用文件描述符3、4與Erlang通訊。
in
> 端口僅用于輸入。
out
> 端口僅用于輸出。
binary
> 端口為二進制端口(后續將詳述)。
eof
> 到達文件末尾后端口不會關閉并發送'EXIT'信號,而是保持打開狀態并向端口的連接進程發送一條{Port,eof}消息,之后連接進程仍可向端口輸出數據。
除了{spawn,Command}類型的端口默認使用use_stdio外,*所有*類型的端口默認都使用stream。
### Erlang進程眼中的端口
程序9.2定義了一個簡單的Erlang進程,該進程打開一個端口并向該端口發送一串消息。與端口相連的外部對象會處理并回復這些消息。一段時間之后進程將關閉端口。
程序9.2
~~~
-module(demo_server).
-export([start/0]).
start() ->
Port = open_port({spawn, demo_server}, [{packet, 2}]),
Port ! {self(), {command, [1,2,3,4,5]}},
Port ! {self(), {command}, [10,1,2,3,4,5]},
Port ! {self(), {command, "echo"}},
Port ! {self(), {command, "abc"}},
read_replies(Port).
read_replies(Port) ->
receive
{Port, Any} ->
io:format('erlang received from port:~w~n', [Any]),
read_replies(Port)
after 2000 ->
Port ! {self(), close},
receive
{Port, closed} ->
true
end
end.
~~~
程序9.2中的open_port(PortName,PortSettings啟動了一個**外部**程序。demo_server是即將運行的程序的名字。
表達式Port!{self(),{command,[1,2,3,4,5]}}向外部程序發送了五個字節(值為1、2、3、4、5)。
為了讓事情有意思一點,我們令外部程序具備一下功能:
- 若程序收到字符串“echo”,則它會向Erlang回復“ohce”。
- 若程序收到的數據塊的第一個字節是10,則它會將除第一個字節以外的所有字節翻倍后返回。
- 忽略其他數據。
運行該程序后我們得到以下結果:
~~~
> demo_server:start().
erlang received from port:{data,[10,2,4,6,8,10]}
erlang received from port:{data,[111,104,99,101]}
true
~~~
### 外部進程眼中的端口
程序9.3
<table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95</pre><pre>/* demo_server.c */
#include <stdio.h>
#include <string.h>
/* Message data are all unsigned bytes */
typedef unsigned char byte;
main(argc, argv)
int argc;
char **argv;
{
int len;
int i;
char *progname;
byte buf[1000];
progname = argv[0]; /* Save start name of program */
fprintf(stderr, "demo_server in C Starting \n");
while ((len = read_cmd(buf)) > 0){
if(strncmp(buf, "echo", 4) == 0)
write_cmd("ohce", 4);
else if(buf[0] == 10){
for(i=1; i < len ; i++)
buf[i] = 2 * buf[i];
write_cmd(buf, len);
}
}
}
/* Read the 2 length bytes (MSB first), then the data. */
read_cmd(buf)
byte *buf;
{
int len;
if (read_exact(buf, 2) != 2)
return(-1);
len = (buf[0] << 8) | buf[1];
return read_exact(buf, len);
}
/* Pack the 2 bytes length (MSB first) and send it */
write_cmd(buf, len)
byte *buf;
int len;
{
byte str[2];
put_int16(len, str);
if (write_exact(str, 2) != 2)
return(-1);
return write_exact(buf, len);
}
/* [read|write]_exact are used since they may return
* BEFORE all bytes have been transmitted
*/
read_exact(buf, len)
byte *buf;
int len;
{
int i, got = 0;
do {
if ((i = read(0, buf+got, len-got)) <= 0)
return (i);
got += i;
} while (got < len);
return (len);
}
write_exact(buf, len)
byte *buf;
int len;
{
int i, wrote = 0;
do {
if ((i = write(1, buf+wrote, len-wrote)) <= 0)
return (i);
wrote += i;
} while (wrote < len);
return (len);
}
put_int16(i, s)
byte *s;
{
*s = (i >> 8) & 0xff;
s[1] = i & 0xff;
}
</pre></div></td></tr></table>
程序9.3通過表達式len=read_cmd(buf)讀取發送至Erlang端口的字節序列,并用write_cmd(buf,len)將數據發回Erlang。
文件描述符0用于從Erlang讀取數據,而文件描述符1用于向Erlang寫入數據。各個C函數的功能如下:
read_cmd(buf)
> 從Erlang讀取一條命令。
write_cmd(buf,len)
> 向Erlang寫入一個長度為len的緩沖區。
read_exact(buf,len)
> 讀取len個字節。
write_exact(buf,len)
> 寫入len個字節。
put_int16(i,s)
> 將一個16位整數打包為兩個字節。
函數read_cmd和write_cmd假設外部服務和Erlang間的協議由一個指明數據包長度的雙字節包頭和緊隨的數據構成。如圖9.1所示。

圖9.1 端口通訊
之所以使用這種協議(雙字節包頭加數據)是由于端口是以如下方式打開的:
~~~
open_port({spawn, demo_server}, [{packet, 2}])
~~~
### 二進制類型
二進制類型是一種用于存儲無類型內存區域的數據類型。若open_port/2的最后一個參數Settings列表中包含原子式binary,則打開的端口便是二進制端口。來自二進制端口的消息都是二進制類型的數據。
為了說明二進制端口和普通端口的區別,我們用“雙字節包頭加數據”協議從外部進程向Erlang發送字符串"hello"。外部程序將輸出如下字節序列:
~~~
0 5 104 101 108 108 111
~~~
若與Erlang進程相連的端口是普通端口,則會向向進程發送消息{Port,{data,[104,101,108,108,111]}}。若是二進制端口,消息則是{Port,{data,Bin}},其中Bin是長度為5的二進制數據對象,內容即為消息中的字節數據。注意,在這兩種情況下,向端口發送數據的外部進程沒有區別。
令端口發送二進制對象而非列表的好處在于,相對于長列表,構造和發送二進制數據的速度要快很多。
下列BIF可用于二進制操作:
term_to_binary(T)
> 將項式T轉為二進制。得到的二進制數據對象為該項式的**外部項式格式**表示。
binary_to_term(Bin)
> 與term_to_binary/1相反。
binary_to_list(Bin)
> 將二進制對象Bin轉為證書列表。
binary_to_list(Bin,Start,Stop)
> 將二進制對象從Start到Stop的部分轉為整數列表。二進制對象的位置下標從1開始計算。
list_to_binary(Charlist)
> 將Charlist轉為二進制數據對象。與term_to_binary(Charlist) 不同,該BIF構造的是一個包含Charlist所包含的字節序列的二進制對象,而前者是針對**項式**Charlist構造一個外部項式格式的二進制對象。
split_binary(Bin,Pos)
> > 將Bin從Pos處切分為兩個新的二進制對象。得到的是包含兩個新二進制對象的元組。例如:
> >
~~~
1> B = list_to_binary("0123456789").
#Bin
2> size(B).
10
3> {B1,B2} = split_binary(B,3).
{#Bin,#Bin}
4> size(B1).
3
5> size(B2).
7
~~~
concat_binary(ListOfBinaries) 構造一個串接二進制對象列表ListOfBinaries中的所有二進制對象的新二進制對象。 另外,保護式binary(X)在X為二進制數據對象時返回成功。二進制對象主要用于網絡中的代碼加載,但也可用于那些需要處理大量音視頻數據等原始數據的應用。通常可以高效地通過端口輸入大量二進制數據,完成數據處理后,再輸出到另一個或原先的端口。
進程字典 每個進程都擁有一個字典。通過下列BIF可以操作該字典: put(Key, Value) 將與鍵Key相關聯的新值Value加入進程字典。若與Key相關聯的值已經存在則該值將被刪除并被新值Value替代。該BIF返回原先與Key關聯的值,若原先沒有值與Key相關聯,則返回undefined。Key和Value可以是任意的Erlang項式。 get(Key) 返回進程字典中與Key關聯的值。若沒有值與Key相關聯則返回undefined。 get() 以{Key, Value}元組列表的形式返回整個進程字典。 get_keys(Value) 返回一個列表,包含進程字典中值為Value的所有的鍵。 erase(Key) 返回整個進程字典后將至刪除。 對于各個進程而言進程字典是局部的。進程剛被創建時進程字典為空。任何函數都可通過調用put(Key, Value)向字典中添加{Key, Value}鍵值對,而后再通過調用get(Key)取出。在catch作用域內,若在調用put后調用throw或出現錯誤,放入字典的值不會被撤回。 借助get()和erase()可以獲取或刪除整個字典。刪除單個條目可用erase(Key)。 有時候我們希望在多個不同函數中訪問同一塊全局數據,而將之作為進程中所有函數的參數來進行傳遞又不太方便。小心使用put和get就可以避免這個問題。 get和set在語言中引入了破壞性操作,令程序員寫出具有副作用的函數。這些函數的調用結果可能跟它們的調用次序相關。對進程字典的使用應該非常小心。get和set就好比傳統命令式語言里的goto。get和set在某些特定場景下很有用,但使用它們會造成不清晰的代碼,應該盡可能地避免使用。鑒于不鼓勵使用進程字典,本書的所有程序都不使用進程字典——為了內容完整,只在此處和附錄中包含相關內容。
網絡內核 net_kernel進程被用于協調分布式Erlang系統。運行時系統會自動向net_kernel發送某些消息。在該進程中執行的代碼決定對于不同的系統消息應該采取何種動作。 Erlang系統可在兩種模式下運行。它可以作為一個不與其他Erlang系統通訊的封閉系統運行,也可以同其他系統進行通訊,這時我們認為它存活著。通過調用BIF alive/2可以令系統活過來。通常這是由Erlang操作系統而不是用戶完成的。以下調用:
~~~
erlang:alive(Name, Port)
~~~
> 將通知網絡命名服務一個Erlang系統已經啟動并可以參與分布式計算了。
> Name是一個用于標識該Erlang系統的本地名稱。該Erlang系統的外部名稱為Name@MachineName,其中MachineName是節點所在的機器名,而字符“@”用于分隔本地名稱與機器名。例如,在名為super.eua.ericsson.se的主機上調用erlang:alive(foo,Port)將會啟動一個名為foo@super.eua.ericsson.se的Erlang系統,該名稱全局唯一。在同一臺機器上可以同時運行多個本地名不同的Erlang系統。
> Port是一個Erlang端口。外部端口程序必須遵從Erlang分布式系統的內部協議。該程序負責所有的網絡操作,如建立與遠程節點間的通訊信道以及向這些節點的字節緩沖區讀寫數據。不同版本的端口程序允許Erlang節點采用不同的網絡技術進行通訊。
> 執行alive/2將使執行該表達式的進程被加入一個可參與分布式計算的Erlang節點池。執行alive/2的進程必須以net_kernel為名進行注冊。否則,該BIF調用會失敗。要將一個節點從網路中斷開,可以關閉分布式端口。
> BIF is_alive()可用于檢測一個節點是否存活。該BIF返回true或false。
> 一旦有新節點出現,net_kernel就會收到一條{nodeup,Node}消息;一旦有節點失敗,net_kernel也相應會收到一條{nodedown,Node}消息。所有調用spawn/4或spawn_link/4的進程創建請求以及所有采用{Name,Node}!Message結構向遠程注冊進程發送消息的請求都會經過net_kernel進程。這使得用戶可以通過自定義net_kernel代碼來達成多種目的。例如,BIF spawn/4實際上是用Erlang自身實現的。在遠程節點創建進程的客戶端代碼為:
> >
~~~
spawn(N,M,F,A) when N /= node() ->
monitor_node(N, true),
{net_kernel, N} ! {self(), spawn, M, F, A, group_leader()},
receive
{nodedown, N} ->
R = spawn(erlang, crasher, [N,M,F,A,noconnection]);
{spawn_reply, Pid} ->
R = Pid
end,
monitor_node(N, false),
R;
spawn(N,M,F,A) ->
spawn(M,F,A).
crasher(Node,Mod,Fun,Args,Reason) ->
exit(Reason).
~~~
> 這段代碼的效果是向遠程節點上的net_kernel進程發送一條消息。遠程的net_kernel負責創建新進程,并告知客戶端新進程的Pid。
> > ### 認證
> Erlang系統采用“magic cookies”的方式內建了認證支持。Magic cookie是分配給各個節點的一個保密原子式。每個節點在啟動時都會被自動分配一個隨機cookie。節點N1要想和節點N2通訊,就必須知道N2的magic cookie。這里不討論N1如何找出N2的cookie。為了令N1得以和N2通訊,N1必須執行erlang:set_cookie(N2,N2Cookie),其中N2Cookie是N2的cookie值。另外,要令N1能夠收到來自N2的響應,N2也必須執行erlang:set_cookie(N1,N1Cookie,其中N1Cookie是N1的cookie值。
> Erlang運行時系統會將cookie插入到發送給所有遠程節點的所有消息中。若一條消息抵達某節點時攜帶著錯誤的cookie,則運行時系統會將這條消息轉換為以下格式:
> >
~~~
{From,badcookie,To,Message}
~~~
> 其中To是消息接收方的Pid或注冊名而From是發送方的Pid。所有未認證的消息發送請求和進程創建請求都會被轉為badcookie消息并發送至net_kernel。net_kernel可以任意處置badcookie消息。
> 以下兩個BIF可用于cookie操作:
> erlang:get_cookie()
> > 返回自己的magic cookie。
> erlang:set_cookie(Node,Cookie)
> > 將節點Node的magic cookie設置為Cookie。獲得Node的cookie后可以使用該BIF。它將令后續發送給Node的所有消息都包含Cookie。如果Cookie確實是Node的magic cookie,則消息將直接被發送至Node上的接收進程。如果包含的cookie有誤,該消息將在接收端被轉為badcookie消息,再被發送至那里的net_kernel。
> 默認情況下,所有節點都假定所有其他節點的cookie是原子式nocookie,因此初始時所有的遠程消息都包含cookie nocookie。
> 若調用erlang:set_cookie(Node,Cookie)時Node的值為本地節點的名字,則本地節點的magic cookie將被設置為Cookie,同時,其他所有cookie值為nocookie的節點都會變為Cookie。如果所有節點都在啟動時執行:
> >
~~~
erlang:set_cookie(node(), SecretCookie),
~~~
> 則它們將自動互相認證以便協作。應用如何獲取到SecretCookie是一個實現問題。保密cookie應保存于一個僅能由用戶讀取或僅能由用戶組讀取的文件中。
> 在UNIX環境下,節點啟動后的默認行為是讀取用戶HOME目錄下名為.erlang.cookie的文件。首先將會對文件的保護權限進行檢查,然后便會調用erlang:set_cookie(node(),Cookie),其中Cookie是包含cookie文件內容的原子式。之后,同一用戶就可以安全地與其他所有在相同用戶ID下運行的Erlang節點進行通訊了(假設所有節點都在同一文件系統下運行)。如果節點駐留在不同的文件系統中,用戶只須保證涉及到的文件系統中的cookie文件的內容相同即可。
> > ### net_kernel消息
> 以下是可以發送給net_kernel的消息的列表:
> - > {From,registered_send,To,Mess} 向注冊進程To的發送消息Mess的請求。
> - > {From,spawn,M,F,A,Gleader} 創建新進程的請求。Gleader是請求發起方進程的group leader。
> - > {From,spawn_link,M,F,a,Gleader} 創建新進程并向新進程建立鏈接的請求。
> - > {nodeup,Node} 當系統中有新節點接入時,net_kernel就會收到該消息。這種情況既可能是某遠程節點來聯絡我們,也可能是本地節點上的某個進程向該遠程節點首次完成了一次遠程操作。
> - > {nodedown,Node} 當某節點失敗或從本地節點無法聯絡到某遠程節點時,net_kernel就會收到該消息。
> - > {From,badcookie,To,Mess} 當有未認證請求發送到本節點時,net_kernel就會收到一條可表征該請求性質的消息。例如,某未認證節點發起了一個進程創建請求,net_kernel就會收到消息:
> >
~~~
{From,badcookie, net_kernel, {From,spawn,M,F,A,Gleader}}
~~~
> > ## 散列
> Erlang提供了一個可從任意項式產生一個整數散列值的BIF:
> hash(Term,MaxInt)
> > 返回一個在1..MaxInt范圍內的整數。
> 借助hash BIF我們可以編寫一個高效的字典查詢程序。該程序的接口與第??節的二叉樹實現的字典幾乎完全一樣。
> > 程序9.4
> >
~~~
-module(tupleStore).
-export([new/0,new/1,lookup/2,add/3,delete/2]).
new() ->
new(256).
new(NoOfBuckets) ->
make_tuple(NoOfBuckets, []).
lookup(Key, Tuple) ->
lookup_in_list(Key, element(hash(Key, size(Tuple)), Tuple)).
add(Key, Value, Tuple) ->
Index = hash(Key, size(Tuple)),
Old = element(Index, Tuple),
New = replace(Key, Value, Old, []),
setelement(Index, Tuple, New).
delete(Key, Tuple) ->
Index = hash(Key, size(Tuple)),
Old = element(Index, Tuple),
New = delete(Key, Old, []),
setelement(Index, Tuple, New).
make_tuple(Length, Default) ->
make_tuple(Length, Default, []).
make_tuple(0, _, Acc) ->
list_to_tuple(Acc);
make_tuple(N, Default, Acc) ->
make_tuple(N-1, Default, [Default|Acc]).
delete(Key, [{Key,_}|T], Acc) ->
lists:append(T, Acc);
delete(Key, [H|T], Acc) ->
delete(Key, T, [H|Acc]);
delete(Key, [], Acc) ->
Acc.
replace(Key, Value, [], Acc) ->
[{Key,Value}|Acc];
replace(Key, Value, [{Key,_}|T], Acc) ->
[{Key,Value}|lists:append(T, Acc)];
replace(Key, Value, [H|T], Acc) ->
replace(Key, Value, T, [H|Acc]).
lookup_in_list(Key, []) ->
undefined;
lookup_in_list(Key, [{Key, Value}|_]) ->
{value, Value};
lookup_in_list(Key, [_|T]) ->
lookup_in_list(Key, T).
~~~
> 該程序與程序??.4的唯一區別就在于函數new/1,我們需要向該函數傳入散列表的大小。
> 程序??.4是傳統散列查找程序的一個簡單實現。散列表T由一個定長元組表示。為了查找項式Key對應的值,需要計算出一個介于1..size(T)之間的散列索引I。element(I,T)返回一個列表,包含散列索引相同的所有{Key,Value}鍵值對。在該列表中可以搜索到所需的{Key,Value}對。
> 向散列表中插入數據時,首先計算出Key的散列索引整數I,再向element(I,T)返回的列表中插入新的{Key,Value}對。原先與Key關聯的值將被丟棄。
> tupleStore模塊提供了高效的字典。為了提高訪問效率散列表的大小必須大于表中所插入的元素的數目。從這種結構中進行查詢非常高效,但插入就遜色些。這是因為大部分Erlang視線中BIF setelement(Index,Val,T)每次都會創建一個新的元組T。
> > ## 效率
> 最后我們來討論一下效率。這并不是說我們認為這個主題不重要,而是因為我們相信過早關注效率問題會導致不良的程序設計。關注重點應該一直放在程序的正確性上,為了達到這個目的,我們提倡開發簡練漂亮且“明顯”正確的算法。
> 作為示例,我們將展示如何將低效的程序改造為高效的程序。
> 作為練習,我們從一個包含某假象公司員工信息元組的文件開始,該文件的內容為:
> >
~~~
{202191,’Micky’,’Finn’,’MNO’,’OM’,2431}.
{102347,’Harvey’,’Wallbanger’,’HAR’,’GHE’,2420}.
... 2860 lines omitted ...
{165435,’John’,’Doe’,’NKO’,’GYI’, 2564}.
{457634,’John’, ’Bull’,’HMR’,’KIO’, 5436}.
~~~
我們要寫一個程序來輸入這些數據、將每個條目都放入字典、訪問所有條目一遍,再將數據寫回文件。這個程序將頻繁執行,因此我們得讓它盡可能地快。 文件訪問 從上述的元組文件中讀入數據的最簡單的方法就是使用file:consult(File)讀取文件(參見附錄C)——這個方法很耗時,因為每一行都會被讀取和解析。一個好一點的做法是將輸入文件從文本格式改為二進制格式。通過以下函數可以實現:
~~~
reformat(FileOfTerms, BinaryFile) ->
{ok, Terms} = file:consult(FileOfTerms),
file:write_file(BinaryFile, term_to_binary(Terms)).
~~~
> 要讀入二進制文件并恢復原始數據,執行:
> >
~~~
read_terms(BinaryFile) ->
{ok, Binary} = file:read(BinaryFile),
binary_to_term(Binary).
~~~
> 讀取二進制文件并將結果轉換為項式要比讀取并解析一組項式要快得多,從下表便中可見一斑:
| 文本大小(bytes) | 二進制大小(bytes) | file:consult (ms) | read_terms (ms) | 耗時比例 |
|-----|-----|-----|-----|-----|
| 128041 | 118123 | 42733 | 783 | 54.6 |
| 4541 | 4190 | 1433 | 16 | 89.6 |
> 對于4.5K的文件,二進制文件讀取要快90倍;對于128K的文件要快55倍。注意二進制文件要被文本文件小一些。
> > ### 字典訪問
> 我們使用了不同的方法來構建和更新雇員字典。這些方法包括:
> lists
> > 所有雇員記錄都保存在一個列表中。在表頭進行首次插入,其余更新對列表進行線性掃描。
> avl
> > 采用第??節描述的AVL樹插入算法。
> hash
> > 采用程序9.4的散列算法。
> 為了檢驗不同方法的效率,我們對我們的每一條雇員數據都進行一次插入和查找,得到以下的計時結果:
| 條目數 | AVL插入 | AVL查找 | 列表插入 | 列表查找 | 散列插入 | 散列查找 |
|-----|-----|-----|-----|-----|-----|-----|
| 25 | 5.32 | 0.00 | 0.00 | 0.64 | 1.32 | 0.00 |
| 50 | 1.32 | 0.32 | 0.00 | 1.00 | 0.32 | 0.00 |
| 100 | 2.00 | 0.50 | 0.00 | 1.50 | 0.33 | 0.16 |
| 200 | 9.91 | 0.50 | 0.00 | 3.00 | 2.08 | 0.17 |
| 400 | 28.29 | 0.46 | 0.04 | 5.96 | 4.25 | 0.09 |
| 800 | 301.38 | 0.54 | 0.02 | 11.98 | 1.77 | 0.15 |
| 1600 | 1060.44 | 0.61 | 0.02 | 24.20 | 4.05 | 0.14 |
> 上表中每次插入或查詢的時間單位都是毫秒。我們看到對于大小超過800的數據表,散列表的查詢效率是最高的。
> 上面我們看到使用二進制文件和散列查詢算法要比使用file:consult和簡單列表查詢方法快六千倍。和傳統命令式語言一樣,決定程序效率的最重要因素還是良好的算法設計。
> 腳注
| [[1]](#) | 當然,要除去服務器用于存儲本地數據結構的空間。 |
|-----|-----|
| [[2]](#) | 非扁平列表就是不含有子列表的列表。(譯者注:也就是說當Data是一個整數列表時,既可以是[1,2,3]也可以是[1,[2,3]],在這里二者是等價的。) |
|-----|-----|