Bluesky spart Millionen Datenbankabfragen mit Bloom-Filtern, die nur einen Hash benötigen
One Hash Bloom Filters
Bloom-Filter beantworten die Frage „Ist X in dieser Menge?“ mit „definitiv nicht“ oder „vielleicht“ und sparen so teure Festplattenzugriffe. Bei Bluesky verhindern sie Millionen von Scylla-Abfragen pro Sekunde. Ein neuer Ansatz von Lu et al. nutzt nur einen Hash, indem der Bit-Array in teilerfremde Partitionen aufgeteilt wird. Die Go-Implementierung gloom ist seit neun Monaten im Einsatz und nutzt Cache-Alignment sowie Sharding für minimale Latenz.
Die obige gelbe Linie hat eine Positivrate von etwa 1 %, was bedeutet, dass wir in 99 % der Fälle die Datenbankabfrage komplett überspringen können.
- aappleby
Das musst du eigentlich gar nicht machen – du kannst bei einer Tabelle mit Zweierpotenz-Größe bleiben und einfach den Hash-Wert sanft durchmischen, um jeden zusätzlichen Bit-Index zu erhalten.
(Quelle – ich habe MurmurHash/SMHasher geschrieben und das Obige in meinen eigenen Bloom-Filtern und Cuckoo-Hash-Tabellen verwendet)
- FreakLegion
NB: Hier tauschst du eine nicht vernachlässigbare Speichereffizienz ein, die sich verschlechtert, je niedriger du die False-Positive-Rate setzt. Partitionierung bedeutet ungleichmäßige Auslastungsraten über die Partitionen hinweg, und entweder akzeptierst du eine niedrige Auslastung (insgesamt größerer Filter) oder du hast so gut wie sicher heiße Blöcke (erhöhte False-Positive-Rate für bestimmte Partitionen).
- cperciva
Obwohl es viel billiger ist, als auf die Festplatte zu gehen, ist die Berechnung von k unabhängigen Hashes pro Schlüssel für sehr leistungsstarke Systeme immer noch etwas teuer.
Kommt darauf an, wie groß der Bloom-Filter ist. Die meisten Hashes sind groß und ihre Bits sind unabhängig.