Tuesday, October 9, 2007

Scalable data structures in Erlang, and gen_leader

A scalable data structure is a data structure distributed across multiple nodes. You can add nodes to get more capacity, more throughput, and better availability. Erlang/OTP is ideal for building such structures, but is missing one critical piece.

I've been working on a distributed hash table (DHT) based on the idea of linear hashing. (The inventor of linear hashing, Witold Litwin, is also working along these lines.) Each node can serve a put or get request, and also owns a set of hash buckets. A mapping of hash buckets to nodes is used to dispatch a request to the right node.

When a node fails, or when a node is added, a new mapping of hash buckets to nodes is required. The question is how to create this new mapping. It is difficult or maybe impossible to guarantee that each node will derive the identical map, especially since map creation isn't perfectly synchronous across the set of nodes, and there may be changes in the node population (e.g. another node failure) during map creation.

The alternative is for one node to create the map and distribute it to other nodes. But which node? What is needed is for the set of participating nodes to agree on a node to carry out this task. This is the "leader election" problem. When a leader is needed, it is needed right away. There must be exactly one leader selected, and all participants must know who the leader is.

Leader election is a suprisingly difficult problem. Erlang/OTP does not include a leader election module. However, I ran across an implementation of leader election that would be right at home in OTP: gen_leader.

gen_leader includes a demo application, gdict. Updates go to the leader and are distributed to all nodes, while reads can be carried out locally. I had some trouble getting gdict to work. One of the gen_leader authors, Ulf Wiger, was kind enough to set me straight. My test program appears below. Some comments on the code:

  • I first wrote the test to run from one node, z@zack, and access a two-node hash table, on nodes a@zack and b@zack. I also specified that nodes a and b were both candidate leaders (second argument to gdict:new) and workers (not eligible to be leader). All that was wrong.
  • The current version of my test runs on node z, makes a, b, and z candidates, has no workers, and runs gdict:new on z.
  • It is necessary to have the nodes see each other, which I accomplished using the hack of the two rpc:call invocations. I still don't completely understand how the nodes are supposed to discover each other, but I haven't gotten very far in reading about OTP.

I haven't done any work with gen_leader other than to watch gdict work. But assuming it works as advertised, (and the authors seem to have been fanatical about testing), it is a crucial piece of software in implementing a scalable data structure in Erlang.

The gdict test code:

-module(test).
-export([main/0]).

-define(DUMP(X), io:format("~p:~p - ~p = ~p~n", [?MODULE, ?LINE, ??X, X])).


main() ->
rpc:call(a@zack, hello, hello, []),
rpc:call(b@zack, hello, hello, []),
?DUMP(node()),
?DUMP(nodes()),
Nodes = [node() | nodes()],
{ok, D} = gdict:new(test, Nodes, []),
?DUMP(D),
?DUMP(gdict:append(a, 1, D)),
?DUMP(gdict:append(b, 2, D)),
?DUMP(gdict:append(c, 3, D)),
?DUMP(gdict:find(a, D)),
?DUMP(gdict:find(b, D)),
?DUMP(gdict:find(c, D)).

55 comments:

Ricjunette said...

Great work.

Sean said...

"It is difficult or maybe impossible to guarantee that each node will derive the identical map..."

Isn't this exactly what every DHT does, without needing centralized creation of the map?

O(1) said...

I may have misused the term DHT. The applications I've been working on have had a small network of nodes, less than 100, all sitting on a LAN. In such environments, the complications of doing without a map, coordinated among all nodes, aren't worth it, in my opinion. It's easier to just have a leader create a map and distribute it. Especially if I can get a working leader-election implementation.

Anonymous said...

buy tramadol online no prescription tramadol high booze - tramadol 50 mg slow release

Anonymous said...

buy cheap tramadol normal dosage tramadol humans - just pills order tramadol online

Anonymous said...

xanax online xanax for anxiety panic - xanax withdrawal panic attack

Anonymous said...

buy tramadol online tramadol for dogs itching - buy tramadol online from usa

Anonymous said...

xanax online xanax side effects for dogs - xanax circle pills

Anonymous said...

generic xanax can buy xanax online yahoo - pills similar to xanax

Anonymous said...

buy tramadol online tramadol legal to buy online - tramadol lethal dose

Anonymous said...

buy carisoprodol carisoprodol overdose limit - carisoprodol soma abuse

Anonymous said...

buy tramadol online order tramadol no prescription overnight - tramadol overdose fatal amount

Anonymous said...

can you really buy xanax online buy xanax cheap online no prescription - xanax side effects next day

Anonymous said...

carisoprodol 350 mg soma carisoprodol - what are soma carisoprodol tablets

Anonymous said...

carisoprodol 350 mg carisoprodol withdrawal syndrome - carisoprodol 350 mg with alcohol

Anonymous said...

buy tramadol online what is ultram tramadol hcl 50 mg - best dosage tramadol

Anonymous said...

buy tramadol online what is tramadol hcl 50 mg used for - tramadol hcl 50mg for dogs

Anonymous said...

soma carisoprodol carisoprodol 350 mg information - soma carisoprodol interactions

Anonymous said...

buy carisoprodol carisoprodol 350 mg buy - soma carisoprodol coupon

Anonymous said...

buy tramadol online purchase tramadol overnight - tramadol hcl 50 mg 377

Anonymous said...

alprazolam 0.5mg xanax effects pregnancy - drug interactions xanax and ibuprofen

Anonymous said...

buy xanax online legally alprazolam 0.5 mg tablet side effects - xanax bars difference between white yellow

Anonymous said...

buy cialis online ok buy cialis online - cialis

Anonymous said...

xanax online xanax generic colors - xanax side effects if you stop taking

Anonymous said...

cialis online cialis side effects - how buy cialis online

Anonymous said...

buy cialis online is cheap cialis safe - order cialis online us

Anonymous said...

cialis online cialis mail order - cialis online from us pharmacy

Anonymous said...

cialis 20mg buy cialis no prescription paypal - cialis coupon 30-day

Anonymous said...

buy tramadol online buy tramadol hcl 50mg - tramadol withdrawal nhs

Anonymous said...

buy tramadol online tramadol for dogs safe - buy tramadol us pharmacy

Anonymous said...

buy tramadol buy tramadol ships florida - buy tramadol online florida

Anonymous said...

buy tramadol tramadol hcl nursing implications - tramadol 50 mg para que es

Anonymous said...

http://landvoicelearning.com/#74967 tramadol is generic for - buy 200 mg tramadol online

Anonymous said...

buy tramadol rx tramadol withdrawal cure - tramadol 717

Anonymous said...

buy tramadol order tramadol with free shipping - tramadol for dogs usa

Anonymous said...

learn how to buy tramdadol tramadol 50 mg compared to percocet - cheap tramadol overnight no prescription

Anonymous said...

buy tramadol tramadol for dogs safe for humans - tramadol dosage neuropathy

Anonymous said...

order tramadol online overnight buy tramadol online bluelight - life after tramadol addiction

Anonymous said...

buy tramadol tramadol online overnight cod - tramadol hcl bp 100mg

Anonymous said...

http://buytramadolonlinecool.com/#61458 legal buy tramadol online united states - is tramadol hcl make you high

Anonymous said...

buy discount tramadol tramadol dosage directions - tramadol for dogs 50mg dosage

Anonymous said...

http://landvoicelearning.com/#21906 tramadol hcl 50 mg migraines - tramadol ultram tramal

Anonymous said...

buy tramadol free shipping generic tramadol usa - tramadol tolerance

Anonymous said...

ways to buy ativan online ativan prolonged qt interval - ativan dosage levels

Anonymous said...

buy lorazepam online lorazepam to buy uk - ativan dosage side effects

Anonymous said...

http://blog.dawn.com/dblog/buy/#side-effects seizure after overdose tramadol - tramadol online prescription

Anonymous said...

ativan online pharmacy ativan drug vs xanax - ativan price per pill

Anonymous said...

ativan without prescription ativan overdose signs symptoms - ativan withdrawal vomiting

Anonymous said...

http://ranchodelastortugas.com/#61301 drug rehab centers xanax - xanax online no prescription overnight

Anonymous said...

http://staam.org/#21236 tramadol dosage buzz - tramadol dosage sizes

Anonymous said...

buy tramadol without a script tramadol dosage get high - buy tramadol online prescription

Anonymous said...

buy xanax online generic xanax same xanax - jpee xanax 2mg

Anonymous said...

no prescription xanax xanax side effects anxiety - 2mg xanax street value

Anonymous said...

http://bayshorechryslerjeep.com/#2902 buying xanax online bluelight - difference between generic xanax

Anonymous said...

buy xanax online xanax bars lyrics - xanax alcohol high