Réalisation d'un système d'échange de données réparties type P2P avec Chord en Erlang

De Wiki de Romain RUDIGER
Aller à : navigation, rechercher

Projet de répartition pair à pair (P2P)

Ce projet en binôme d'une durée de 18h, réalisé en Erlang, consistait à construire un système de partage d'objets en pair à pair similaire à ceux vus en cours. Ce système implémente le système de routage de Chord.

Participant : Benoît FARRE, Romain RÜDIGER.

Période : 05/01/09 - 07/01/09.

Problème à résoudre

Le service est le suivant : chaque utilisateur (donc chaque nœud du système) peut rejoindre le système, le quitter, partager un objet, localiser un exemplaire et en demander le transfert à l'un des nœuds qui le partage. Ici un objet est une ville accompagnée de sa liste de rues.

Problèmes résolus

Le programme ci dessous est capable de :

  1. rejoindre un système
  2. partager un objet
  3. rechercher l'emplacement d'un objet
  4. demander le transfert d'un objet

Il manque :

  1. quitter le système
  2. un processus pour consolider le réseau en vérifiant les voisins
  3. implémenter l'utilisation de la finger table pour accélérer la recherche d'un noeud
  4. faire des fonctions pour faciliter les commandes utilisateur

Manuel d'utilisation

Compilation:

c(kaloha).

Lancement sur le PC1:

kaloha:start(node()).

Lancement sur le PC2 en se connectant sur PC1:

kaloha:start('PC1').

Pour ajouter une ville:

{initd,node()} ! {add_town,'Nantes',['Rue1','Rue2']}.

Pour rechercher une ville:

{initd,node()} ! {get_town,'Nantes'}.

Pour afficher des infos du PCX:

{initd,'PCX'} ! {echo,info}.
{initd,'PCX'} ! {echo,all}.

Programme

%%%
%%% Authors: Romain Rüdiger, Benoît Farré
%%% Date: 1/2009
%%% Description: Kaloha is a start of a chord client implementation.
%%%              -Join a chord network,
%%%              -Identify Successor and Predecessor,
%%%              -Add a city with a streets list ({add_town,'Nantes',['street 1','street 2']}),
%%%              -Localize and get a city from any node.
%%%

-module(kaloha).

-export([start/1,stop/0,init/0,init/1,p2/1,make_finger_table/2,handler/1,is_in/3,update_finger_table/1,update_finger_table/2]).

-define(htable_size,10).

-define(wait_time,10000).

-record(noeud,{addr,id,succ=erlang:make_tuple(?htable_size,[]),pred,finger_table=erlang:make_tuple(?htable_size,[]),data=erlang:make_tuple(p2(?htable_size),[]),action,current_object,current_object_id}).

-record(finger_entry,{id,the_owner}).

-record(object,{town,streets}).

%%%
%%% Start/1
%%% Description: To start a new node:
%%%		 -If its the first node, launch: kaloha:start(node()),
%%%		 -Else, launch: kaloha:start(A_konw_host).
%%% Parameter: A know host or itself.
start(Known_addr) ->
    Addr=node(), % Notre addresse
    if
	Known_addr==Addr -> % Premier noeud du reseau
	    register(initd,spawn(kaloha,init,[]));
	true -> % Il y a deja des noeuds sur le reseau
	    register(initd,spawn(kaloha,init,[Known_addr]))
    end.
%%%
%%% Stop
%%% Description: To stop a node.
stop() ->
    io:format("Stop of the node ~w (PID : ~w) !~n",[node(),whereis(initd)]),
    PID = whereis(initd),
    exit(PID,kill),
    unregister(initd),
    PID = whereis(update_finger),
    exit(PID,kill),
    unregister(update_finger).

%%%
%%% Initialisation
%%% Description: This is used by the first node of a new chord network.
init() -> % Initialisation du premier noeud du reseau
    Id=erlang:phash(node(),p2(?htable_size)),
    Etat=#noeud{addr=node(),id=Id,pred=node()},
    New_Etat=make_finger_table(Etat,?htable_size),
    %End of the initialisation, start the node handler.
    register(finger_table,spawn(kaloha,update_finger_table,[New_Etat#noeud.finger_table])),
    handler(New_Etat).

%%%
%%% Initialisation
%%% Description: This is used by a new node who knows another node to join the network.
%%% Parameter: The name of a known node.
init(Known_addr) ->
    Id=erlang:phash(node(),p2(?htable_size)),
    Etat=#noeud{addr=node(),id=Id,pred=node()},
    Etat1=make_finger_table(Etat,?htable_size),
    %get our successor
    {initd,Known_addr} ! {get_succ,node()},
    receive
	{succ,Succ} -> 
	    Etat2=Etat1#noeud{succ=setelement(1,Etat1#noeud.succ,Succ)}; % add our successor in the noeud.succ list
	{exist} ->
	    Etat2=Etat1,
	    io:format("Problem ID ~w already exist!~n",[Id]),
	    exit
    end,
    %get our predessor
    {initd,element(1,Etat2#noeud.succ)} ! {get_pred,node()},
    receive
	{pred,Pred} -> 
	    Etat3=Etat2#noeud{pred=Pred} % set our predecessor in noeud.pred
    end,
    %update noeud.succ of our predecessor
    {initd,Etat3#noeud.pred} ! {set_succ,node(),node()},
    %update noeud.pred of our successor
    {initd,element(1,Etat3#noeud.succ)} ! {set_pred,node(),node()},
    %merge our noeud.data from our successor
    Pred_id = erlang:phash(Etat3#noeud.pred,p2(?htable_size)),
    % compute the Index for data_merge/2
    if 
	(Id < Pred_id) -> % Si id de notre pred est > à notre id (On passe par 0)
	    Index = p2(?htable_size) - Pred_id + Id ;
	true ->
	    Index = Id - Pred_id
    end,
    Etat4=merge_data(Etat3,Index),
    register(finger_table,spawn(kaloha,update_finger_table,[Etat3#noeud.finger_table])),
    %End of the initialisation, start the node handler.
    handler(Etat4).

    


%%%
%%% Handler/1
%%% Description: This is the node listener.
%%% Parameter: The node state.
handler(Etat) ->
    Id = Etat#noeud.id,
    Succ = element(1,Etat#noeud.succ),
    Succ_id = erlang:phash(Succ,p2(?htable_size)),
    Pred = Etat#noeud.pred,
    Pred_id = erlang:phash(Pred,p2(?htable_size)),
    receive
	{echo,info} -> % Echo node information
	    io:format("~nInfo of node ~w (~w):~n -Predecessor: ~w~n -Successor: ~w~n",[Etat#noeud.addr,Id,Etat#noeud.pred,element(1,Etat#noeud.succ)]),
	    io:format("Handle wait for receive cmd~n"),
	    handler(Etat);
	{echo,all} -> % Echo all node information
	    io:format("~nInfo of node ~w (~w):~n -Predecessor: ~w~n -Successors: ~w~n -finger_table: ~w~n -data: ~w~n",[Etat#noeud.addr,Id,Etat#noeud.pred,Etat#noeud.succ,Etat#noeud.finger_table,Etat#noeud.data]),
	    io:format("Handle wait for receive cmd~n"),
	    handler(Etat);
	{get_succ,From} -> % Send our first successor to From
	    io:format("Handle : get_succ from ~w, our succ is ~w.~n",[From,Succ]),
	    case Succ == node() of % Our succ is ourselves ?
		true -> % we are so lonely... :-*
		    io:format("-We are is successor~n"),
		    {initd,From} ! {succ,node()},
		    io:format("Handle wait for receive cmd~n"),
		    handler(Etat);
		false -> % we are not alone :-D
		    case is_in(Id,Succ_id,erlang:phash(From,p2(?htable_size))) of % Our succ is the same of From ?
			true ->
			    io:format("-Our succ is the same of From succ: ~w~n",[Succ]),
			    {initd,From} ! {succ,Succ},
			    io:format("Handle wait for receive cmd~n"),
			    handler(Etat);
			false ->
			    case (Id == erlang:phash(From,p2(?htable_size))) of % We have the same id ?
				true -> 
				    io:format("-Already exist~n"),
				    {initd,From} ! {exist},
				    io:format("Handle wait for receive cmd~n"),
				    handler(Etat);
				false ->
				   io:format("-Transmit get_succ to our succ: ~w~n",[Succ]),
				    {initd,Succ} ! {get_succ,From},
				    io:format("Handle wait for receive cmd~n"),
				    handler(Etat)
			    end
		end
	    end;
	{set_succ,From,New_succ} -> % update our succ
	    io:format("Handle : set_succ from ~w, New_succ = ~w~n",[From, New_succ]),
	    Etat1=Etat#noeud{succ=setelement(1,Etat#noeud.succ,New_succ)},  
	    io:format("Handle wait for receive cmd~n"),
	    handler(Etat1);
	{get_pred,From} -> % send our pred
	    io:format("Handle : get_pred from ~w, pred = ~w~n",[From, Pred]),
	    {initd,From} ! {pred,Pred},
	    io:format("Handle wait for receive cmd~n"),
	    handler(Etat);
	{set_pred,From,New_pred} -> % update our pred
	    io:format("Handle : set_pred from ~w, New_pred = ~w~n",[From, New_pred]),
	    Etat1=Etat#noeud{pred=New_pred},
	    io:format("Handle wait for receive cmd~n"),
	    handler(Etat1);
	{add_object,From,Object} -> % add an object in our noeud.data
	    io:format("Handle : add_object from ~w~n",[From]),
	    Object_id = erlang:phash(Object#object.town,p2(?htable_size)),
	    Etat1=Etat#noeud{data=setelement(Object_id+1,Etat#noeud.data,Object)},
	    io:format("Handle wait for receive cmd~n"),
	    handler(Etat1);
	{add_town,Town,Streets} -> % add a town (user request): {initd,node()} ! {add_town,'Nantes',['rue 1','rue 2']}
	    Object_id = erlang:phash(Town,p2(?htable_size)),
	    io:format("Handle : add_town of id ~w, get_owner.~n",[Object_id]),
	    % save the user request in State
	    Etat2 = Etat#noeud{action = 'add_town', current_object = #object{town=Town,streets=Streets}},
	    % look for the owner of this object
	    {initd,Succ} ! {get_owner,node(),Object_id},
	    io:format("Handle wait for receive cmd~n"),
	    handler(Etat2);
	{get_owner,From,Search_id} ->% get if we are the owner of a specified Id
	    io:format("Handle : get_owner of the id ~w from ~w~n",[Search_id,From]),
	    case (Pred_id==Succ_id) and (Succ_id==Id) of % we are alone?
		true ->
		    {initd,From} ! {return_owner,node()},
		    io:format("Handle wait for receive cmd~n"),
		    handler(Etat);
		false ->
		    case is_in(Pred_id,Id,Search_id) of % We are the owner of this id ?
			true ->
			    io:format("-We are the owner of the id: ~w~n",[Search_id]),
			    {initd,From} ! {return_owner,node()},
			    io:format("Handle wait for receive cmd~n"),
			    handler(Etat);
			false ->
			    case (Id == Search_id) of % Our id is the same as the Search_id?
				true ->
				    io:format("-We are the owner of the id: ~w~n",[Search_id]),
				    {initd,From} ! {return_owner,node()},
				    io:format("Handle wait for receive cmd~n"),
				    handler(Etat);
				false ->
				    io:format("-Transmit get_owner to our succ: ~w~n",[Succ]),
				    {initd,Succ} ! {get_owner,From,Search_id}, % transmit the request to our Succ
				    io:format("Handle wait for receive cmd~n"),
				    handler(Etat)
			    end
		    end
	    end;
	{get_owner_to_finger_table,From,Search_id} ->% get if we are the owner of a specified Id
	    case (Pred_id==Succ_id) and (Succ_id==Id) of % we are alone?
		true ->
		    {initd,From} ! {return_owner_to_finger_table,node()},
		    handler(Etat);
		false ->
		    case is_in(Pred_id,Id,Search_id) of % We are the owner of this id ?
			true ->
			    {initd,From} ! {return_owner_to_finger_table,node()},
			    handler(Etat);
			false ->
			    case (Id == Search_id) of % Our id is the same as the Search_id?
				true ->
				    {initd,From} ! {return_owner_to_finger_table,node()},
				    handler(Etat);
				false ->
				    {initd,Succ} ! {get_owner_to_finger_table,From,Search_id}, % transmit the request to our Succ
				    handler(Etat)
			    end
		    end
	    end;
	{return_owner,Owner} -> % respnse of our get_owner request
	    case Etat#noeud.action of % restart the last action
		'add_town' ->
		    io:format("Handle : return_owner (~w), the action was : add_town.~n",[Owner]),
		    {initd,Owner} ! {add_object,node(),Etat#noeud.current_object},
		    io:format("Handle wait for receive cmd~n"),
		    handler(Etat);
		'get_town' ->
		    io:format("Handle : return_owner (~w), the action was = get_town.~n",[Owner]),
		    {initd,Owner} ! {get_object,node(),Etat#noeud.current_object_id,(Etat#noeud.current_object)#object.town},
		    io:format("Handle wait for receive cmd~n"),
		    handler(Etat)
	    end;
	{return_owner_to_finger_table,Owner} -> % respnse of our get_owner_to_finger_table request
	    {finger_table,node()} ! {the_owner,Owner},
	    handler(Etat);
	{get_town,Town} -> % Retrieve a city for an user:  {initd,node()} ! {get_town,'Nantes'}
	    Object_id = erlang:phash(Town,p2(?htable_size)),
	    Etat2 = Etat#noeud{action = 'get_town', current_object = #object{town=Town,streets=[]}, current_object_id = Object_id},
	    io:format("Handle : get_town ~w of id ~w.~n",[Town,Object_id]),
	    {initd,Succ} ! {get_owner,node(),Object_id}, % Search for the owner
	    io:format("Handle wait for receive cmd~n"),
	    handler(Etat2);
	{get_object,From,Object_id,Town} -> % Retrieve a city to a node
	    Object = element(Object_id+1,Etat#noeud.data),
	    io:format("Handle : get_object of id ~w from ~w~n",[Object_id,From]),
	    case (Object /= []) of 
		true ->
		    case (Object#object.town == Town) of
			true ->
			    io:format("-We found the town, send it to ~w.~n",[From]),
			    {initd,From} ! {return_town,node(),element(Object_id+1,Etat#noeud.data)},
			    io:format("Handle wait for receive cmd~n"),
			    handler(Etat);
			false ->
			    io:format("-We found another town for this id, send [] to ~w.~n",[From])
		    end;
		false ->
		    io:format("-We didn't find the town ~w on node ~w, send [] to ~w.~n",[Town,node(),From])
	    end,
	    {initd,From} ! {return_town,node(),[]},
	    io:format("Handle wait for receive cmd~n"),
	    handler(Etat);
	{get_object,From,Object_id} -> % We search in noeud.data the id of the object
	    {initd,From} ! {return_object,element(Object_id+1,Etat#noeud.data)},
	    handler(Etat);
	{return_town,From,Object} -> % Answer of our get_town
	    io:format("Handle : return_town of ~w, the object = ~w.~n",[From,Object]),
	    Etat2 = Etat#noeud{action = '', current_object = '', current_object_id = ''},
	    io:format("Handle wait for receive cmd~n"),
	    handler(Etat2);
	{set_finger_table,New_finger_table} -> % Update the finger_table
	    io:format("Handle : set_finger_table.~n"),
	    Etat1 = Etat#noeud{finger_table = New_finger_table},
	    handler(Etat1);
	X ->
	    io:format("Command not found: ~w~n",[X]),
	    io:format("Handle wait for receive cmd~n"),
	    handler(Etat)
    end.

%%%%%%%%%%%%%%%%%%%%%%
%%% Internal functions

%%%
%%% merge_data/2
%%% Description: This is used to merge our noeud.data from our successor when we join a network
%%% Parameter: The state of our node, the index to check each data.
merge_data(Etat,1) -> 
    Etat;

merge_data(Etat,Index) ->
    Pred_id = erlang:phash(Etat#noeud.pred,p2(?htable_size)),
    {initd,element(1,Etat#noeud.succ)} ! {get_object,node(),(Pred_id+Index)rem p2(?htable_size)},
    receive % Wait to receive the requested object
	{return_object,Object} ->
	    Etat1=Etat#noeud{data=setelement(((Pred_id+Index)rem p2(?htable_size))+1,Etat#noeud.data,Object)}
    end,
    merge_data(Etat1,Index-1).

%%%
%%% is_in/3
%%% Description: Check if X is in ]A,B[
%%% Parameter: -X the element,
%%%            -A and B the interval.
%%% Return: True if X is in ]A,B[, else false.
is_in(A,B,X) ->
    if 
	((X > A) and (X < B)) ->
	    true;
	((A > B) and ((X > A) or (X < B))) -> % Cas quand on passe par 0 
	    true;
	true ->
	    false
    end.

%%%
%%% p2/1
%%% Description: Compute a power of 2.
%%% Parameter: -Val is the exposant.
%%% Return: The result of 2^Val.
p2(0) ->
    1;
    
p2(Val) ->
    2 * p2(Val-1).

%%%
%%% make_finger_table/2
%%% Description: Initialize the finger table at the node start.
%%% Parameter: -The node state,
%%%            -The index of the tuple.
%%% Return: The new node State.
make_finger_table(Etat,0) ->
    Etat;

make_finger_table(Etat,Index) ->
    Finger_start=(Etat#noeud.id+p2(Index-1)) rem p2(?htable_size),
    Finger_entry = #finger_entry{id=Finger_start},
    New_Etat=Etat#noeud{finger_table=setelement(Index,Etat#noeud.finger_table,Finger_entry), succ=setelement(Index,Etat#noeud.succ,Etat#noeud.addr)},
    make_finger_table(New_Etat,Index-1).

%%%
%%% update_finger_table/1
%%% Description: keep the finger table of this node up to date

update_finger_table(Finger_table, 0) ->
    Finger_table;

update_finger_table(Finger_table, Index) ->
    Finger_entry = element(Index,Finger_table),
    {initd,node()} ! {get_owner_to_finger_table,node(),Finger_entry#finger_entry.id},
    receive
	{the_owner,Owner} ->
	    Finger_entry#finger_entry{the_owner = Owner},
	    Finger_table1 = setelement(Index,Finger_table,#finger_entry{id=Finger_entry#finger_entry.id,the_owner=Owner}),
	    update_finger_table(Finger_table1,Index - 1)
    end.

update_finger_table(Finger_table) ->
    receive 
    after ?wait_time ->
        Finger_table1 = update_finger_table(Finger_table,?htable_size),
        {initd,node()} ! {set_finger_table,Finger_table1},
	update_finger_table(Finger_table1)
    end.

Téléchargement

media:Projet_P2P.zip