CUBIT: Concurrent Updatable Bitmap Indexing

Zusammenfassung

Bitmap-Indizes sind für leseintensive analytische Workloads weit verbreitet, weil sie geclustert sind und effiziente Reads bei kleinem Speicherbedarf bieten. Aktualisierungen sind jedoch in der Regel ineffizient. Da analytische Anwendungen zunehmend mit transaktionalen Anwendungen verschmelzen und Hybrid Transactional/Analytical Processing (HTAP) entsteht, ist es wünschenswert, dass Bitmap-Indizes effiziente nebenläufige Echtzeit-Updates unterstützen. In diesem Beitrag schlagen wir Concurrent Updatable Bitmap indexing (CUBIT) vor: effiziente Echtzeit-Updates, die mit der Zahl genutzter CPU-Kerne skalieren und Anfragen nicht stören. Unser Entwurf stützt sich auf drei Prinzipien. Erstens verwenden wir eine horizontale bitweise Darstellung aktualisierter Bits, die effiziente atomare Updates ohne Sperren ganzer Bitvektoren ermöglicht. Zweitens schlagen wir einen leichtgewichtigen Snapshot-Mechanismus vor, der Anfragen auf getrennten Snapshots ausführt und eine wait-free Fortschrittsgarantie liefert. Drittens konsolidieren wir Updates latch-frei und bieten damit eine starke Fortschrittsgarantie. Unsere Auswertung zeigt, dass CUBIT einen 3- bis 16-fach höheren Durchsatz und eine 3- bis 220-fach niedrigere Latenz erreicht als moderne aktualisierbare Bitmap-Indizes. Die updatefreundliche Natur von CUBIT erweitert den Einsatzbereich von Bitmap-Indizierung. In Experimenten mit OLAP-Workloads und üblichen, gebündelten Updates überwindet CUBIT die Wartungsstillstandszeiten und übertrifft DuckDB auf TPC-H um das 1,2- bis 2,7-Fache. Bei HTAP-Workloads mit Echtzeit-Updates erreicht CUBIT eine 2- bis 11-fache Leistungsverbesserung gegenüber dem Stand der Technik.