Wiederbelebung

Revivification in Tsavorite bezieht sich auf die Wiederverwendung ("Revivification") von Tombstoned (gelöschten) Datensätzen sowie von In-Memory-Quellendatensätzen für RCUs, die durch Upsert oder RMW durchgeführt werden. Dies minimiert das Log-Wachstum (und den ungenutzten Speicherplatz) für Szenarien mit vielen Löschungen. Es wird in den folgenden Fällen verwendet

• Ein Upsert, RMW oder Delete, der einen neuen Datensatz hinzufügt
• CopyToTail aus Read oder RMW, das IO durchführte (oder ein Lesen aus dem unveränderlichen Bereich des Logs, das nach Tail kopiert wird)
• Revivification wird *nicht* für den ReadCache verwendet

Es gibt zwei Formen der Revivification

• In-Chain: Tombstoned-Datensätze verbleiben in der Hash-Kette. Ein nachfolgender Upsert oder RMW desselben Schlüssels belebt den Datensatz wieder, wenn er eine ausreichende Wertlänge hat.
• FreeList: Eine Freiliste wird gepflegt, und Datensätze, die Tombstoned sind und sich am Ende der Hash-Kette befinden (direkt von der Hashtabelle aus verwiesen), werden aus der Hash-Kette entfernt und in einer Freiliste (einem in Bins unterteilten (nach Zweierpotenzen, standardmäßig), mehrsegmentigen Satz von Rundpuffern) gehalten.

Diese sind getrennt von der Wiederverwendung eines Datensatzes aufgrund einer RETRY-Rückgabe von CreateNewRecordXxx. In diesem Fall wird die Datensatzadresse im PendingContext gespeichert und CreateNewRecordXxx gibt entweder RETRY_LATER oder RETRY_NOW zurück; wenn CreateNewRecordXxx erneut versucht wird, wird dieser Datensatz abgerufen (wenn die Länge noch ausreicht und er nicht unter die minimal erforderliche Adresse gefallen ist). Die Wiederverwendung durch Retry ist immer aktiviert; Revivification möglicherweise nicht.

Externe Schnittstelle

Dieser Abschnitt beschreibt die externe API und die Kommandozeilenargumente für Revivification.

RevivificationSettings

Diese Struktur gibt an, ob Revivification aktiv sein soll

• EnableRevivification: Wenn dies wahr ist, wird zumindest In-Chain-Revivification durchgeführt; andernfalls wird keine Datensatz-Revivification durchgeführt (aber Retry-Wiederverwendung weiterhin).
• FreeListBins: Wenn dieses Array von RevivificationBin nicht null ist, dann wird Revivification eine Freiliste von Datensätzen beinhalten, wie unten definiert.
• SearchNextHigherBin: Standardmäßig durchsuchen wir bei der Suche nach FreeRecords nur den Bin für die angegebene Größe. Wenn dies gesetzt ist, wird, wenn keine Datensätze im anfänglichen Bin vorhanden sind, auch der nächsthöhere Bin durchsucht.
• RevivifiableFraction: Es kann wünschenswert sein, einen Datensatz, der zu nahe an der ReadOnlyAddress liegt, nicht zu verwenden; einige Apps werden es vorziehen, dass ein neu eingefügter Datensatz so lange wie möglich im veränderlichen Bereich verbleibt. RevivifiableFraction begrenzt den zulässigen Bereich der Revivification auf den Bruchteil des Speichers unmittelbar unter der TailAddress; er hat dieselbe Semantik wie LogSettings.MutablePercent und kann nicht größer als diese sein. Wenn beispielsweise RevivifiableFraction .2 ist, TailAddress 100.000 und HeadAddress 50.000, dann sind die 10.000 Datensätze, die dem Tail am nächsten liegen, für die Wiederverwendung zulässig. Dies geschieht auf Adressraum-Basis, nicht auf Datensatzanzahl, sodass die tatsächliche Anzahl der Datensätze, die revivifiziert werden können, bei Datensätzen mit variabler Länge variiert.
• RestoreDeletedRecordsIfBinIsFull Gelöschte Datensätze, die einem RevivificationBin hinzugefügt werden sollen, werden aus der Hash-Kette gestrichen. Wenn der Bin voll ist, steuert diese Option, ob der Datensatz (falls möglich) in die Hash-Kette zurückgeführt wird. Dies bewahrt sie als In-Chain-revivifizierbare Datensätze, auf Kosten der möglichen Auslagerung des Datensatzes auf die Festplatte, während er Teil der Hash-Kette ist, und somit nur eine I/O durchführen zu müssen, um festzustellen, dass der Datensatz gelöscht und somit potenziell unnötig ist. Für Anwendungen, die dieselben Schlüssel wiederholt hinzufügen und löschen, sollte diese Option auf true gesetzt werden, wenn die FreeList verwendet wird.
• UseFreeRecordPoolForCopyToTail Bei expliziten CopyToTail-Operationen wie Kompaktierung, CopyToTail beim Lesen aus dem unveränderlichen In-Memory-Bereich oder Disk-IO steuert dies, ob die Zuweisung für die abgerufenen Datensätze aus dem FreeRecordPool erfolgen kann. Diese Operationen erfordern möglicherweise, dass die Datensätze am Ende des Logs zugewiesen werden, um so lange wie möglich im Speicher zu bleiben.

RevivificationBin

Diese Struktur enthält die Definition der Freilisten-Bins, die Listen von freien Adressen innerhalb eines bestimmten Größenbereichs sind.

• RecordSize: Die maximale Größe von Datensätzen in dieser Partition (die Mindestgröße ist entweder 16 oder die RecordSize des vorherigen Bins + 8). Diese sollten gemäß den erwarteten Datensatzgrößen für Ihre App partitioniert werden. Ignoriert, wenn TsavoriteKV feste Daten verwendet; in diesem Fall gibt es nur einen Bin für Datensätze mit fester Länge.
• NumberOfRecords: Die Anzahl der Datensätze (Adressen), die in diesem Bin gespeichert werden. Tsavorite unternimmt nach bestem Wissen und Gewissen den Versuch, den Bin in Segmente zu unterteilen, um sequentielle Suchen nach verschiedenen Größen zu reduzieren.
• BestFitScanLimit: Die maximale Anzahl von Einträgen, die nach dem Finden von First Fit nach dem besten passenden gesucht werden soll; kann der spezielle Wert UseFirstFit sein, um First-Fit zu verwenden. Ignoriert für Datentypen mit fester Länge.

GarnetServer.exe Kommandozeilenargumente

GarnetServer.exe unterstützt die folgenden Kommandozeilenargumente für Revivification

• --reviv: Eine Abkürzung, um Revivification mit Standard-Bins in Zweierpotenzgrößen anzugeben. Dieser Standard kann durch --reviv-in-chain-only oder durch die Kombination von --reviv-bin-record-sizes und --reviv-bin-record-counts überschrieben werden.
• --reviv-bin-record-sizes: Für den Hauptspeicher die Größen von Datensätzen in jedem RevivificationBin, in aufsteigender Reihenfolge. Überschreibt den Standard --reviv; kann nicht mit --reviv-in-chain-only verwendet werden.
• --reviv-bin-record-counts: Für den Hauptspeicher die Anzahl der Datensätze in jedem Bin
  • Standard (nicht angegeben): Wenn reviv-bin-record-sizes angegeben ist, hat jeder Bin RevivificationBin.DefaultRecordsPerBin Datensätze.
  • Eine Zahl: Wenn --reviv-bin-record-sizes angegeben ist, haben alle Bins diese Anzahl von Datensätzen, andernfalls Fehler.
  • Mehrere durch Kommas getrennte Zahlen: Wenn reviv-bin-record-sizes angegeben ist, muss es die gleiche Größe wie dieses Array haben, andernfalls Fehler. Dies definiert die Anzahl der Datensätze pro Bin und überschreibt den Standard --reviv; kann nicht mit --reviv-in-chain-only verwendet werden.
• --reviv-fraction: Bruchteil des veränderlichen In-Memory-Log-Speichers, von der höchsten Log-Adresse abwärts bis zum schreibgeschützten Bereich, der für die Revivification zulässig ist. Gilt sowohl für den Haupt- als auch für den Objektspeicher.
• reviv-search-next-higher-bins: Sucht in dieser Anzahl von nächsthöheren Bins, wenn die Suche nicht im am besten passenden Bin erfüllt werden kann. Erfordert --reviv oder die Kombination von --reviv-bin-record-sizes und --reviv-bin-record-counts.
• --reviv-bin-best-fit-scan-limit: Anzahl der Datensätze, die nach dem Finden von First Fit nach dem besten passenden durchsucht werden sollen. Erfordert --reviv oder die Kombination von --reviv-bin-record-sizes und --reviv-bin-record-counts. Werte sind
  • RevivificationBin.UseFirstFit: Gibt die erste Adresse zurück, deren Datensatz groß genug ist, um die Anfrage zu erfüllen.
  • RevivificationBin.BestFitScanAll: Durchsucht alle Datensätze im Bin nach der besten Passform und stoppt frühzeitig, wenn wir eine exakte Übereinstimmung finden.
  • Andere Zahl: Begrenzt die Suche auf diese Anzahl von Datensätzen nach First Fit, bis zur Anzahl der Datensätze im Bin.
• --reviv-in-chain-only: Revivifiziert Tombstoned-Datensätze nur in Tag-Ketten (verwendet keine Freiliste). Kann nicht mit reviv-bin-record-sizes oder reviv-bin-record-counts verwendet werden. Gilt auch für den Objektspeicher.
• --reviv-obj-bin-record-count: Anzahl der Datensätze im einzigen Freidatensatz-Bin für den Objektspeicher. Der Objektspeicher hat nur einen einzigen Bin, im Gegensatz zum Hauptspeicher. Ignoriert, es sei denn, der Hauptspeicher verwendet die Freidatensatzliste.

Interne Implementierung

Dieser Abschnitt beschreibt das interne Design und die Implementierung von Revivification.

Pflegen zusätzlicher Wertlänge

Da variable Wertlängen wachsen und schrumpfen können, müssen wir die tatsächliche Länge des Werts zusätzlich zu den Wertdaten speichern. Datentypen mit fester Länge (einschließlich Objekte) müssen dies nicht speichern, da ihre Wertlänge sich nicht ändert.

Diese Speicherung von Datensatzlängen gilt sowohl für Revivification- als auch für Nicht-Revivification-Szenarien. ConcurrentWriter und InPlaceUpdater können die Datensatzgröße ändern und müssen wissen, wie viel Speicherplatz ihnen zur Verfügung steht, wenn sie später im Speicher wachsen können.

• In-Place-Updates in ConcurrentWriter und InPlaceUpdater verwenden dies, um die UpsertInfo und RMWInfo Eigenschaften UsedValueLength und FullValueLength zu setzen. Diese Eigenschaften werden unten erläutert.
• Revivification benötigt dies, um Anfragen vom FreeRecordPool zu erfüllen und dann auch, um die UpsertInfo und RMWInfo Eigenschaften UsedValueLength und FullValueLength zu setzen.

Die Speicherung der zusätzlichen Wertlänge erfolgt durch Aufrunden der verwendeten Wertlänge (der aktuellen Länge des Werts) auf eine ganze Zahl, und dann, wenn der zugewiesene Wertspeicher 4 Bytes oder mehr größer ist, wird die zusätzliche Länge bei (Beginn des Werts plus der aufgerundete verwendete Speicherplatz) gespeichert. Somit ist die volle Wertgröße die aufgerundete verwendete Wertgröße plus die zusätzliche Wertgröße. Wenn diese zusätzliche Länge gespeichert werden kann, wird das RecordInfo.Filler-Bit gesetzt, um anzuzeigen, dass die zusätzliche Länge vorhanden ist. Variable Längen-Log-Zuweisungen sind 8-Byte (RecordInfo Größe) ausgerichtet, so dass jede zusätzliche Länge, die kleiner als sizeof(int) ist, aus dieser Aufrundung abgeleitet werden kann.

Sicherstellen der Log-Integrität

Die Speicherung der zusätzlichen Wertlänge muss sorgfältig erfolgen, damit die Invariante beibehalten wird, dass ungenutzter Speicher genullt ist. Dies ist notwendig, da Log-Scans davon ausgehen, dass alle Nicht-Null-Daten, auf die sie stoßen, hinter der vorherigen Datensatzlänge ein gültiges RecordInfo-Header sind. Wenn die zusätzliche Länge vor dem Filler-Bit gesetzt wird oder das Filler-Bit gelöscht wird, bevor die zusätzliche Länge genullt wird, könnte ein Log-Scan kurzzeitig eine kurze Länge sehen, auf die Nicht-Null-Zusatzlänge stoßen und diese für ein gültiges RecordInfo halten. Die andere Richtung ist sicher: Das Filler-Bit kann gesetzt sein, aber die zusätzliche Länge ist Null. In diesem Fall sieht der Scan ein genulltes RecordInfo (RecordInfo.IsNull()) und geht von uninitialisiertem Speicher aus und springt um die Größe eines RecordInfo (8 Bytes) weiter.

Diese Invariante wird auch beim Verkleinern von variablen Wertlängen beibehalten, auch wenn das Filler-Bit nicht vorhanden ist. Wenn ein Wert verkleinert wird, müssen die Daten hinter der neuen (kürzeren) Größe genullt werden, bevor die kürzere Größe gesetzt wird.

Durch Kombination dieser beiden müssen wir beim Anpassen einer variablen Wertlänge

• Die zusätzliche Wertlänge löschen.
• Das Filler-Bit entfernen.
• Den zusätzlichen Wertdatenraum über die neue (kürzere) Größe hinaus nullen.
• Die neue (kürzere) Wertlänge setzen.
• Das Filler-Bit setzen.
• Die zusätzliche Wertlänge auf den korrekten neuen Wert setzen.

Die von Tsavorite bereitgestellte Implementierung für variable Längen ist SpanByte, und die Varianten von SpanByteFunctions machen hier das Richtige.

UpdateInfo Record-Längenmanagement

Für Datentypen mit variabler Länge verfügen die UpsertInfo, RMWInfo und DeleteInfo über zwei Felder, die den relevanten IFunctions-Callback über die Datensatzlänge informieren (ohne die Interna der Wertspeicherung kennen zu müssen).

• UsedValueLength: die Menge an Wertspeicher, die tatsächlich in Gebrauch ist.
• FullValueLength: Der volle zugewiesene Speicher für den Wert; dies ist die angeforderte Wertgröße für das anfängliche Einfügen des Datensatzes, aufgerundet auf 8-Byte-Ausrichtung.

Für SpanByte initialisiert die Überladung von VariableLenghtBlittableAllocator.GetValue mit (physicalAddress, physicalAddress + allocatedSize), die die Standard-SpanByte-Implementierung von IVariableLengthStructureSettings aufruft, den Wertspeicher tatsächlich zu einem gültigen SpanByte, das die angeforderte Wertlänge (bis zur maximalen Anzahl von Elementen, die hineinpassen) enthält. Andere Datentypen mit variabler Länge tun dies jedoch möglicherweise nicht.

DisposeForRevivification

Im Allgemeinen sind die IFunctions Dispose*-Funktionen für Daten bestimmt, die nicht in das Log geschrieben werden (normalerweise aufgrund eines CAS-Fehlers oder eines Fehlers in SingleWriter, InitialUpdater oder CopyUpdater). Daten, die in das Log geschrieben werden, werden von OnEvictionObserver gesehen, wenn einer registriert ist. Revivifizierte Datensätze werden jedoch aus dem Log entnommen und wiederverwendet; daher müssen sie der Anwendung die Möglichkeit geben, Dispose() auszuführen.

Um dies zu handhaben, wurde eine neue IFunctions-Methode DisposeForRevivification hinzugefügt. Wenn ein Datensatz in die Freiliste verschoben, aus der In-Chain- oder Freiliste revivifiziert oder aus Retry wiederverwendet wird, hat er einen Schlüssel und möglicherweise einen Wert. Tsavorite ruft DisposeForRevivification zweimal auf

• Zum Zeitpunkt der Aufnahme eines Datensatzes in die Freiliste. In diesem Fall ist der Parameter newKeySize -1, was anzeigt, dass wir ihn noch nicht wiederverwenden. Der Hauptgrund für diesen Aufruf ist die schnellstmögliche Freigabe nicht mehr benötigter Objekte. Für Nicht-Objekttypen fallen hierbei nur minimale Kosten an; Datentypen mit fester Länge tun nichts, und der einzige Garnet-Datentyp mit variabler Länge ist SpanByte, der zu diesem Zeitpunkt auch nichts tun muss (es gibt keine Zuweisungen).
  • DisposeForRevivification wird nicht für In-Chain-Tombstoned-Datensätze aufgerufen; der Schlüssel muss gültig bleiben, und der Wert wird bei der Auslagerung verworfen.
  • DisposeForRevivification wird nicht für Retry-recycelte Datensätze zum Zeitpunkt ihrer Aufnahme in den PendingContext aufgerufen, da sie beim Abrufen aufgerufen wird und dies immer geschieht (wir versuchen immer wieder).
• Zum Zeitpunkt der Wiederverwendung, sei es aus der Freiliste oder In-Chain, oder aus dem Retry-Wiederverwendung, mit newKeySize auf die tatsächliche Größe des neuen Schlüssels gesetzt, wenn er aus der Freiliste wiederverwendet wird. Dies ist nur für Datentypen mit variabler Länge und für Garnet, was nur SpanByte bedeutet, von Belang, der sicherstellt, dass der Datensatz jederzeit für Scans "gültig" ist, indem er immer mit Nullen initialisiert wird. Bei der Wiederverwendung garantiert Tsavorite, dass ein gültiger Schlüssel und Wert (auch wenn der Wert Standard ist) im Datensatz vorhanden sind, und ruft DisposeForRevivification wie folgt auf
• Löscht die zusätzliche Wertlänge und den Füller (die zusätzliche Wertlänge wird in lokalen Variablen beibehalten).
• Ruft DisposeForRevivification auf mit newKeySize > 0, wenn der Datensatz aus der Freiliste abgerufen wurde
  • Wenn DisposeForRevivification den Wert und möglicherweise den Schlüssel löscht, muss er dies gemäß dem Protokoll zum Nullsetzen von Daten nach dem verwendeten Speicher tun, wie unter Pflegen zusätzlicher Wertlänge beschrieben. SpanByte muss nichts löschen, da ein SpanByte nichts enthält, das freigegeben werden muss.
  • In einer potenziell abwärtskompatiblen Änderung gegenüber früheren Versionen muss jede variable Implementierung, die nicht SpanByte ist, entweder DisposeForRevivification implementieren, um den Speicher mit Nullen zu initialisieren, oder ihre SingleWriter-, InitialUpdater- und CopyUpdater-Implementierungen überarbeiten, um einen vorhandenen Wert zu erkennen und ihn ähnlich wie ConcurrentWriter oder InPlaceUpdater zu behandeln.
    • Für SpanByte haben SingleWriter usw. einen gültigen Zielwert im Ziel für nicht revivifizierte Datensätze, da VariableLengthBlittableAllocator.GetAndInitializeValue (aufgerufen nach der Datensatzzuweisung) die Standard-SpanByte-Implementierung von IVariableLengthStructureSettings aufruft und den Wertspeicher tatsächlich zu einem gültigen SpanByte initialisiert, das die gesamte angeforderte Wertgröße enthält. Für neu zugewiesene (nicht revivifizierte) Datensätze werden die Wertdaten mit Nullen initialisiert; für revivifizierte Datensätze ist dies nicht garantiert; nur der Wertspeicher nach UsedValueLength ist garantiert null, daher müssen SingleWriter usw. bereit sein, den Zielwert zu verkleinern.

In-Chain Revivification

Wenn die Freiliste nicht aktiv ist, verbleiben alle Tombstoned-Datensätze in der Hash-Kette; und selbst wenn die Freiliste aktiv ist, kann ein gelöschter Datensatz möglicherweise nicht gestrichen werden. Ein nachfolgender Upsert oder RMW desselben Schlüssels belebt den Datensatz wieder, wenn er über eine ausreichende zugewiesene Wertlänge verfügt.

In-Chain-Revivification ist immer aktiv, wenn RevivificationSettings.EnableRevivification wahr ist. Sie funktioniert wie folgt

• Delete() wird auf normale Weise durchgeführt; der Tombstone wird gesetzt. Wenn der Tombstoned-Datensatz am Ende der Tag-Kette steht (d.h. der Datensatz im HashBucketEntry ist) und die Freiliste aktiviert ist, wird er in die Freiliste verschoben. Andernfalls (oder wenn diese Verschiebung fehlschlägt) verbleibt er in der Tag-Kette.
• Upsert() und RMW() versuchen, einen Tombstoned-Datensatz wiederzubeleben
  • Wenn der Datensatz groß genug ist, initialisieren wir seinen Wert neu, indem wir
    • Die zusätzliche Wertlänge und den Füller löschen und DisposeForRevivification wie unter Pflegen zusätzlicher Wertlänge beschrieben aufrufen.
    • Den Tombstone entfernen.

FreeList Revivification

Wenn RevivificationSettings.FreeBinList nicht null ist, erstellt dies die Freiliste gemäß den RevivificationBin-Elementen des Arrays. Wenn die Datentypen fest sind, muss es ein Element des Arrays geben; andernfalls kann es viele geben.

Wenn die Freiliste aktiv ist und ein Datensatz gelöscht wird, und er sich am Ende der Hash-Kette befindet, nicht gesperrt ist und seine PreviousAddress unterhalb von BeginAddress zeigt, dann kann er per CAS (Compare-And-Swap) aus der Hash-Kette entfernt werden. Wenn dies erfolgreich ist, wird er der Freiliste hinzugefügt. Ähnliche Überlegungen gelten für das Freilisten der Quellendatensätze von RCUs, die durch Upsert und RMW durchgeführt werden.

FreeList-Revivification funktioniert wie folgt

• Delete() prüft, ob sich der Datensatz am Ende der Hash-Kette befindet (d. h. der Datensatz im HashBucketEntry ist).
  • Wenn nicht, versuchen wir nicht, ihn in die Freiliste aufzunehmen, da dies zu komplex wäre: TracebackForKeyMatch müsste den nächsthöheren Datensatz zurückgeben, dessen .PreviousAddress auf diesen zeigt, *und* wir müssten prüfen, ob dieser nächsthöhere Datensatz ebenfalls freigelistet (und möglicherweise revivifiziert) wurde.
  • Andernfalls prüft Delete(), ob seine PreviousAddress unterhalb von BeginAddress zeigt. Wenn nicht, müssen wir ihn belassen; er kann der Marker für einen darunter liegenden gelöschten Datensatz sein, und seine Entfernung aus der Tag-Kette würde es ermöglichen, auf den früheren Datensatz fälschlicherweise zuzugreifen.
  • Andernfalls versuchen wir, die .PreviousAddress des neu Tombstoned Datensatzes in den HashBucketEntry zu CASen (Compare-And-Swap).
    • Es ist möglich, das CAS aufgrund einer gleichzeitigen Einfügung fehlschlagen zu lassen
  • Wenn dies erfolgreich ist, fügen wir den Datensatz der Freiliste hinzu. Dies versiegelt ihn für den Fall, dass andere Threads die Tag-Kette durchlaufen.
    • Wenn dieses Hinzufügen fehlschlägt, liegt es daran, dass der Bin voll ist. Anstatt den Datensatz vollständig zu verlieren, versucht Tsavorite, ihn als gelöschten Datensatz wieder einzufügen.
• Upsert und RMW, die RCU durchführen, prüfen *bevor* sie den CAS durchführen, ob der Quellendatensatz im HashBucketEntry vorhanden ist. Wenn ja und alle anderen Bedingungen zutreffen, wird der Quellendatensatz wie bei Delete freigelistet (außer dass kein Versuch unternommen wird, ihn wieder einzufügen, wenn das Hinzufügen zur Freiliste fehlschlägt).
• Upsert() und RMW() versuchen, einen Freilisten-Datensatz wiederzubeleben, wenn sie einen neuen Datensatz erstellen müssen
  • Sie rufen TryTakeFreeRecord auf, um einen Datensatz aus der Freiliste zu entfernen.
  • Bei Erfolg initialisiert TryTakeFreeRecord den Datensatz durch
    • Die zusätzliche Wertlänge und den Füller löschen und DisposeForRevivification wie unter Pflegen zusätzlicher Wertlänge beschrieben aufrufen.
    • Entsiegeln des Datensatzes; Epoch-Management garantiert, dass niemand mehr ausgeführt wird, der diesen Datensatz gesehen hat, bevor er in den Freidatensatz-Pool aufgenommen wurde.

Überlegungen zur Nebenläufigkeitskontrolle für FreeList Revivification

FreeList Revivification erfordert, dass ConcurrencyControlMode nicht ConcurrencyControlMode.None ist; andernfalls kann die Tag-Kette instabil sein, wobei der erste Datensatz in der Tag-Kette möglicherweise entfernt und durch Revivification wiederverwendet wird, während ein Thread von ihm zurückverfolgt.

• Thread1: Holt die erste Datensatzadresse vom HashBucketEntry
• Thread2: Löscht und entfernt den ersten Datensatz und legt ihn auf die Revivification-Freiliste
• Thread3: Revivifiziert diesen Datensatz mit einem anderen Schlüssel und setzt seine .PreviousAddress
• Thread1: Folgt der *ehemaligen* .PreviousAddress und befindet sich nun auf einer völlig anderen Tag-Kette. Dies ist *nur* für den ersten Datensatz in der Tag-Kette (den endgültigsten Datensatz im HashBucketEntry) möglich; wir entfernen keine Datensätze in der Mitte der Tag-Kette.

Für ConcurrencyControlMode.LockTable, da die einzige aktuelle LockTable-Implementierung über die HashBuckets erfolgt und das Sperren auf HashBucket-Ebene höher ist als die Tag-Kette, erhalten wir eine stabile Tag-Kette *fast* kostenlos. Die Kosten sind, dass der HashBucket *vor* dem Aufruf von TracebackForKeyMatch gesperrt werden muss.

FreeRecordPool Design

Die Freilisten-Hierarchie besteht aus

• Der FreeRecordPool, der die Bins verwaltet und entscheidet, welcher Bin für Enqueue und Dequeue verwendet werden soll.
• Mehrere FreeRecordBins, einer für jeden RevivificationBin in den RevivificationSettings mit der entsprechenden Anzahl von Datensätzen, maximaler Datensatzgröße und Best-Fit-Scan-Spezifikation.
• Jedes Element eines Bins ist ein FreeRecord

Jeder Bin ist eine separate Zuweisung, so dass der Pool einen Größenindex verwendet, der ein Cache-ausgerichteter separater Vektor von Integern mit den Bin-Größen ist, der sequenziell durchsucht wird, um die Bin-Größe zu bestimmen. Dies vermeidet das Laden jeder einzelnen Cache-Zeile eines Bins, um seine Größe zu überprüfen.

FreeRecord Design

Ein FreeRecord enthält eine freie Log-Adresse und das Epoch, in dem er freigegeben wurde; seine Daten sind ein 'long', das enthält

• die Adresse (48 Bits) und
• die Größe (16 Bits) des Datensatzes an der Adresse. Wenn die Größe > 2^16 ist, dann ist der Datensatz "übergroß" und seine genaue Größe wird vom hlog bezogen.
  • Die Adresse wird ähnlich wie RecordInfo.PreviousAddress gespeichert, mit der gleichen Anzahl von Bits
  • Die Größe wird über der Adresse verschoben und die restlichen Bits verwendet. Somit ist sie auf 16 Bits beschränkt; alle freien Datensätze über dieser Größe gehen in den übergroßen Bin.

Da dies nur ein Long ist, haben wir atomare Vergleichs- und Austauschoperationen beim Setzen und Nehmen der Adresse.

FreeRecordBin Design

Die Datensätze des Bins haben Größen zwischen [maximale Datensatzgröße des vorherigen Bins + 8] und [maximale Datensatzgröße des aktuellen Bins]. Als Abkürzung bezeichnen wir Bins nach ihrer maximalen Datensatzgröße, d. h. "der 64-Byte-Bin" bedeutet "der Bin, dessen Mindestdatensatzgröße 8 mehr als die maximale Größe des vorherigen Bins beträgt und dessen maximale Datensatzgröße 64 ist."

Jeder Bin hat einen Cache-ausgerichteten Vektor von FreeRecord, der als Rundpuffer fungiert. Im Gegensatz zu FIFO-Warteschlangen pflegen wir keinen Lese-/Schreibzeiger aus folgenden Gründen

• Einige Datensätze im Bin sind kleiner als die Größenanforderung für eine bestimmte Zuweisungsanfrage; dies könnte bedeuten, dass eine Anzahl von Datensätzen übersprungen wird, bevor eine Übereinstimmung gefunden wird. Mit dem reinen FIFO-Ansatz würden viele Datensätze verloren gehen. Die einzigen Lösungen, die den Lese-/Schreibzeiger beibehalten, sind das Wiedereinreihen der übersprungenen Datensätze oder eine Variante des Vorausblickens über den Lesezeiger hinaus, was Komplexität einführen würde, wie z. B. potenzielles Blockieren nachfolgender Schreibvorgänge (der Lesezeiger könnte "eingefroren" sein, aber mit vielen offenen Elementen dahinter, zu denen der Schreibzeiger nicht vordringen kann).
• Die Pflege der Lese- und Schreibzeiger erfordert eine Sperre bei jedem Aufruf, zusätzlich zur Add/Remove-Sperre auf dem FreeRecord selbst.

Wir möchten eine Lösung erhalten, die nur eine Sperre für Lese- und Schreibvorgänge hat, nicht das gesamte Segment durchläuft und sich bestmöglich um die beste Passform bemüht. Um dies zu erreichen, verwenden wir eine Strategie der Segmentierung des Bins nach Datensatzgrößen.

Segmentierung von variablen Längen-Bins

Für variable Schlüssel- und Werttypen segmentieren wir Bins basierend auf dem Größenbereich bei 8-Byte-Ausrichtung.

Zuerst wird die maximale Anzahl von Datensätzen im Bin auf eine Cache-ausgerichtete Größe aufgerundet und kann weiter aufgerundet werden, um sicherzustellen, dass jedes Segment an einer Cache-Grenze beginnt. FreeRecords sind 16 Bytes, wie oben erwähnt, also 4 pro Cache-Zeile. Allerdings sind 4 Elemente zu klein für ein Segment, daher benötigen wir eine minimale Segmentgröße von 8 (2 Cache-Zeilen). Dies ist eine definierte Konstante MinSegmentSize und kann bei Bedarf geändert werden.

Wir berechnen Bin-Segmente, indem wir die Anzahl der Datensätze im Bin gleichmäßig durch den Bereich der möglichen 8-Byte-ausgerichteten Datensatzgrößen im Bin teilen, mit einem Minimum von zwei Cache-Zeilen (8 Elementen) pro Segment. Segmente haben keine Lese-/Schreibzeiger; sie sind einfach der Index, bei dem in der Datensatz-Array des Bins begonnen wird, berechnet aus der Laufzeit basierend auf der Datensatzgröße (beim Hinzufügen) oder der angeforderten Datensatzgröße (beim Entnehmen).

Hier sind 3 Beispiele für die Bestimmung der Größenbereiche, unter Verwendung von Bin-Definitionen wie folgt

• Ein 32-Byte-Bin und ein 64-Byte-Bin, beide mit 1024 Datensätzen
• Zwischenliegende Bins werden wir ignorieren, die aber mit einer maximalen Datensatzgröße von 2k enden.
• Ein Bin, dessen maximale Datensatzgröße 4k beträgt und 256 Datensätze hat. Dieses Beispiel nimmt von der

Die folgenden Segmentierungsstrategien werden verwendet

• Das 32-Byte-Bin hat eine Mindestgröße von 16, da es das erste Bin ist. Da die Größen in Vielfachen von 8 oder mehr betrachtet werden, hat es 3 mögliche Datensatzgrößen: 16, 24, 32. Daher erstellen wir interne Segmente der Größe 1024/3, runden dann auf, so dass jedes Segment eine Datensatzanzahl hat, die ein Vielfaches von 4 ist. Somit ist jedes Segment 344 Elemente (1024/3 ist 341,33...; auf ein Vielfaches von MinSegmentSize aufgerundet), und es gibt insgesamt 1032 Elemente im Bin. Diese Segmente beginnen an den Indizes 0, 344, 688.
• Die Mindestgröße des 64-Byte-Bins ist 40 (8 mehr als die maximale Größe des vorherigen Bins). Nach dem Vorherigen hat es 4 mögliche Datensatzgrößen: 40, 48, 56, 64. 1024 ist gleichmäßig durch 4 bis zu einer MinSegmentSize-ausgerichteten Größe von 256 teilbar, und daher beginnen die Segmente bei 0, 256, 512, 768.
• Der Größenbereich des größeren Bins hat zu viele mögliche Größen, um ein Segment für jede Größe zu erstellen, und verwendet daher eine andere Segmentberechnungsstrategie. In diesem Fall beträgt der Größenbereich 2k, was durch 8 geteilt 256 mögliche Datensatzgrößen innerhalb des Bins ergibt. Die Division der Bin-Datensatzanzahl durch diese ergibt 4, was unter der erforderlichen MinSegmentSize liegt. Daher setzen wir die Segmentanzahl des Bins auf MinSegementSize und teilen den Bin-Datensatzanzahl durch diese, um die Anzahl der Segmente (aufgerundet auf eine ganze Zahl) zu erhalten, und setzen dann die Segmentgrößen-Inkrementierung auf den Größenbereich geteilt durch die Segmentanzahl. Wir haben somit 16 Segmente und teilen daher den Größenbereich durch 16, um die Datensatzgrößenbereiche für die Segmente zu erhalten. Die Anzahl der Datensätze ist die Segmentgröße multipliziert mit der Segmentanzahl. Die Segmente sind
  • Segment 0 beginnt an Index 0 mit einer maximalen Datensatzgröße von 2k+16 (somit kann das Segment eine Mischung aus Datensätzen der folgenden Größen enthalten: 2k+8, 2k+16)
  • Segment 1 beginnt an Index 8 mit einer maximalen Datensatzgröße von 2k + 16*2
  • Segment 2 beginnt an Index 16 mit einer maximalen Datensatzgröße von 2k+16*3
  • Und so weiter
• Im Wesentlichen sind die Partitionen Mini-Bins, für die wir die Start-Offsets basierend auf der Datensatz- oder Anfragegröße effizient berechnen können.

Eine Alternative zur größenbasierten Partitionierung wäre die Verwendung der Thread-ID, wie es LightEpoch tut. Bei der threadid-basierten Partitionierung gibt es jedoch keine Organisation der Größe; wir könnten eine zufällige Verteilung der Größen haben. Bei der größenbasierten Partitionierung landen wir viel wahrscheinlicher auf der gewünschten Größe (oder nahe daran), und beim Überlaufen landen wir die Hälfte der Zeit in der nächsthöheren Datensatzgrößen-Partition, was möglicherweise eine nahezu beste Passform mit minimalem Aufwand ergibt. Darüber hinaus erleichtert die größenbasierte Partitionierung die Suche nach der besten Passform für eine Anfrage.

Best-Fit und First-Fit

Wie die Namen schon sagen, haben wir die Wahl zwischen First-Fit oder Best-Fit, um eine Anfrage zu erfüllen. Wir erlauben beides über RevivificationBin.BestFitScanLimit

• UseFirstFit: Der Wert ist Null, also scannen wir nicht; wenn ein Datensatz aus dem Bin angefordert wird, gibt es den ersten zurück, der eine Größe >= der angeforderten Größe hat, ein addedEpoch >= SafeToReclaimEpoch hat und eine Adresse >= der MinAddress hat, die an den Take-Aufruf übergeben wurde.
• BestFitScanAll: Der Wert ist Int.MaxValue, also scannen wir den gesamten Bin (möglicherweise mit Umbruch), behalten die beste Passform im Auge und versuchen dann, diese zurückzugeben (was fehlschlagen kann, wenn ein anderer Thread sie zuerst zurückgegeben hat, in welchem Fall wir es erneut versuchen). Wenn an irgendeinem Punkt eine exakte Passform gefunden wird, versucht dieser Bin, diesen Datensatz zurückzugeben.
• Eine andere Zahl < Bin-Datensatzanzahl: Ähnlich wie BestFitScanAll, mit dem Unterschied, dass die Anzahl der zu durchsuchenden Datensätze begrenzt ist.

Bins mit fester Länge

Für Datentypen mit fester Länge und fester Wertlänge gibt es nur einen Bin und natürlich keine größenbasierte Partitionierung. In diesem Fall könnten wir eine Thread-ID-basierte Partitionierung verwenden (wie auch jede ausreichend große Partition), um den Index innerhalb der Partition zu bestimmen, von dem aus die Iteration beginnen soll. Die Thread-ID-basierte Partitionierung leidet jedoch unter der Möglichkeit, dass Schreiber in andere Partitionen schreiben als Leser lesen. Im schlimmsten Fall müssen die Leser vollständig durch alle Partitionen wrappen, um an die Datensätze zu gelangen. Dies kann durch die reduzierte Cache-Zeilen-Ping-Pong-Bildung zwischen Prozessorencaches ausgeglichen werden, wenn die ersten 4 Datensätze der Partition wiederholt von verschiedenen Threads aktualisiert werden, aber dies wurde nicht ausprobiert.

Überprüfung auf leere Bins

Wir wollen keinen pro Operation Zähler für Datensätze im FreeRecordPool oder jedem FreeRecordBin pflegen, da dies eine zusätzliche Sperre pro Add oder Take wäre. Aus diesem Grund können wir keine "jederzeit genaue" Angabe darüber haben, ob der Pool oder ein Bin leer sind. Die Überprüfung leerer Bins ist jedoch teuer, daher wollen wir dies optimieren.

Es gibt zahlreiche "Performance vs. Genauigkeit"-Kompromisse beim Setzen eines oder mehrerer grober Flags, die angeben, ob der Pool und/oder einzelne Bins leer sind.

• Dies auf Pool-Ebene zu tun, erfordert die Koordination mit allen Bins
• Dies auf Bin-Ebene zu tun, erfordert die Kenntnis, auf welchen Bin eine Anfrage abgebildet wird, was einige Berechnungen erfordert.
• Offensichtlich wird ein "leer"-Flag durch Add auf false gesetzt. Es ist jedoch nicht einfach, es auf true zu setzen, wenn Take das letzte Flag entfernt hat, da gleichzeitig ein Add stattfinden könnte.

Der gewählte Ansatz ist die Pflege von Bin-Level isEmpty-Flags.

• Add setzt immer isEmpty auf false.
• Wir löschen isEmpty bei Take() nicht, da dies zu verlorenen "isEmpty = false"-Flags aufgrund von Add führen könnte.
• Wir unterhalten eine Worker-Task, die periodisch alle Bins durchläuft, um IsEmpty auf true zu setzen.

Diese Aufgabe, Bins zu durchlaufen, um isEmpty zu setzen, wird von der Klasse CheckEmptyWorker durchgeführt, die eine separate On-Demand-Task zum Durchführen des Inkrements verwendet. Dies geschieht in einer Schleife, die Folgendes ausführt:

• 1 Sekunde warten
• Scan: Scan each bin in the entire pool
  • If the bin is already marked isEmpty, do nothing
  • Otherwise, iterate all entries in the bin
    • If an is found with a valid address, exit that bin's loop
    • Otherwise, set that bin's isEmpty flag.

CheckEmptyWorker hat eine Start-Methode, die von FreeRecordPool Add oder Take aufgerufen wird. Diese Start-Methode prüft, ob der CheckEmptyWorkerWorker gestartet wurde, und startet ihn gegebenenfalls.

Da dies eine persistente Aufgabe ist, verfügt sie über eine CancellationTokenSource, die von CheckEmptyWorker.Dispose() signalisiert wird, wenn wir die TsavoriteKV herunterfahren.

Fixed vs. VarLen

Für Typen, die keine variablen Längen haben, ist die Datensatzgröße fest, sodass der FreeRecordPool dafür nur einen einzigen Bin hat. Andernfalls hat er den vollen Bereich variabler Längen-Bins.

Hinzufügen eines Datensatzes zum Pool

Beim Hinzufügen eines Datensatzes zum Pool

• Der Aufrufer ruft FreeRecordPool.TryAdd auf.
• TryAdd scannt den Größenindex, um den Bin-Index zu finden
• Der Bin an diesem Index wird aufgerufen, um den Datensatz hinzuzufügen
  • Der Bin berechnet den Segment-Offset basierend auf der Datensatzgröße und durchläuft dann einen linearen Scan, um nach einem freien Speicherplatz zu suchen (oder einem Speicherplatz, dessen Adresse < hlog.ReadOnlyAddress ist).
  • Wenn er einen findet, wird der Datensatz mit seiner Adresse, Größe (wenn unter 16 Bit) und der aktuellen Epoche zum Zeitpunkt des TryAdd-Aufrufs hinzugefügt. TryAdd gibt dann true zurück.
  • andernfalls gibt TryAdd false zurück

Entnehmen eines Datensatzes aus dem Pool

Beim Entnehmen eines Datensatzes müssen wir

• Bestimmen Sie den Bin, der der angeforderten Größe entspricht
• Wenn der Bin leer ist, kehren Sie zurück
• Andernfalls muss jede zurückgegebene Adresse die Invariante aufrechterhalten, dass Hash-Ketten abwärts zeigen; die HashTableEntry.Address wird als minimale erforderliche Adresse übergeben. Dies ist entweder eine gültige untere Adresse oder eine ungültige Adresse (unterhalb von BeginAddress).

Die Operation wird dann wie folgt fortgesetzt:

• Der Aufrufer ruft FreeRecordPool.TryTake auf.
• TryTake scannt den Größenindex, um den Bin-Index zu finden
• Der Bin an diesem Index wird aufgerufen, um zu versuchen, den Datensatz zu entnehmen
  • Der Bin berechnet den Segment-Offset basierend auf der Datensatzgröße und durchläuft dann einen linearen Scan, um nach einem Datensatz zu suchen, der >= der erforderlichen Größe ist und eine Adresse >= der an den Aufruf übergebenen minAddress hat. Siehe Best-Fit und First-Fit für eine Diskussion darüber, welche gangbaren Datensätze zurückgegeben werden.
  • Wenn er einen passenden Datensatz findet und den Bin erfolgreich zu leer CASen kann, wird der Datensatz zurückgegeben und TryTake gibt true zurück.
  • Andernfalls gibt TryTake false zurück