Come memorizzare (e trovare) i valori aggiornati in una tabella hash distribuita?

4

Le tabelle hash distribuite sono un ottimo modo per archiviare dati immutabili in modo resiliente.

Tuttavia, mi chiedo come sarebbe possibile memorizzare nuove versioni di vecchi dati in questo sistema.

Poiché in una rete distribuita è impossibile fidarsi incondizionatamente dell'altra parte, è necessario un modo per garantire che un'altra parte non manipoli i dati memorizzati. Il modo più semplice per farlo è quello di memorizzare i valori dei dati sotto le chiavi generate da questi valori utilizzando una funzione di hash unidirezionale. Ciò significa che quando qualcuno vuole cambiare i dati, invalida la relazione tra valori chiave e valore di quei dati, che è facile da controllare.

Supponiamo che qualcuno memorizzi un documento nel DHT, ma in seguito abbia apportato alcune modifiche e desideri archiviare quella nuova versione. Come possono le altre persone connesse al DHT scoprire che esiste una nuova versione di questo documento? L'unica informazione che ho trovato su questo ha detto che un'idea sarebbe quella di archiviare i dati con versione così:

v1: hash(random_number) -> document1
v2: hash(key(v1)) -> document2
v3: hash(key(v2)) -> document3
...etc.

Quindi, per verificare se c'è una nuova versione, tutto ciò che un client dovrebbe fare è applicare l'algoritmo di hashing ancora una volta all'hash del valore corrente.

Svantaggio: questo approccio non ha la relazione tra chiave e valore, il che significa che un valore potrebbe essere modificato (da un server malevolo o da un man-in-the-middle) senza invalidare la chiave.

In che modo questi due approcci possono essere combinati? O c'è un modo diverso e migliore per gestirlo?

    
posta Qqwy 27.09.2015 - 12:12
fonte

3 risposte

6

Una volta stabilito che i client non possono essere considerati attendibili, è un dato di fatto che ogni valore è immutabile e ogni chiave è immutabile. E l'immutabilità è per sempre.

Questo a sua volta significa che questo non è un problema di archiviazione e ricerca di valori, è un problema di identificazione della chiave della versione più aggiornata di un valore, quindi è un versioning problema.

Quando cerchi di risolvere il problema della versione, devi prima chiedere di nuovo se puoi fidarti delle tue fonti.

  • Se puoi fidarti delle tue fonti, tutto ciò di cui hai bisogno è una soluzione semplice, quasi banale. Ciò potrebbe comportare:

    • Mappare le chiavi alle coppie di tasti effettivi e numeri di versione, in modo che tu possa elencarli tutti per trovare quello con il numero di versione più alto.

    • Mappare le chiavi ai tasti successore in modo che, dato un tasto "corrente", puoi attraversare la catena e trovare la chiave che corrisponde all'ultima versione.

  • Se non ti fidi delle tue fonti, allora devi utilizzare un meccanismo di voto. Questo è un argomento che ha ricevuto molte ricerche, sotto il vasto titolo di "Consenso". Quindi, un buon punto di partenza sarebbe l'articolo wikipedia pertinente: Wikipedia: Consenso (Informatica)

risposta data 06.10.2015 - 10:28
fonte
2

Ci sono modi in cui questo può essere risolto, e puoi renderlo complesso come vuoi. Il modo più semplice è quello di autenticare gli altri server e consentire ai server di fidarsi l'uno dell'altro se sono autenticati. SSL client e server autenticato per la connessione di rete otterrebbe questo.

Potresti anche fare un sistema di autenticazione federato, in cui chiedi a terze parti fidate di garantire altri server. Questo può essere ottenuto anche utilizzando certificati SSL sia sul client che sul server, e autenticato che i certificati sono firmati da un certificato attendibile.

Se sei veramente dopo una cache di scalabilità su Internet, l'ultima opzione è quella di avere il voto sulla cache, basato sulla risposta della maggioranza, e confida che ci siano più server onesti che server disonesti nella rete. Tuttavia, quando si ha una situazione in cui non ci si fida dei server, è comunque necessario risolvere il problema dal punto di vista del cliente ... in che modo il client si fida dei server per inviare i propri dati? Come fa il cliente a sapere che i loro dati sono distribuiti a un numero sufficiente di server affidabili che i loro dati sono accettati. Ora avendo letto tutto questo, consultate l'ipotesi della PAC e rendetevi conto che se andate su questa rotta, dovete avere tolleranza della partizione perché non conoscete i server che fanno parte del sistema. Devi avere disponibilità, il che significa che la cosa che devi sacrificare è la coerenza.

    
risposta data 05.10.2015 - 19:22
fonte
2

Vuoi

  1. Un client connesso a un numero qualsiasi di server (dannosi).
  2. Una persona autorizzata per creare nuovi valori, connessi a server (dannosi).

Le tue ipotesi sono (correggimi se ho torto):

  1. I valori sono così grandi che hanno bisogno di identificatori (hash).
  2. Il cliente e la persona non possono comunicare direttamente.

Senza ulteriori ipotesi il cliente non può essere sicuro di alcun valore della persona. Possibili nuovi presupposti sono:

  1. La persona firma i valori
  2. Nuovi valori possono essere creati da chiunque
  3. La persona non è maliziosa
  4. La persona può raggiungere il cliente
  5. La persona e il client hanno orologi sincroni
  6. Il client può identificare i messaggi della persona
  7. Un messaggio dalla persona al cliente può raggiungere il client entro un tempo noto
  8. Il cliente non ha bisogno di raggiungere la persona
  9. Il cliente non può raggiungere la persona
  10. I valori hanno relazione con l'ora del client
  11. Un nuovo valore rende i valori precedenti non validi
  12. Un cliente deve conoscere tutti i valori di una persona
  13. Il client può sapere che un valore non è valido senza avere un nuovo valore
  14. I valori sono validi solo per un intervallo di tempo

Per favore dimmi quali supposizioni hai escluso. Per favore dimmi quali sono le tue ipotesi. Per favore dimmi quali presupposti non ti interessano. Ci potrebbe essere anche di più.

    
risposta data 07.10.2015 - 12:46
fonte

Leggi altre domande sui tag