9448
Comment:
|
8379
|
Deletions are marked like this. | Additions are marked like this. |
Line 2: | Line 2: |
<<TableOfContents(2)>> | <<TableOfContents(4)>> |
Line 5: | Line 5: |
=== bool check_non_participation(p_id, lvl, _pos) === | === check_non_participation === '''bool check_non_participation(p_id, lvl, _pos)''' |
Line 17: | Line 18: |
* Prepara ''waiting_answer'' = new !WaitingAnswer(null, (lvl,_pos) come PeerTupleGNode con top = lvl+1). ~-Il fatto che l'istanza di IPeersRequest è a null fa in modo che i metodi remoti che ricevono le notifiche si comportano in modo adeguato. Sostanzialmente dovrebbe cambiare solo il fatto che quando si riceve la segnalazione di get_request si risponde sempre con l'eccezione !PeersUnknownMessageError, ache se si è potuto recuperare l'istanza di !WaitingAnswer. Sull'istanza di !WaitingAnswer viene poi valorizzato il membro response con qualcosa diverso da ''null'' solo per indicare che il g-nodo partecipa.-~ | * Prepara ''waiting_answer'' = new !WaitingAnswer(null, (lvl,_pos) come PeerTupleGNode con top = lvl+1). ~-Il fatto che l'istanza di IPeersRequest è a null fa in modo che i metodi remoti che ricevono le notifiche si comportano in modo adeguato. Sostanzialmente dovrebbe cambiare solo il fatto che quando si riceve la segnalazione di get_request si risponde sempre con l'eccezione !PeersUnknownMessageError, anche se si è potuto recuperare l'istanza di !WaitingAnswer. Sull'istanza di !WaitingAnswer viene poi valorizzato il membro response con qualcosa diverso da ''null'' solo per indicare che il g-nodo partecipa.-~ |
Line 19: | Line 20: |
* IAddressManagerRootDispatcher ''gwstub'' * IAddressManagerRootDispatcher? ''failed'' = null |
* IPeersManagerStub ''gwstub'' * IPeersManagerStub? ''failed'' = null |
Line 27: | Line 28: |
* Esegue gwstub.peers_manager.forward_peer_message(m’). | * Esegue gwstub.forward_peer_message(m’). |
Line 54: | Line 55: |
=== void publish_my_participation(p_id) === | === publish_my_participation === '''void publish_my_participation(p_id)''' |
Line 66: | Line 68: |
* tcp_stub.peer_manager.set_participant(p_id, gn). | * tcp_stub.set_participant(p_id, gn). |
Line 71: | Line 73: |
* br_stub.peer_manager.set_participant(p_id, gn). | * br_stub.set_participant(p_id, gn). |
Line 76: | Line 78: |
=== void set_participant(int p_id, PeerTupleGNode gn) === | === set_participant === '''void set_participant(int p_id, PeerTupleGNode gn)''' |
Line 98: | Line 101: |
* tcp_stub.peer_manager.set_participant(p_id, ret_gn). | * tcp_stub.set_participant(p_id, ret_gn). |
Line 103: | Line 106: |
* br_stub.peer_manager.set_participant(p_id, ret_gn). | * br_stub.set_participant(p_id, ret_gn). |
Line 110: | Line 113: |
== Algoritmo di mantenimento di un database distribuito == === bool begin_replica(q, p_id, x̄, r, timeout_exec, out ISerializable resp, out IPeersContinuation cont) === |
== Algoritmi per il mantenimento di un database distribuito == === Per migliorare la persistenza dei dati === '''bool begin_replica(q, p_id, x̄, r, timeout_exec, out IPeersResponse? resp, out IPeersContinuation cont)''' |
Line 116: | Line 120: |
* !RemoteCall ''r'': la richiesta di replicare la coppia k,val , | * IPeersRequest ''r'': la richiesta di replicare la coppia k,val , |
Line 121: | Line 125: |
* ''exclude_tuple_list'' = new PeerTupleGNodeContainer. | * ''exclude_tuple_list'' = new PeerTupleGNodeContainer(x̄.tuple.size). |
Line 125: | Line 129: |
=== bool next_replica(IPeersContinuation cont, out ISerializable resp) === * resp = new ISerializableNone. |
'''bool next_replica(IPeersContinuation cont, out IPeersResponse? resp)''' * resp = null. |
Line 131: | Line 135: |
* Se si riceve l'eccezione !PeersNoParticipantsInNetworkError: * Return False. |
* Se si riceve l'eccezione !PeersNoParticipantsInNetworkError o !PeersDatabaseError: * Return False. L'eccezione !PeersDatabaseError va vista come "OUT_OF_MEMORY" essendo la replica una operazione di sovrascrittura o inserimento. |
Line 138: | Line 142: |
=== bool begin_retrieve_cache(p_id, r, timeout_exec, out ISerializable resp, out IPeersContinuation cont) === * Gli argomenti sono: * int ''p_id'', * !RemoteCall ''r'': la richiesta di ricevere la cache , * int ''timeout_exec'', * ''resp'' viene valorizzato con la risposta o null; * ''cont'' è un oggetto di cui all'esterno si sa solo che implementa l'interfaccia vuota IPeersContinuation. * resp = new ISerializableNone. * Per ''j'' da 0 a levels-1: * !PeerTupleNode ''x̄'' = make_tuple_node(new HCoord(0, pos[0]), j+1) : cioè la tupla dei primi j+1 livelli di n = n~-,,0,,-~·...·n~-,,j,,-~. * ''exclude_tuple_list'' = new PeerTupleGNodeContainer. * !PeerTupleNode ''respondant''; * ret = contact_peer(p_id, x̄, r, timeout_exec, True, out respondant, exclude_tuple_list). * Se si riceve l'eccezione !PeersNoParticipantsInNetworkError: * Continue. Prossima iterazione del ciclo. * aggiungi respondant a exclude_tuple_list. * cont = {p_id, r, timeout_exec, j, exclude_tuple_list}. * resp = ret. * Return True. * Return False. === bool next_retrieve_cache(IPeersContinuation cont, out ISerializable resp) === * resp = new ISerializableNone. * ''j'' = cont.j. * !PeerTupleNode ''x̄'' = make_tuple_node(new HCoord(0, pos[0]), j+1) : cioè la tupla dei primi j+1 livelli di n = n~-,,0,,-~·...·n~-,,j,,-~. * !PeerTupleNode ''respondant''; * ret = contact_peer(cont.p_id, x̄, cont.r, cont.timeout_exec, True, out respondant, cont.exclude_tuple_list, True). * Se si riceve l'eccezione !PeersNoParticipantsInNetworkError: * Return False. * resp = ret. * Return False. |
=== Per garantire la coerenza dei dati === Per garantire la coerenza dei dati e gestire l'esaustività e le limitazioni di memoria dei singoli nodi, gli algoritmi sviluppati sono illustrati nei seguenti documenti: * [[Netsukuku/ita/docs/ModuloPeers/DatabaseTTL|Database con un Time To Live]] * [[Netsukuku/ita/docs/ModuloPeers/DatabaseFixedKeys|Database a chiavi fisse]] |
Modulo PeerServices - Appunti - Algoritmi 2 / 2
Algoritmo di rilevamento di non partecipazione
check_non_participation
bool check_non_participation(p_id, lvl, _pos)
- In questo algoritmo non ci interessa sapere se un g-nodo partecipa, ma solo se è possibile dire con certezza che esso non partecipa. In caso di incertezza l'algoritmo restituisce False.
Produci x̄ = la tupla x̄0·x̄1·...·x̄lvl-1 dove x̄i = 0 per ogni i. La tupla identifica un indirizzo a caso all'interno del g-nodo g = (lvl, _pos). Se lvl = 0 allora x̄ è null.
Produci n = make_tuple_node(new HCoord(0, pos[0]), lvl+1) , cioè la tupla n0·n1·...·nlvl. La tupla che identifica il nodo corrente nel g-nodo di livello lvl+1 in cui il messaggio si muoverà.
m’ = new PeerMessageForwarder.
m’.n = n.
m’.x̄ = x̄.
m’.lvl = lvl.
m’.pos = _pos.
m’.p_id = p_id.
m’.msg_id = un identificativo generato a caso per questo messaggio.
Calcola timeout_instradamento = f ( map_paths.i_peers_get_nodes_in_my_group(lvl + 1) ).
Prepara waiting_answer = new WaitingAnswer(null, (lvl,_pos) come PeerTupleGNode con top = lvl+1). Il fatto che l'istanza di IPeersRequest è a null fa in modo che i metodi remoti che ricevono le notifiche si comportano in modo adeguato. Sostanzialmente dovrebbe cambiare solo il fatto che quando si riceve la segnalazione di get_request si risponde sempre con l'eccezione PeersUnknownMessageError, anche se si è potuto recuperare l'istanza di WaitingAnswer. Sull'istanza di WaitingAnswer viene poi valorizzato il membro response con qualcosa diverso da null solo per indicare che il g-nodo partecipa.
waiting_answer_map[m’.msg_id] = waiting_answer.
IPeersManagerStub gwstub
IPeersManagerStub? failed = null
- While True:
- Try:
- Calcola gwstub = map_paths.i_peers_gateway(lvl, _pos, null, failed)
Se riceve l'eccezione PeersNonexistentDestinationError:
- Restituisci True. Rimuovi waiting_answer_map[m’.msg_id]. Termina algoritmo.
- Try:
- Esegue gwstub.forward_peer_message(m’).
Se riceve StubError o DeserializeError:
- failed = gwstub.
- Continua con la prossima iterazione del ciclo.
- Esci dal ciclo.
- Try:
- Try:
- Sta in attesa su waiting_answer.ch per max timeout_instradamento.
- Se waiting_answer.exclude_gnode ≠ null:
- Restituisce False. Rimuovi waiting_answer_map[m’.msg_id]. Termina algoritmo.
- Altrimenti-Se waiting_answer.non_participant_gnode ≠ null:
- # significa che abbiamo ricevuto notizia di un gnodo non partecipante.
waiting_answer.non_participant_gnode è un PeerTupleGNode che rappresenta un g-nodo h dentro il mio g-nodo di livello top.
- Se è visibile nella mia mappa, cioè se (lvl,top) non partecipa:
- Restituisci True. Rimuovi waiting_answer_map[m’.msg_id]. Termina algoritmo.
- Altrimenti:
- Restituisce False. Rimuovi waiting_answer_map[m’.msg_id]. Termina algoritmo.
- Altrimenti-Se waiting_answer.response ≠ null:
- # significa che abbiamo ricevuto il contatto e che lvl,_pos partecipa.
- Restituisce False. Rimuovi waiting_answer_map[m’.msg_id]. Termina algoritmo.
- Altrimenti:
- # significa che abbiamo ricevuto un nuovo valore in waiting_answer.min_target.
- Restituisce False. Rimuovi waiting_answer_map[m’.msg_id]. Termina algoritmo.
Se riceve l'eccezione TimeoutError:
- # dobbiamo trattare waiting_answer.min_target come da escludere.
- Restituisce False. Rimuovi waiting_answer_map[m’.msg_id]. Termina algoritmo.
Algoritmo di divulgazione della partecipazione
publish_my_participation
void publish_my_participation(p_id)
gn = make_tuple_gnode(new HCoord(0, pos[0]), levels). La tupla n0·n1·...·nlevels-1, che identifica il nodo corrente nella rete.
tempo_attesa = 300 secondi.
iterazioni = 5.
- While True (per sempre):
Se iterazioni > 0:
- Decrementa iterazioni di 1.
- Altrimenti:
- tempo_attesa = 1 giorno + random(1..24*60*60) secondi.
Prepara un IPeersMissingArcHandler missing_handler che in caso di invocazione esegua:
- Calcola tcp_stub = neighbors_factory.i_peers_get_tcp(missing_arc).
- Try:
- tcp_stub.set_participant(p_id, gn).
Se riceve StubError o DeserializeError:
- Ignora.
- Calcola br_stub = neighbors_factory.i_peers_get_broadcast(missing_handler).
- Try:
- br_stub.set_participant(p_id, gn).
Se riceve StubError o DeserializeError:
- Ignora.
- Aspetta tempo_attesa.
set_participant
void set_participant(int p_id, PeerTupleGNode gn)
E' già stata istanziata lista_recenti un ArrayList di HCoord.
- Se services.has_key(p_id) AND NOT services[p_id].p_is_optional:
- Ignora il messaggio. Algoritmo termina.
int case, HCoord ret.
- Calcola convert_tuple_gnode(gn, out case, out ret).
- Se case = 1:
- Cioè gn rappresenta un mio g-nodo.
- Ignora il messaggio. Algoritmo termina.
- Altrimenti:
- Cioè gn rappresenta un g-nodo a cui io non appartengo, ed ho già calcolato in ret il g-nodo visibile nella mia topologia in cui gn si trova.
- Se ret ∈ lista_recenti:
- Ignora il messaggio. Algoritmo termina.
- Altrimenti:
- lista_recenti.add(ret).
- Se NOT participant_maps.has_key(p_id):
participant_maps[p_id] = new ParticipantMap().
- participant_maps[p_id].participant_list.add(ret).
ret_gn = make_tuple_gnode(ret, levels)
Prepara un IPeersMissingArcHandler missing_handler che in caso di invocazione esegua:
- Calcola tcp_stub = neighbors_factory.i_peers_get_tcp(missing_arc).
- Try:
- tcp_stub.set_participant(p_id, ret_gn).
Se riceve StubError o DeserializeError:
- Ignora.
- Calcola br_stub = neighbors_factory.i_peers_get_broadcast(missing_handler).
- Try:
- br_stub.set_participant(p_id, ret_gn).
Se riceve StubError o DeserializeError:
- Ignora.
- Svolgi quanto segue in una nuova tasklet portando dietro ret:
- Aspetta 60 secondi.
- lista_recenti.remove(ret).
Algoritmi per il mantenimento di un database distribuito
Per migliorare la persistenza dei dati
bool begin_replica(q, p_id, x̄, r, timeout_exec, out IPeersResponse? resp, out IPeersContinuation cont)
- Gli argomenti sono:
int q: il numero delle repliche richieste,
int p_id,
PeerTupleNode x̄: la tupla dell'hash della chiave del record, cioè hp ( k ),
IPeersRequest r: la richiesta di replicare la coppia k,val ,
int timeout_exec,
resp viene valorizzato con la risposta o null;
cont è un oggetto di cui all'esterno si sa solo che implementa l'interfaccia vuota IPeersContinuation.
lista_repliche = new List di PeerTupleNode.
exclude_tuple_list = new PeerTupleGNodeContainer(x̄.tuple.size).
- cont = {q, p_id, x̄, r, timeout_exec, lista_repliche, exclude_tuple_list}.
- Return next_replica(cont, out resp).
bool next_replica(IPeersContinuation cont, out IPeersResponse? resp)
- resp = null.
- Se cont.lista_repliche.size ≥ cont.q:
- Return False.
PeerTupleNode respondant;
- ret = contact_peer(cont.p_id, cont.x̄, cont.r, cont.timeout_exec, True, out respondant, cont.exclude_tuple_list).
Se si riceve l'eccezione PeersNoParticipantsInNetworkError o PeersDatabaseError:
Return False. L'eccezione PeersDatabaseError va vista come "OUT_OF_MEMORY" essendo la replica una operazione di sovrascrittura o inserimento.
- resp = ret.
- aggiungi respondant a cont.lista_repliche.
- aggiungi respondant a cont.exclude_tuple_list.
Return cont.lista_repliche.size < cont.q.
Per garantire la coerenza dei dati
Per garantire la coerenza dei dati e gestire l'esaustività e le limitazioni di memoria dei singoli nodi, gli algoritmi sviluppati sono illustrati nei seguenti documenti: