Facebook gibt den Hash Table F14 als Open Source frei

Als Teil von Facebooks C++-Library Folly steht die Hashtabelle Entwicklern ab sofort ebenfalls quelloffen zur Verfügung.

In Pocket speichern vorlesen Druckansicht
Facebook gibt den Hash Table F14 als Open Source frei

(Bild: Facebook)

Lesezeit: 2 Min.
Von
  • Matthias Parbel

Entwicklern, die Hashing für Datenbankanwendungen oder andere Applikationen einsetzen, bietet sich mit der in Facebooks C++-Library Folly enthaltenen Hashtabelle F14 nun eine weitere Option an: Facebook hat F14 als Open Source freigegeben. Der von Nathan Bronson und Xiao Shi entwickelte Hash-Algorithmus verspricht höhere Performance und eine effizientere Speicherauslastung gegenüber vergleichbaren Ansätzen. Mehrere Speicherlayouts für verschiedene Anwendungsszenarien sollen sicherstellen, dass jeweils möglichst viele Daten eines Programms in den Cache geladen werden können, um den Speicherbedarf zu reduzieren.

Der Gefahr der Entartung durch Kollisionen, die sich bei anhaltendem Wachstum der Datenmenge zwangsläufig ergeben – sofern die Tabelle nicht vergrößert und jedes darin enthaltene Element neu gehasht wird – begegnet F14 durch gebündeltes Key Mapping. Statt die Schlüssel lediglich in einen einzigen Slot zu mappen, nutzt Facebook Blöcke von Slots (sogenannte Chunks). Mit Vektor-Instruktionen wie SSE2 (x86_64) oder NEON (aarch64) lassen sich die Chunks durchsuchen und alle Slots gleichzeitig filtern.

F14 verwendet 14 Slots pro Chunk, da die Facebook-Entwickler bei dieser Anzahl ein optimales Verhältnis zwischen dem Cache Alignment und der Kollisionsrate ermittelt haben. Im Fall eines Chunk Overflow oder wenn zwei Schlüssel beide die Filterstufe passieren, führt F14 eine Kollisionsauflösung durch. Dieser zweistufige Suchvorgang (Double Hashing) erfordert zunächst zwar mehr Zeit als sie andere Hash-Algorithmen benötigen, räumen die Facebook-Entwickler ein, aber F14 arbeite insgesamt dennoch schneller, da es in der Praxis seltener zu Störungen der Instruction Pipeline durch Kollisionen komme.

Eine ausführliche Beschreibung des Hash-Algorithmus sowie eine Einordnung seiner Leistungsfähigkeit findet sich im Blogbeitrag zur Freigabe von F14. Der Code steht im Rahmen der Folly-Projektwebsite auf GitHub bereit. (map)