Differences between revisions 6 and 41 (spanning 35 versions)
Revision 6 as of 2015-08-15 17:04:42
Size: 9405
Editor: lukisi
Comment:
Revision 41 as of 2015-10-25 07:43:52
Size: 8379
Editor: lukisi
Comment:
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 IPeersResponse? 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 IPeersResponse? resp) === '''bool next_replica(IPeersContinuation cont, out IPeersResponse? resp)'''
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 IPeersResponse? 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 = null.
 * 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 IPeersResponse? resp) ===
 * resp = null.
 * ''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 = 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:
    • 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 : 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:

Netsukuku/ita/docs/ModuloPeers/AppuntiAlgo2 (last edited 2015-11-28 11:14:43 by lukisi)