I filtri Bloom sono una funzione di analisi delle informazioni. Questi consentono di determinare se un dato o un insieme di questi sono memorizzati all'interno di un database o di un insieme distribuito di dati. Le sue caratteristiche principali sono la sua estrema efficienza in questo compito. È per queste caratteristiche che trovano largo impiego nei sistemi dove è necessario verificare l'esistenza di un dato specifico all'interno di un vasto insieme di questi.
UUno degli strumenti più utili per analizzare le informazioni probabilistiche e unidirezionali sono i filtri bloom. Questi filtri sono strumenti o strumenti che ci consentono di analizzare grandi quantità di informazioni probabilistiche. Questo per sapere se un elemento o un dato fa parte di un insieme. Questa è una funzionalità estremamente utile nei momenti in cui dobbiamo gestire grandi volumi di dati. Soprattutto quando tali informazioni non possono essere elaborate manualmente rapidamente.
Ecco perché grazie ai filtri bloom, criptovalute come Bitcoin hanno la funzione di Borse SPV. Ma vediamo questa funzione anche in criptovalute come Ethereum dove ti consentono di cercare informazioni nel tuo blockchain in modo efficiente.
E questo grazie al fatto che i filtri Bloom ci permettono di avere solo due risultati: falsi positivi o negativi. Cioè, implementando i filtri bloom è possibile sapere in modo rapido ed efficiente se determinati elementi possono esistere in memoria o se sicuramente non esistono. I risultati falsi positivi rivelano la possibilità che un elemento o un dato possano far parte di un insieme. Mentre i risultati negativi concludono definitivamente che l'elemento o i dati non sono inclusi nel set valutato. Lo strumento a sua volta ci consente di escludere completamente i falsi negativi, il che facilita notevolmente l'analisi dei dati.
Ma cosa ha portato alla creazione dei filtri bloom? Qual è il rapporto di questi con il mondo della blockchain? Bene, lo vedremo di seguito.
Origine dei filtri di fioritura
I filtri Bloom sono stati progettati negli anni '70 dallo sviluppatore Burton Howard Bloom. Bloom, laureato in Informatica al MIT, ha progettato questi filtri come una struttura dati probabilistica efficiente in termini di spazio che ci consente di verificare se un elemento o un dato fa parte o meno di un insieme. L'obiettivo dopo la sua creazione era quello di creare uno strumento di classificazione dei dati attraverso l'applicazione di funzioni hash che restituissero un risultato o un'identificazione. Allo stesso tempo, consente di rispondere con certezza se l'elemento che si sta controllando non fa parte dell'insieme, o riflette che probabilmente è al suo interno.
Pertanto, il design di questi filtri Bloom consente di gestire database o informazioni di grandi dimensioni ad alta velocità. E allo stesso tempo viene fatto un uso efficiente dello spazio di archiviazione. Ciò è dovuto al fatto che i filtri bloom non richiedono di contenere o memorizzare gli elementi oi dati stessi, ma semplicemente controllare se sono o meno all'interno del set. Un'operazione di sola lettura dei dati che consente elevate prestazioni e ampie capacità di elaborazione delle informazioni.
Come sono configurati i filtri bloom?
I filtri Bloom hanno quella che è nota come struttura dati di matrice di input. Questo array ha una lunghezza o una capacità di archiviazione grande quanto necessario. Ciò significa che al momento della costruzione di un filtro bloom è possibile impostare la lunghezza del filtro, come richiesto. Definire quante voci verranno aggiunte alla struttura dati di base e quante funzioni hash Verranno utilizzati all'interno del filtro, associati a ciascuno di questi ingressi.
Allo stesso modo, al momento della sua progettazione è necessario tenerne conto l'intervallo di funzioni hash deve iniziare da 0 e terminare con il numero di voci esistenti meno 1. Cioè, se un filtro bloom è progettato per 10 ingressi, inizierà con il numero 0 e terminerà con il numero 9. Se uno è progettato per 20 ingressi, il filtro bloom inizierà dal numero 0 e finirà al numero 19. Una pratica di progettazione computazionale che cerca di ottimizzare al massimo le risorse di elaborazione dei filtri.
Allo stesso modo, quando l'insieme di input esistenti trova tutti i suoi valori a 0, significa che i dati non sono nel filtro bloom. Quindi è vuoto. Quindi, nel momento in cui inizi ad aggiungere dati o elementi al filtro, le informazioni verranno passate attraverso le rispettive funzioni hash che posizioneranno quelle informazioni nella posizione corrispondente all'interno del filtro bloom. Pertanto, queste posizioni rifletteranno il valore 1, indicando che contengono elementi già analizzati.
Da questi valori si costruisce il funzionamento dei filtri bloom che spiegheremo in dettaglio di seguito.
Come funzionano i filtri bloom
Quindi, una volta configurato il filtro bloom, possiamo iniziare a verificare se un elemento fa parte o meno dell'insieme. Per ottenere ciò, il processo da seguire inizia con il passaggio dell'input di dati desiderato all'algoritmo del filtro bloom. Cioè, prendiamo i dati dal sistema e li elaboriamo utilizzando le funzioni hash del sistema. Di conseguenza, queste funzioni hash restituiranno due posizioni.
Questi hash e le posizioni che restituiscono di conseguenza vengono archiviati e correlati ai dati che li originano. Pertanto, il filtro continua a raccogliere informazioni, applicando funzioni hash su di esse e memorizzando i risultati del suo funzionamento. Tuttavia, questo processo ha una procedura aggiuntiva che massimizza la sua efficienza e migliora il tempo di risposta dei sistemi che applicano questo tipo di filtro alle loro strutture.
Innanzitutto, se i dati che sono stati passati al filtro passano attraverso le funzioni hash e restituiscono posizioni con valori diversi da 0, l'elemento è all'interno dell'insieme. Questo è ciò che è noto come positivo che indica l'esistenza di quell'elemento nell'insieme. Può anche essere il caso in cui gli hash restituiscono risultati con valori diversi.
Al contrario, se una o entrambe le posizioni mostrano un valore di 0, l'elemento non è sicuramente all'interno dell'insieme. Un'altra situazione prevista dall'algoritmo e che si chiama negativa o falsa positiva. Questo risultato è definitivo o conclusivo poiché i filtri bloom non daranno mai falsi negativi. Cioè, se l'algoritmo di un filtro bloom rileva un negativo o un falso positivo, questa informazione non è sicuramente nel set di dati analizzato.
D'altra parte, quando si configura un filtro bloom è molto importante definire il numero di bit e le funzioni hash che verranno applicate. Poiché un numero maggiore di funzioni hash, il tasso di errore viene notevolmente ridotto, quindi la probabilità di ottenere risultati falsi positivi sarà inferiore. Allo stesso modo, una volta che il set di bit del filtro bloom è completamente riempito, i dati inseriti non possono essere cancellati. Questo per non provocare la comparsa di falsi negativi nel filtro.
Quanto sono importanti i falsi positivi e i negativi nei filtri bloom?
L'importanza degli stati falsi positivi e negativi dei filtri bloom risiede nell'efficienza. Come abbiamo già accennato, i filtri bloom sono programmati per tenere conto di entrambi gli stati. E nel caso in cui vengano presentati, possiamo intraprendere le azioni pertinenti per dare una risposta appropriata.
Ad esempio, se lavoriamo con un sistema di archiviazione dati per generare una cache, un filtro bloom è di grande aiuto. Questo grazie al fatto che ogni volta che il sistema riceve un dato, quello che dobbiamo fare è verificare se tali dati non sono nei dati che abbiamo memorizzato nella cache. Quindi, se introduciamo questi dati e il filtro bloom restituisce un negativo o un falso positivo, possiamo essere sicuri che questi dati non si trovano nel set di informazioni che gestiamo. A quel punto, possiamo procedere a memorizzare questi nuovi dati nella cache in modo da potervi accedere in seguito in modo rapido ed efficiente.
Se, d'altra parte, il filtro bloom restituisce un risultato positivo, possiamo semplicemente scartare la memorizzazione delle informazioni e lavorare con ciò che abbiamo nella cache, dando un migliore accesso alle informazioni e risparmiando così preziose risorse di calcolo.
Questo tipo di operazione non è estranea al software che utilizziamo quotidianamente. Ad esempio, i browser Web utilizzano la cache memorizzata sui nostri dischi rigidi per darci accesso a determinate risorse rapidamente, rispetto alla consultazione di tali dati online. I database dei server e altri sistemi che gestiscono enormi quantità di dati utilizzano anche filtri bloom o algoritmi simili per migliorare l'efficienza delle risposte e della gestione dei dati.
Funzioni hash all'interno dei filtri bloom
Quando si configura un filtro bloom, è necessario utilizzare funzioni hash indipendenti e distribuite in modo uniforme. Queste funzioni hash consentono di assegnare un identificatore a qualsiasi tipo di dati, che può essere utilizzato per indicizzare o confrontare tali dati all'interno di un set.
Quando parliamo di funzioni hash parliamo del noto SHA-256, MD5 o di altre funzioni come CRC32. Tuttavia, nei filtri in fiore bisogna stare attenti. L'uso di molte funzioni hash aggiunge sicurezza ma lo rende anche più complesso e lento, quindi le funzioni dovrebbero essere scelte in modo tale che le loro capacità siano pienamente sfruttate.
Da parte sua, la caratteristica unidirezionale delle funzioni hash consente di determinare o creare un identificatore da uno o più dati, ma non è possibile eseguire il processo opposto. Quindi, se un utente scopre un identificatore, non sarà in grado di sapere quali sono i dati o gli elementi ad esso correlati.
Vantaggi e svantaggi dell'utilizzo del filtro bloom
Vantaggi
- I filtri bloom, non archiviando un set di dati in quanto tale, sono più efficienti in termini di utilizzo dello spazio di archiviazione. Dal momento che salvano solo se un'informazione o un elemento esiste o meno all'interno del filtro bloom.
- Allo stesso modo, questa funzione consente la verifica dei dati o degli elementi può essere eseguita in modo molto più rapido ed efficiente. Anche se si deve anche tenere conto che maggiore è il numero di funzioni hash, maggiore è il tempo richiesto dal filtro bloom per verificare l'esistenza degli elementi o dei dati.
- come i filtri bloom utilizzano il concetto di hashing unidirezionale. Se un utente vi accede, non sarà in grado di conoscere direttamente nessuna delle informazioni contenute in questi filtri.
Svantaggi
- Questi strumenti non restituire i dati verificato. Invece ti permettono solo di controllare se esistono o meno.
- Quando si ottengono risultati positivi, si può solo presumere che probabilmente siano corretti. Non si può essere certi o completamente certi che i dati positivi facciano parte del tutto. Contrariamente a quanto accade in caso di esito negativo. Dove puoi avere una risposta o un risultato finale decisivo.
- Quando si progetta il filtro bloom, è necessario assegnargli una dimensione, indipendentemente dal fatto che si tratti di pochi bit o milioni di bit. Una volta designata una dimensione, non si ridurrà o crescerà più di quanto stabilito in precedenza. Pertanto, affinché il filtro bloom sia efficiente, è necessario definire o essere chiari in anticipo quanti dati verranno aggiunti. Pertanto, se queste informazioni non sono note, è probabile che un filtro bloom venga progettato con pochissimi elementi che non siano altrettanto efficaci per la gestione delle informazioni desiderate. Oppure può essere il caso in cui viene progettato un filtro bloom molto grande che richiede uno spazio di archiviazione molto ampio per gestire la piccola quantità di informazioni. Il che risulterebbe in uno spreco di spazio.
Casi d'uso dei filtri Bloom
Criptovalute: Bitcoin ed Ethereum
Il sistema Bitcoin utilizza filtri bloom per velocizzare la sincronizzazione dei portafogli o borsellini SPV; che consentono loro di specificare solo le transazioni per le quali desiderano ricevere gli aggiornamenti di sistema. Formando un insieme di transazioni che possono trasmettere ai nodi completi della rete. Lì puoi controllare questi filtri. Quindi ricevere la conferma dell'aggiunta o meno di questo insieme di transazioni alla catena. Non è necessario gestire una copia completa della blockchain. In Bitcoin questa funzionalità viene modificata dai blocchi compatti menzionati in BIP-158.
Da parte sua, la rete Ethereum utilizza filtri bloom come file meccanismo attraverso il quale puoi trovare i log all'interno della tua blockchain. Pertanto, implementando questi filtri, puoi facilmente cercare gli eventi che si sono verificati all'interno del sistema Ethereum. Senza sovraccaricarlo gestendo informazioni eccessive. La creazione di applicazioni può gestire queste informazioni in modo molto più efficiente. Pur non richiedendo una grande quantità di spazio di archiviazione. Poiché con i filtri bloom non è necessario memorizzare dati che potrebbero essere duplicati all'interno del sistema.
In Ethereum, quando un blocco viene generato e verificato, l'indirizzo del contratto ei campi indicizzati dei record vengono aggiunti a un filtro bloom. Questo filtro si trova nell'intestazione del blocco. Quindi, se un'applicazione vuole trovare tutte le voci di registro, il nodo dovrebbe scansionare solo l'intestazione. In questo modo puoi riconoscere se i dati richiesti sono presenti o meno. Pertanto, questi elementi non vengono aggiunti al blocco in quanto tali, al fine di risparmiare spazio di archiviazione.
Reti e canali di informazione
Un'altra importante implementazione dei filtri Bloom consente alle reti o ai canali di informazione di poter fornire consigli sugli articoli agli utenti. Consentendo che questi non si ripetano. Vale a dire, puoi scoprire quali articoli ha letto un utente per consigliare quelli che non ha ancora visto.
Allo stesso modo, i grandi centri di distribuzione di dati e contenuti (CDN) utilizzano filtri bloom per massimizzare l'efficienza dell'archiviazione dei dati e dell'uso della rete, evitando che elementi ripetuti o poco utilizzati diventino parte dei loro sistemi sovraccaricandoli. Ciò include aziende come Akamai, Namecheap CDN, Fastly o Cloudflare.