Erlang] Message pass mechanism

You have to be very carefully about using message passing. The overhead is much more than you think. Here is the thing:

Comparition version:

A ———–> B
A <———– B

Original version:

A ———–> B
A <———– B
A <———– B

The original version can be almost ten times slower than comparition version!

Advertisements

[Erlang] Diffie-Hellman Key Exchange

Recently I try to write Diffie-Hellman key exchange protocol. And I found that Erlang’s library crypto provide  dh_generate_key & dh_compute_key API.


Types
byte() = 0 ... 255
ioelem() = byte() | binary() | iolist()
iolist() = [ioelem()]
Mpint() = <<ByteLen:32/integer-big, Bytes:ByteLen/binary>>
dh_generate_key(DHParams) -> {PublicKey,PrivateKey}
dh_generate_key(PrivateKey, DHParams) -> {PublicKey,PrivateKey}
  • DHParameters = [P, G]
  • P, G = Mpint Where P is the shared prime number and G is the shared generator.
  • PublicKey, PrivateKey = Mpint()

Generates a Diffie-Hellman PublicKey and PrivateKey (if not given).

dh_compute_key(OthersPublicKey, MyPrivateKey, DHParams) -> SharedSecret
  • DHParameters = [P, G]
  • P, G = Mpint Where P is the shared prime number and G is the shared generator.
  • OthersPublicKey, MyPrivateKey = Mpint()
  • SharedSecret = binary()

Computes the shared secret from the private key and the other party’s public key.

So this is how to use the API.

crypto:start().

% you can use dh_generate_parameters(512, 2) to generate

DHParams = [<<LenP:32, BinP/binary>>, <<LenG:32, BinG/binary>>],

{<<LenPub:32, PubKey/binary>>, PrivKey} =crypto:dh_generate_key(DHParams), SessionKey = crypto:dh_compute_key(<<LenA:32, BinA/binary>>,

PrivKey,  DHParams),

For more information, you can check /usr/local/lib/erlang/lib/crypto-1.6.3/src/crypto.erl

[Erlang] priority message passing notes

在Erlang User Conference 2006上, 看到一篇關於Erlang message passing的slide, 覺得蠻有趣的

Ref: http://www.duomark.com/erlang/briefings/euc2006/index.html

這篇slide分成3個部份

第1部份是講基本語法

第2部份就是我比較感興趣的地方, 他提到一個有趣的問題

問題描述:
在利用Erlang接受message的時候, 如果有一種priority message, 只要一接收到這種message, 就要先執行相對應的工作, 但是在Erlang的message model中, 他有一個message queue, 所有的message都會被丟到這個queue裡面, 照順序接收,他並不保證有某些message接收的順序是比較高的, 所以我們應該要怎麼解決這個問題?

解法:
其實這個問題並不是很好解決, 他先提出兩種polling的方法, 但是都不是很好, 而且一個process當中最好不要有兩個以上的receive message statement, 可能會有memory performance的問題, 所以他給出利用protocol溝通的方式:

分成router, high process, low process and data store 4個process, 簡單來說router會控制現在是要讓high process還是讓low process去access data store, 所以利用protocol來判斷兩個process當中的message queue, 一旦high process有要處理的message, 就擋掉low process!

flow-chart

第3部份:

介紹一種(event programming) pattern, 來避免利用一大堆State machine來實作(以後更改太困難…).

Description:
central event loop will call associate method according to the message. After the method executed, it will return the control to main loop. The main loop will dispatch messages for multiple process instance which is not blocking! Central event loop can detect asynchronous process message!!

Code:

event_loop(M, S) ->
    receive
        {From, Event} ->
            dispatch(From, Event, M, S);
        {From, Ref, Event} ->
            dispatch(From, Event, M, S);
        Other ->
            io:format(”Unknown msg: ~p~n", [Other]),
            exit({unknown_msg, Other})

    end.
% Recv will be the asynch process id
event_loop(M, S, Recv) ->
    receive
      {From, Event} when element(From, Recv) == [] ->
            dispatch(From, Event, M, S);
      {From, Ref, Event} when element(From, Recv) == Ref ->
            dispatch(From, Event, M, S);
      {From, Ref, Event} when element(From, Recv) == [] ->
            dispatch(From, Event, M, S)
    end.
% M:Event method can be asynchronous process
% which will return {ok, NewState, Recv}
dispatch(From, Event, M, S) when atom(Event) ->
    handle(M:Event(From, S), M);

dispatch(From, {Event, Arg}, M, S) ->
    handle(M:Event(From, Arg, S), M).
handle({ok, NewState}, M) ->
    event_loop(M, NewState);

handle({ok, NewState, Recv}, M) ->
    event_loop(M, NewState, Recv).

[Erlang] short summary (part 2)

上次大概介紹了Erlang這個語言的特性, 這次我想稍微介紹一下OTP的設計概念或者說我們應該要怎麼用Erlang來設計network service。(需要稍微了解Erlang 語法), (p.s 本篇code跟圖出處都是Joe的論文)

Erlang的OTP設計上,他是把關於concurrent programming隱藏起來,讓使用者只需要專注於sequencial programming的部分,現在我們來看它是怎麼實作的。

OTP也是使用client-server的架構, 所謂client-server就是指以下這張圖

image

最基本的generic server code如下:

-module(server1).
-export([start/3, stop/1, rpc/2]).
start(Name, F, State) –>
 % register and create a process which name is Name
 % and tell the server to use the handler function F
 register(Name, spawn(fun() ->
        loop(Name, F, State)
        end)). 
stop(Name) -> Name ! stop. 
rpc(Name, Query) –>
  % send the message to server Name
  Name ! {self(), Query},
  receive
        {Name, Reply} -> Reply
  end.
loop(Name, F, State) ->
   receive
         stop -> void;
         {Pid, Query} –>
               % important!! use function F to compute message
               {Reply, State1} = F(Query, State),
               % and return the message to client
               Pid ! {Name, Reply},
               loop(Name, F, State1)
end.

以上的程式流程大概是這樣跑:
註冊新的process當server, 告訴它使用的handler, 此process一直在function loop中wait message, 它會接收到兩種message, 一種是stop, 那server就會停止,另一種傳Query, 讓server利用Query去做事, 然後再回傳結果給client Pid, 並且更新server自己的狀態

有了以上的generic server model, 我們現在就可以實際針對我們所要開發的server了!

假設今天只是要做個簡單的Home Location Register

-module(vshlr1).
-export([start/0, stop/0, handle_event/2, i_am_at/2, find/1]). 
-import (server1, [start/3, stop/1, rpc/2]).
-import(dict, [new/0, store/3, find/2]). 
start() –> start(vshlr, fun handle_event/2, new()). 
stop() –> stop(vshlr). 
% server’s api
i_am_at(Who) –> rpc(vshlr, {i_am_at, Who, Where}).
find(Who) –> rpc(vshlr, {find, Who}). 
% event_handler
handle_event({i_am_at, Who, Where}, Dict) –>

    { ok, store(Who, Where, Dict)};
handle_event({find, Who}, Dict) –>

    {find(Who, Dict), Dict).

所以我們只要實做出自己的handler就可以產生一個簡單的

所以在Erlang的virtual machine下, 我們就可以這樣做

1> vshlr1:start().
true
2> vshlr1:find(“joe”).
error
3> vshlr1:i_am_at(“joe”,”sics”).
ack
4> vshlr1:find(“joe”).
{ok,”sics”}

上面的例子中, 我們可以看到對於用Erlang來實作出一個簡單的server是如此的簡單, 但是我們還沒有提到關於error recovery跟runtime upgrade的部分, 以下就這兩個部分來說明

Error recovery:

首先修改我們的server code

rpc(Name, Query) –>
    % send the message to server Name
    Name ! {self(), Query},
    receive
           {Name, Reply} –> Reply ;
           {Name, crash} –> exit(rpc)
   after 10000 –>
           exit(timeout)
end.
loop(Name, F, State) ->
       receive
          stop -> void;
          {From, Query} –>
                case (catch F(Query, State)) of
                    {‘EXIT’, Why} –>
                        log_error(Name, Query, Why),
                        From ! { Name, crash},
                        loop(Name, F, State);
                   {Reply, State1} –>
                       From !{Name, ok, Reply},
                       loop(Name, F, State1)
                  end
  end.
log_error(Name, Query, Why) –>
% something you can log

所以當有錯誤發生的時候, 我們就直接把錯誤log下來, 並且告訴client, 關掉client, 而且我們設置了一個timeout, 當client等待太久, 也會關掉

接下來我們接著改成可以runtime code replacement的版本

swap_code(Name, F) –> rpc(Name, {swap_code, F}).
loop(Name, F, State) ->
     receive
           stop -> void;
          {From, {swap_code, F1}} –>
                From ! { Name, ok, ack},
                loop(Name, F1, State);
          {From, Query} –>
               case (catch F(Query, State)) of
                    {‘EXIT’, Why} –>
                        log_error(Name, Query, Why),
                        From ! { Name, crash},
                        loop(Name, F, State);
                  {Reply, State1} –>
                        From !{Name, ok, Reply},
                        loop(Name, F, State1)
            end 
  end.

一切都是如此的簡單容易, 當然真正的OTP不是那麼簡單的, 不過這邊我只大概說明OTP設計的概念, 還有Erlang在設計這類程式的方便性, OTP裡面還有關於supervisor等課題沒介紹,而且關於效率上跟實務上的應用我本身也不熟(剛開始接觸而已^^””), 接下來我準備開始實際去trace Erlang的source code, 看底層的實作關於message passing跟light weight process, 所以可能會拖很久才會繼續寫下去吧XD

Reference: Making reliable distributed systems in the presence of software errors

[Erlang] short summary (part 1)

最近在學習Erlang,發現Erlang其實是一個蠻簡單容易理解的語言,而且針對特定的問題(concurrent progarmming, 分散式系統, 網路service),寫起來很快。尤其現在multi-core的CPU,在Functional language的model下(No share memory),應該更能好好運用其多核心的運算能力,Erlang 應該可以算是目前Functional Language在工業上面蠻常運用到的(尤其在電信業),他一開始是從Ericsson裡面的CSLab所開發出來的,後來就open source出來,他最強大的是一套可以稱為Framework or Library的工具OTP(Open Telecom Platform),因為它主要是focus on server,他把一些設計concurrent program的概念隱藏在裡面,所以你直接套用這套工具的話,可以省不少事。

Erlang是跑在他自己的Virtual machine上面,具有一些特性:

  • runtime update
  • pure message passing
  • light weight process
  • fault tolerant

runtime update:

Erlang的Virtual Machine讓你可以在程式執行的時候,去修改程式碼後,他會dynamic load進新的程式碼,讓你不必把程式關掉在執行

light weight process:

Erlang不像是其他程式語言,它直接把process的概念放進語法裡面,在Erlang的設計概念中,他希望所有的事物都是透過你把事情切割分別讓process去操作,而且Erlang創造一個process的overload不是很大

pure message passing:

在Erlang當中,既然可以自由的創造process,那這些process之間要怎麼溝通呢?他不像是傳統寫C, C++這類sequential程式一樣是利用lock/unlock等synchronize技巧,他純粹就是你直接可以Send message給別的process,其他process只要等著receice message就可以了,這有個好處,就是沒有share variable等因素可能會造成race condition or dead lock,而且Erlang並沒有限制process只能在local,你可以自由的send message到遠端的node,這正好發揮了distribute system的強處

fault tolerant:

因為Erlang一開始就用途就是為了電信業上面的switch,在電信業本身它希望程式能夠再發生error的時候,能夠自動correct error或是restart,所以在Erlang的設計概念中,他希望process如果發生處理不了的問題,就讓process自動被kill,跟這個process有相關的process會收到通知說,有process被kill,在根據原因來做一些適當的處理

待續

在part 2中,我準備稍微介紹一下OTP裡面關於實作server的pattern

[erlang] Parse Transform

最近看到某個library的function居然呼叫的時候,強制必須傳list comprehension,讓我很shock, 居然erlang可以這樣檢查type?!

Ex:

version 1: (ok)
qlc([X || X <- Table])

version 2: (error)
Val = [X || X <- Table ]
qlc(Val)

結果實際trace erlang的source code 加上 IRC上面的人解答

原來erlang可以用類似pre-process的方式, 在parse的時候就判斷參數的正確性

這雖然不是什麼新概念, 但是你可以寫parser的plug-in, 這感覺就很不一樣!

p.s IRC上的人果然都是好人~ 有問題都可以問問~~

Reference:
http://www.erlang.org/documentation/doc-5.4.8/lib/stdlib-1.13.8/doc/html/qlc.html