• Netsukuku
• ita
• docs
• ModuloPeers
• DatabaseTTL

Modulo PeerServices - Database TTL

Implementiamo un servizio che mantiene un database distribuito. Ogni record in esso ha un Time To Live. Le chiavi sono in un set che può essere molto grande.

Ogni nodo partecipante può avere un limite di memoria, oltre il quale il nodo rifiuterà di immagazzinare altri record.

In questo servizio ipotiziamo che non ci siano vincoli per il client, cioè qualsiasi operazione è permessa (nei limiti del dominio delle chiavi e dei valori) senza alcun tipo di autorizzazione. Comunque risulterà facile implementare in un servizio analogo qualsiasi tipo di vincolo da parte del server; basterà codificare nella classe del valore di ritorno le eccezioni previste dal servizio.

Diamo per assunto che il lettore abbia già compreso negli altri documenti i concetti:

• Recupero di un record garantendo la coerenza del dato.

• Classe RequestWaitThenSendRecord.

• Tempo critico di coerenza.
• Interfaccia che la classe del servizio deve fornire che permetta di:
  • max_timeout_exec.
  • is_insert_request.
  • is_read_only_request.
  • is_update_request.
  • produrre risultato "NOT_FOUND" per una richiesta.

Operazione di inserimento

Il nodo q vuole inserire un record k=w nel database distribuito.

Ci sono 4 possibili esiti finali a questa richiesta:

1. Il nodo q viene informato che al momento nella rete non c'è nessun partecipante al servizio. Chiamiamolo esito "NO_PARTICIPANTS".

2. Il nodo q viene informato che la chiave k era libera e il record k=w è stato inserito. Chiamiamolo esito "OK".

3. Il nodo q viene informato che la chiave k è già valorizzata con il valore v. Chiamiamolo esito "NOT_FREE".

4. Il nodo q viene informato che la chiave k è libera ma la memoria nel database distribuito è esaurita. Chiamiamolo esito "OUT_OF_MEMORY"

Operazione di sola lettura

Il nodo q vuole leggere il valore del record per una chiave k nel database distribuito.

Ci sono 3 possibili esiti finali a questa richiesta:

1. Il nodo q viene informato che al momento nella rete non c'è nessun partecipante al servizio. Chiamiamolo esito "NO_PARTICIPANTS".

2. Il nodo q viene informato che il record per la chiave k è stato trovato e il suo valore è v. Chiamiamolo esito "OK".

3. Il nodo q viene informato che la chiave k non è presente nel database. Chiamiamolo esito "NOT_FOUND".

E' importante che l'operazione di sola lettura sia distinta dalle operazioni che possono diventare un aggiornamento. Diciamo possono dal punto di vista di un nodo n’ che, contattato durante il cammino di ricerca dell'​hash_node per la chiave k e ricevuta la richiesta, si rifiuta di elaborarla in quanto non esaustivo; infatti l'esito finale della richiesta dipende dal nodo servente n che la elaborerà. Questo nodo n’, se la richiesta che riceve può essere identificata come di "sola lettura", non necessiterà di resettare il tempo per cui si deve considerare non esaustivo per k.

Operazione di modifica

Il nodo q vuole modificare il valore o rimuovere il record per una chiave k nel database distribuito.

Ci sono 3 possibili esiti finali a questa richiesta:

1. Il nodo q viene informato che al momento nella rete non c'è nessun partecipante al servizio. Chiamiamolo esito "NO_PARTICIPANTS".

2. Il nodo q viene informato che il record per la chiave k è stato modificato/rimosso. Chiamiamolo esito "OK".

3. Il nodo q viene informato che la chiave k non è presente nel database. Chiamiamolo esito "NOT_FOUND".

Nodo servente esaustivo o non esaustivo

Un nodo n servente, che cioè partecipa attivamente al servizio, quando viene a conoscenza di una chiave k per la quale dovrebbe essere il detentore di un record (ad esempio perché riceve una richiesta di qualche tipo riferita alla chiave k), se il record per la chiave k non è presente nella sua memoria, si deve chiedere se può o non può asserire che il record per la chiave k non esiste nel database.

Ci riferiamo a questo quando diciamo che il nodo n è esaustivo o non esaustivo per la chiave k.

Se un nodo viene interrogato su una chiave k che non è nella sua memoria e per tale chiave si considera esaustivo, allora può asserire che il record per la chiave k non esiste nel database.

Se un nodo viene interrogato su una chiave k che non è nella sua memoria e per tale chiave si considera non esaustivo, allora non può asserire che il record non esiste.

Per gestire questo aspetto il nodo n fa uso di alcune strutture dati:

• Elenco di chiavi HashMap<Object,Timer> not_exhaustive_keys e per ogni chiave dell'elenco un relativo timer.

• Se il nodo riceve una richiesta relativa alla chiave k che non è nella sua memoria e la chiave k è nell'elenco not_exhaustive_keys e il suo timer non è scaduto, allora il nodo si ritiene non esaustivo per tale chiave. Se il relativo timer è scaduto tale chiave viene rimossa dall'elenco.

• Elenco di chiavi List<Object> not_found_keys.

• Se il nodo riceve una richiesta relativa alla chiave k che non è nella sua memoria e la chiave k è nell'elenco not_found_keys, allora il nodo si ritiene esaustivo per tale chiave.

• In nessun momento una stessa chiave k può appartenere ad entrambi gli elenchi suddetti. Inoltre, se una chiave k è nella memoria del nodo non può appartenere a nessuno degli elenchi suddetti.

• Stato di default e relativo timer.

• Si tratta di un flag che dice al nodo come considerarsi per una chiave k che non è nella sua memoria e nemmeno nell'elenco not_exhaustive_keys e nemmeno nell'elenco not_found_keys.

• Il timer si riferisce al tempo di validità dello stato di default non esaustivo. Cioè: quando per qualche determinato evento il nodo mette il suo stato di default a non esaustivo, allora imposta anche il timer al TTL dei record di questo servizio; quando il timer scade, automaticamente lo stato di default del nodo torna ad essere esaustivo.

• Si usa una sola variabile: Timer timer_default_not_exhaustive.

Il nodo n gestisce l'elenco not_exhaustive_keys in modo da memorizzare quando e per quanto tempo deve ritenersi non esaustivo per una data chiave k. Il nodo n è in grado di farlo perché le richieste per tale chiave giungono al nodo stesso e possono essere esaminate (ad esempio per vedere se sono di sola lettura o possono produrre un aggiornamento) prima che il nodo risponda rifiutando l'elaborazione. Se nessuna richiesta giunge per la chiave k entro il TTL dei record di questo servizio, allora il record se era presente nel database adesso non lo è più; per questo il singolo elemento della lista not_exhaustive_keys può essere rimosso dalla lista quando scade il suo timer.

Questo elenco non può crescere senza limite; però non si può permettere che il nodo si consideri esaustivo quando non lo è. Per questo, se l'elenco not_exhaustive_keys diventa troppo grande il nodo n mette il suo stato di default a non esaustivo per il tempo TTL dei record e può svuotare del tutto l'elenco not_exhaustive_keys. In seguito tornerà ad inserire singole chiavi nell'elenco not_exhaustive_keys mentre il timer dello stato di default andrà scorrendo.

Il nodo n gestisce anche l'elenco not_found_keys in modo da memorizzare quando deve ritenersi esaustivo per una data chiave k. Inserisce una chiave in questo elenco quando elabora una richiesta di rimozione per la chiave k oppure quando la procedura di recupero del record per la chiave k si conclude con un "NOT_FOUND". Questo elenco è una sorta di cache: se una chiave si trova in esso allora il nodo può rispondere senza costringere il client a ulteriori trasmissioni e attese, ma se non vi si trova e il nodo è non esaustivo per k allora rifiuterà l'elaborazione e il client giungerà comunque alla risposta corretta. Non si vuole far crescere la lista senza limite, ma allo stesso tempo si vuole tenere chiavi utili, quindi si mettono in testa alla lista gli elementi appena aggiunti e si rimuovono gli elementi in coda quando serve.

La gestione dell'elenco not_found_keys è indipendente dallo stato di default del nodo. Cioè, sebbene l'elenco abbia un effetto concreto solo quando lo stato di default è non esaustivo, comunque l'elenco non viene svuotato quando il nodo passa allo stato di default esaustivo.

Algoritmi

Nell'illustrare i seguenti algoritmi viene posta particolare attenzione alla gestione delle strutture dati not_exhaustive_keys, not_found_keys e timer_default_not_exhaustive.

Algoritmo di valutazione esaustivo per k:

bool is_exhaustive(k)

• Se k è in not_exhaustive_keys:

  • assert: k non è in not_found_keys.

  • Se not_exhaustive_keys[k].timer è scaduto:

    • Rimuovi k da not_exhaustive_keys.

  • Altrimenti:
    • Return False.

• Se k è in not_found_keys:

  • assert: k non è in not_exhaustive_keys.

  • Return True.

• Se timer_default_not_exhaustive è scaduto:

  • Return True.
• Altrimenti:
  • Return False.

Algoritmo di valutazione out of memory:

bool is_out_of_memory()

• Se my_records_size() + retrieving_keys.size >= max_records:

  • Return True.
• Altrimenti:
  • Return False.

Algoritmo di aggiunta k a not_exhaustive_keys:

void add_not_exhaustive(k)

• ttl è il tempo di vita di un record per questo servizio.

• max_not_exhaustive_keys è il numero massimo di chiavi nell'elenco not_exhaustive_keys.

• assert: k non è in not_found_keys.

• Se k è in not_exhaustive_keys:

  • Reimposta not_exhaustive_keys[k] = new Timer(ttl).

  • Return.

• Se not_exhaustive_keys.size < max_not_exhaustive_keys:

  • Aggiungi not_exhaustive_keys[k] = new Timer(ttl).

  • Return.

• Imposta timer_default_not_exhaustive = new Timer(ttl).

• Esegui not_exhaustive_keys.clear().

• Return.

Algoritmo di aggiunta k a not_found_keys:

void add_not_found(k)

• max_not_found_keys è il numero massimo di chiavi nell'elenco not_found_keys.

• assert: k non è in not_exhaustive_keys.

• Se k è in not_found_keys:

  • Esegui not_found_keys.remove(k).

• Se not_found_keys.size >= max_not_found_keys:

  • Esegui not_found_keys.remove_at(0).

• Esegui not_found_keys.add(k).

Algoritmo di rimozione di k da not_exhaustive_keys:

void remove_not_exhaustive(k)

• Se k è in not_exhaustive_keys:

  • Esegui not_exhaustive_keys.unset(k).

Algoritmo di rimozione di k da not_found_keys:

void remove_not_found(k)

• Se k è in not_found_keys:

  • Esegui not_found_keys.remove(k).

Algoritmo alla ricezione della richiesta:

IPeersResponse on_request(IPeersRequest r, int common_lvl) throws PeersRefuseExecutionError, PeersRedoFromStartError

• Se is_insert_request(r):

  • Object k = get_key_from_request(r).

  • Se my_records_contains(k):

    • assert: k non è in not_exhaustive_keys.

    • assert: k non è in not_found_keys.

    • Risponde con "NOT_FREE" e il valore attuale di k.

    • L'algoritmo termina.

  • Se is_exhaustive(k):

    • Se is_out_of_memory():

      • Esegui remove_not_found(k).

      • Esegui add_not_exhaustive(k).

      • Rilancia PeersRefuseExecutionError.OUT_OF_MEMORY.

      • L'algoritmo termina.
    • Altrimenti:

      • Esegui remove_not_found(k).

      • Esegui remove_not_exhaustive(k).

      • Elabora l'inserimento in memoria di k. Ottiene la risposta da restituire. res = execute(r).

      • Se not my_records_contains(k):

        • Esegui add_not_found(k).

      • Risponde con res.

      • L'algoritmo termina.
  • Altrimenti:

    • Se la chiave k è nell'elenco retrieving_keys, il quale gli associa un canale di comunicazione ch:

      • Aspetta sul canale di comunicazione ch fino a un massimo di max_timeout_exec(r) - 1000.

      • Rilancia PeersRedoFromStartError.

      • L'algoritmo termina.
    • Altrimenti:

      • Se not is_out_of_memory():

        • Esegui start_retrieve(k).

      • Esegui remove_not_found(k).

      • Esegui add_not_exhaustive(k).

      • Rilancia PeersRefuseExecutionError.NOT_EXHAUSTIVE.

      • L'algoritmo termina.

• Se is_read_only_request(r):

  • Object k = get_key_from_request(r).

  • Se my_records_contains(k):

    • assert: k non è in not_exhaustive_keys.

    • assert: k non è in not_found_keys.

    • Risponde con "OK" e il valore attuale di k.

    • L'algoritmo termina.

  • Se is_exhaustive(k):

    • Esegui add_not_found(k).

    • Risponde con "NOT_FOUND".
    • L'algoritmo termina.
  • Altrimenti:

    • Rilancia PeersRefuseExecutionError.NOT_EXHAUSTIVE.

    • L'algoritmo termina.

• Se r is RequestWaitThenSendRecord:

  • Object k = r.k.

  • Se not my_records_contains(k) e not is_exhaustive(k):

    • Rilancia PeersRefuseExecutionError.NOT_EXHAUSTIVE.

    • L'algoritmo termina.

  • Calcola δ il tempo critico di coerenza, basandosi sul numero approssimato di nodi nel minimo comune g-nodo tra il nodo corrente e quello del richiedente, cioè il proprio g-nodo di livello common_lvl.

  • Attende δ.

  • Se my_records_contains(k):

    • assert: k non è in not_exhaustive_keys.

    • assert: k non è in not_found_keys.

    • ret = new RequestWaitThenSendRecordResponse().

    • ret.record = tdd.get_record_for_key(k).

    • Return ret.

    • L'algoritmo termina.

  • Se is_exhaustive(k):

    • Esegui add_not_found(k).

    • Return new RequestWaitThenSendRecordNotFound(). Restituisce al richiedente l'eccezione NOT_FOUND.

    • L'algoritmo termina.
  • Altrimenti:

    • Rilancia PeersRedoFromStartError.

    • L'algoritmo termina.

• Se is_update_request(r):

  • Object k = get_key_from_request(r).

  • Se my_records_contains(k):

    • assert: k non è in not_exhaustive_keys.

    • assert: k non è in not_found_keys.

    • Elabora la richiesta di modifica per k. Ottiene la risposta da restituire. res = execute(r).

    • L'algoritmo termina.

  • Se is_exhaustive(k):

    • Esegui add_not_found(k).

    • Risponde con "NOT_FOUND".
    • L'algoritmo termina.
  • Altrimenti:

    • Se la chiave k è nell'elenco retrieving_keys, il quale gli associa un canale di comunicazione ch:

      • Aspetta sul canale di comunicazione ch fino a un massimo di max_timeout_exec(r) - 1000.

      • Rilancia PeersRedoFromStartError.

      • L'algoritmo termina.
    • Altrimenti:

      • Se not is_out_of_memory():

        • Esegui start_retrieve(k).

      • Esegui remove_not_found(k).

      • Esegui add_not_exhaustive(k).

      • Rilancia PeersRefuseExecutionError.NOT_EXHAUSTIVE.

      • L'algoritmo termina.

Algoritmo di avvio del recupero (in una nuova tasklet) del record per la chiave k:

void start_retrieve(k)

• Crea un canale di comunicazione ch.

• Mette la chiave k nell'elenco retrieving_keys, associandogli il canale ch.

• In una nuova tasklet:

  • Avvia il procedimento di recupero del record per la chiave k.

  • Si tratta di una richiesta di sola lettura (con attesa del tempo di coerenza) in cui il nodo n è il client e si auto-esclude come servente.

  • Gli esiti possono essere:
    • "NO_PARTICIPANTS" o "NOT_FOUND":

      • L'esito "NO_PARTICIPANTS" è come un "NOT_FOUND", visto che il nodo n è partecipante e la chiave k non è nella sua memoria.

      • Esegui remove_not_exhaustive(k).

      • Esegui add_not_found(k).

      • INtkdChannel temp_ch = retrieving_keys[k].

      • Esegui retrieving_keys.unset(k).

      • Invia un messaggio asincrono (senza schedulare altre tasklet) a tutti quelli che sono in attesa su temp_ch.

    • "OK":

      • Esegui remove_not_exhaustive(k).

      • Esegui remove_not_found(k).

      • Mette il record nella sua memoria.

      • INtkdChannel temp_ch = retrieving_keys[k].

      • Esegui retrieving_keys.unset(k).

      • Invia un messaggio asincrono (senza schedulare altre tasklet) a tutti quelli che sono in attesa su temp_ch.