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:
Great work.
"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?
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.
buy tramadol online no prescription tramadol high booze - tramadol 50 mg slow release
buy cheap tramadol normal dosage tramadol humans - just pills order tramadol online
xanax online xanax for anxiety panic - xanax withdrawal panic attack
buy tramadol online tramadol for dogs itching - buy tramadol online from usa
xanax online xanax side effects for dogs - xanax circle pills
generic xanax can buy xanax online yahoo - pills similar to xanax
buy tramadol online tramadol legal to buy online - tramadol lethal dose
buy carisoprodol carisoprodol overdose limit - carisoprodol soma abuse
buy tramadol online order tramadol no prescription overnight - tramadol overdose fatal amount
can you really buy xanax online buy xanax cheap online no prescription - xanax side effects next day
carisoprodol 350 mg soma carisoprodol - what are soma carisoprodol tablets
carisoprodol 350 mg carisoprodol withdrawal syndrome - carisoprodol 350 mg with alcohol
buy tramadol online what is ultram tramadol hcl 50 mg - best dosage tramadol
buy tramadol online what is tramadol hcl 50 mg used for - tramadol hcl 50mg for dogs
soma carisoprodol carisoprodol 350 mg information - soma carisoprodol interactions
buy carisoprodol carisoprodol 350 mg buy - soma carisoprodol coupon
buy tramadol online purchase tramadol overnight - tramadol hcl 50 mg 377
alprazolam 0.5mg xanax effects pregnancy - drug interactions xanax and ibuprofen
buy xanax online legally alprazolam 0.5 mg tablet side effects - xanax bars difference between white yellow
buy cialis online ok buy cialis online - cialis
xanax online xanax generic colors - xanax side effects if you stop taking
cialis online cialis side effects - how buy cialis online
buy cialis online is cheap cialis safe - order cialis online us
cialis online cialis mail order - cialis online from us pharmacy
cialis 20mg buy cialis no prescription paypal - cialis coupon 30-day
buy tramadol online buy tramadol hcl 50mg - tramadol withdrawal nhs
buy tramadol online tramadol for dogs safe - buy tramadol us pharmacy
buy tramadol buy tramadol ships florida - buy tramadol online florida
buy tramadol tramadol hcl nursing implications - tramadol 50 mg para que es
http://landvoicelearning.com/#74967 tramadol is generic for - buy 200 mg tramadol online
buy tramadol rx tramadol withdrawal cure - tramadol 717
buy tramadol order tramadol with free shipping - tramadol for dogs usa
learn how to buy tramdadol tramadol 50 mg compared to percocet - cheap tramadol overnight no prescription
buy tramadol tramadol for dogs safe for humans - tramadol dosage neuropathy
order tramadol online overnight buy tramadol online bluelight - life after tramadol addiction
buy tramadol tramadol online overnight cod - tramadol hcl bp 100mg
http://buytramadolonlinecool.com/#61458 legal buy tramadol online united states - is tramadol hcl make you high
buy discount tramadol tramadol dosage directions - tramadol for dogs 50mg dosage
http://landvoicelearning.com/#21906 tramadol hcl 50 mg migraines - tramadol ultram tramal
buy tramadol free shipping generic tramadol usa - tramadol tolerance
ways to buy ativan online ativan prolonged qt interval - ativan dosage levels
buy lorazepam online lorazepam to buy uk - ativan dosage side effects
http://blog.dawn.com/dblog/buy/#side-effects seizure after overdose tramadol - tramadol online prescription
ativan online pharmacy ativan drug vs xanax - ativan price per pill
ativan without prescription ativan overdose signs symptoms - ativan withdrawal vomiting
http://ranchodelastortugas.com/#61301 drug rehab centers xanax - xanax online no prescription overnight
http://staam.org/#21236 tramadol dosage buzz - tramadol dosage sizes
buy tramadol without a script tramadol dosage get high - buy tramadol online prescription
buy xanax online generic xanax same xanax - jpee xanax 2mg
no prescription xanax xanax side effects anxiety - 2mg xanax street value
http://bayshorechryslerjeep.com/#2902 buying xanax online bluelight - difference between generic xanax
buy xanax online xanax bars lyrics - xanax alcohol high
Post a Comment