Generic Error-Free Bloom Filter Synchronization Library

Motivation

Viele Anwendungen erfordern es, zwei Sets von Daten zwischen zwei Geräten zu synchronisieren. Beispiele sind die Filesynchronisation bei inkrementellen Backup-Systemen oder die Synchronisierung von Datenbanken und verteilten Filesystemen oder auch der Abgleich der Bundle Storages von zwei DTN Knoten. Hierbei ist das Differenzset zwischen zwei Mengen zu bestimmen, um herauszufinden welche Elemente des einen Set im anderen nicht vorhanden sind. Dieses Problem ist als Set Reconcillation bekannt.

Da eine Liste aller Elemente bei großen Sets sehr umfangreich ist, existieren effizientere approximative Methoden, wie zum Beispiel Bloom Filter, um Elemente des Differenzsets zu bestimmen. Viele Anwendungen können jedoch Fehler, die durch approximative Methoden entstehen, nicht tolerieren sondern benötigen fehlerlose Verfahren. Interessant sind daher Set Reconcillation Methoden die deterministisch sind, zustandslos (stateless) arbeiten und dabei dennoch effizient sind: Eine Voraussetzung hierbei ist, dass nichts über das Set des Kommunikationspartners bekannt sein muss, um einen Abgleich durchzuführen. Bei zustandsbehafteten Synchronisationen, die z.B. auf der Übertragung von Inkrementen beruhen, muss der Zustand des Gegenübers stets bekannt sein. Zustandslose Synchronisationsverfahren haben diesen Nachteil nicht und eignen sich daher zum Beispiel um zustandsbehaftete Synchronisationsverfahren zu starten (Bootstrapping), oder um einen konsistenten Zustand herzustellen, wenn Fehler aufgetreten sind.

Aufgabenstellung

In dieser Arbeit soll eine generische Library zum Abgleich zweier Sets auf Basis der um einen Trie erweiterten Bloom Filter erstellt werden. Folgende generelle Anforderungen bestehen an die Library:

• Sie muss in C (oder C++) entwickelt werden werden
• Sie soll auch auf Embedded Plattformen wie OpenWRT problemlos nutzbar sein
• Abhängigkeiten zu externen Libraries sind mit Blick auf die Embedded Plattformen auf entsprechend geeignete und gebräuchliche Libraries zu reduzieren
• Zur Kommunikation soll die Library keine eigenen Funktionen bereitstellen. Stattdessen soll ein geeignetes Interface es externen Programmen ermöglichen, eigene Kommunikationsverfahren zu implementieren
• Die Größe der zu verwaltenden Sets soll soweit möglich nicht durch den Arbeitsspeicher limitiert sein. Es ist das Ziel, Datensets mit mehreren 10 Millionen Einträgen oder mehr verwalten zu können

Die Geschwindigkeit der Library soll mit Testdaten evaluiert werden. Ein Profiling soll zeigen, welche Teile des Mechanismus die Laufzeit maßgeblich beeinflussen.

Die Library soll in einer bestehenden Anwendung eingesetzt werden oder diese ersetzen. Der erreichte Kommunikationsoverhead ist mit der ursprünglichen Anwendung zu vergleichen.

Zu möglichen Einsatzszenarien der Library ist eine Analyse anzufertigen. Hierbei können zum Beispiel Wege angedeutet werden, wie man den Mechanismus erweitern müsste, wenn es sich bei den zu synchronisierenden Sets um Daten handelt, deren Inhalt sich bei gleicher Identität ändert, oder Elemente die komplex strukturierte Metadaten enthalten (File Synchronisation). Ebenfalls erwähnenswert sind Anwendungsfälle wo es nicht um das Differenzset, sondern um die Schnittmenge geht, wie beispielsweise bei der Deduplikation von Daten.