Sperren

Es gibt drei Sperrmodi in Tsavorite, die über einen ConcurrencyControlMode-Wert im Tsavorite-Konstruktor festgelegt werden.

• LockTable: Die Hash-Index-Buckets von Tsavorite werden verwendet, um den Sperrstatus zu speichern. Locktable-Sperren sind entweder manuell oder transient.
  • Manuell: Garnet ruft zu Beginn einer Transaktion eine Lock-Methode auf LockableContext oder LockableUnsafeContext (im Folgenden gemeinsam als Lockable*Context bezeichnet) auf und übergibt ein geordnetes Array von Schlüsseln. Nach Abschluss der Transaktion muss Unlock aufgerufen werden. Tsavorite versucht nicht, während einzelner Operationen auf diesen Sitzungskontexten zu sperren.
  • Transient: Tsavorite erwirbt und gibt Sperren für einzelne Schlüssel für die Dauer einer Datenoperation frei: Upsert, RMW, Read oder Delete. Kollektiv werden diese hier als InternalXxx für die internen Methoden bezeichnet, die sie implementieren.
• None: Tsavorite führt keine Sperren durch.

Alle Sperren werden durch Spinnen auf Interlocked.CompareExchange und Thread.Yield() erworben und haben eine begrenzte Spin-Anzahl, um Deadlocks zu vermeiden. Wenn die gewünschte Sperre in dieser Zeit nicht erworben werden kann, wird die Operation wiederholt.

Wie oben erwähnt, erfolgt die manuelle Sperrung durch den Erwerb der Lockable*Context-Instanz von einer ClientSession. Derzeit gibt es 4 *Context-Implementierungen; alle sind struct zur Inline-Vermeidung. Alle *Context werden als Eigenschaften der ClientSession mit dem Namen des Typs (z. B. clientSession.LockableContext) abgerufen. Die Merkmale jedes *Context sind:

• BasicContext: Dies ist exakt dasselbe wie ClientSession, ruft intern direkt die Methoden von ClientSession auf und verwendet die TsavoriteSession von ClientSession wieder. Es bietet sicheres Epochenmanagement (Erwerb und Freigabe der Epoche bei jedem Aufruf) und transiente Sperren.
• UnsafeContext : IUnsafeContext: Dies bietet transiente Sperren, aber anstatt eines sicheren Epochenmanagements, das pro Operation von Tsavorite gehandhabt wird, unterstützt es "unsicheres" manuelles Epochenmanagement, das vom Client über BeginUnsafe() und EndUnsafe() gesteuert wird. Es liegt in der Verantwortung des Clients, diese Aufrufe korrekt auszuführen. Die API-Methoden von UnsafeContext rufen die internen Methoden ContextRead usw. auf, ohne die Wiederaufnahme und Aussetzung (innerhalb von try/finally) des Epochesschutzes durchzuführen, wie es die "sicheren" API-Methoden tun.
• LockableContext : ILockableContext: Dies bietet sicheres Epochenmanagement, erfordert aber anstelle von transienten Sperren manuelle Sperren über BeginLockable und EndLockable. Diese Anforderung stellt sicher, dass alle Sperren erworben werden, bevor Methoden aufgerufen werden, die auf diese Schlüssel zugreifen.
• LockableUnsafeContext : ILockableContext, IUnsafeContext: Dies kombiniert manuelles Epochenmanagement und manuelle Sperren und stellt beide Methodensätze bereit.

Zusätzlich zu den Lock-Methoden unterstützt Tsavorite:

• TryLock: Akzeptiert ein Array von Schlüsseln und gibt true zurück, wenn alle Sperren erworben wurden, andernfalls false (und alle erworbenen Sperren werden freigegeben).
• TryPromoteLock: Akzeptiert einen einzelnen Schlüssel und gibt true zurück, wenn die Sperre des Schlüssels von Lesen zu Exklusiv befördert werden konnte.

Überlegungen

Alle manuellen Sperren von Schlüsseln müssen die Schlüssel in einer deterministischen Reihenfolge sperren und in umgekehrter Reihenfolge freigeben, um Deadlocks zu vermeiden.

Lock-Spinning ist begrenzt, um Deadlocks wie die folgenden zu vermeiden.

• Lockable*Context LC1 sperrt k1 exklusiv.
• BasicContext BC1 versucht, eine exklusive transiente Sperre für k1 zu erwerben, und spinnt, während es die Epoche hält.
• LC1 führt eine RMW auf k1 durch, was zu einem CopyUpdate führt; dies führt zu einer BlockAllocation, die feststellt, dass Seiten aus dem Anfang des Logs geleert werden müssen, um Platz am Ende zu schaffen.
  • LC1 ruft daher BumpCurrentEpoch(... OnPagesClosed) auf.
  • Da BC1 die Epoche hält, wird der Aufruf OnPagesClosed() nie abgearbeitet, sodass es zu einem Deadlock kommt. Indem wir sicherstellen, dass Sperren begrenzt gesponnen werden, zwingen wir eine oder beide der oben genannten Sitzungen, alle bereits erworbenen Sperren freizugeben und zum Aufrufstapel zurückzukehren, um die Operation über RETRY_LATER (was die Epoche aktualisiert und es anderen Operationen wie dem oben genannten OnPagesClosed() ermöglicht, abzuschließen) erneut zu versuchen.

Transiente Sperren werden niemals über ausstehende E/A oder andere Warteoperationen hinaus gehalten. Alle Low-Level-Implementierer der Datenoperationen (InternalRead, InternalUpsert, InternalRMW und InternalDelete - kollektiv als InternalXxx bezeichnet) geben diese Sperren frei, wenn der Aufruf beendet ist. Wenn die Operationen wiederholt werden müssen, werden die Sperren als Teil des normalen Betriebs dort erneut erworben.

Beispiel

Hier ist ein Beispiel für die beiden oben genannten Anwendungsfälle, zusammengefasst aus den Unit-Tests in LockableUnsafeContextTests.cs.

    var luContext = session.GetLockableUnsafeContext();
    luContext.BeginUnsafe();
    luContext.BeginLockable();

    var keys = new[]
    {
        new FixedLengthLockableKeyStruct<long>(readKey24, LockType.Shared, luContext),      // Source, shared
        new FixedLengthLockableKeyStruct<long>(readKey51, LockType.Shared, luContext),      // Source, shared
        new FixedLengthLockableKeyStruct<long>(resultKey, LockType.Exclusive, luContext),   // Destination, exclusive
    };

    // Sort the keys to guard against deadlock
    luContext.SortKeyHashes(keys);

    Assert.IsTrue(luContext.TryLock(keys));

    luContext.Read(key24, out var value24);
    luContext.Read(key51, out var value51);
    luContext.Upsert(resultKey, value24 + value51);

    luContext.Unlock(keys);

    luContext.EndLockable();
    luContext.EndUnsafe();

Internes Design

Dieser Abschnitt behandelt das interne Design und die Implementierung der Sperrmechanismen von Tsavorite.

Operationen-Datenstrukturen

Es gibt eine Reihe von Variablen, die erforderlich sind, um die Hauptinformationen des Hash-Tabelleneintrags, den "Quell"-Datensatz (wie oben definiert) und andere stapelbasierte Daten zu verfolgen, die für die Operation relevant sind. Diese Variablen sind in Strukturen platziert, die sich auf dem Stapel auf InternalXxx-Ebene befinden.

HashEntryInfo

Diese wird für die Hash-Ketten-Durchquerung und CAS-Updates verwendet. Sie besteht hauptsächlich aus:

• Dem Hashcode des Schlüssels und dem zugehörigen Tag.
• einer stabilen Kopie des HashBucketEntry zum Zeitpunkt der Populieru ng des HashEntryInfo.
  • Dies hat sowohl Address (die das Readcache-Bit enthalten kann oder nicht) als auch AbsoluteAddress (Address ohne das Readcache-Bit) Zugriffsmethoden.
• ein Zeiger (im unsicheren "C/C++ *"-Sinne) auf den Live-HashBucketEntry, der von anderen Sitzungen aktualisiert werden kann, während unsere aktuelle Operation fortschreitet.
  • Wie bei der stabilen Kopie hat dies zwei Adress-Zugriffsmethoden: CurrentAddress (die das Readcache-Bit enthalten kann oder nicht) und AbsoluteCurrentAddress (CurrentAddress ohne das Readcache-Bit).
• Eine Methode zum Aktualisieren der stabilen Kopie des HashBucketEntry mit den aktuellen Informationen aus dem "Live"-Zeiger.

RecordSource

Dies ist als RecordSource<TKey, TValue> implementiert und enthält die Informationen, die den Quell-Datensatz und die Sperrinformationen für diesen Datensatz identifizieren.

• Ob es einen In-Memory-Quell-Datensatz gibt, und wenn ja:
  • seine logische und physische Adresse.
  • ob er sich im Readcache oder im Hauptprotokoll befindet.
  • ob er gesperrt ist.
• Die neueste logische Adresse dieses Schlüssel-Hashs im Hauptprotokoll. Wenn es keine Readcache-Datensätze gibt, ist dies dasselbe wie die HashEntryInfo-Adresse.
• Wenn es Readcache-Datensätze in der Kette gibt, enthält RecordSource die niedrigsten logischen und physischen Readcache-Adressen. Diese werden zum "Einschieben" eines neuen Hauptprotokoll-Datensatzes in die Lücke zwischen den Readcache-Datensätzen und den Hauptprotokoll-Datensätzen verwendet; siehe ReadCache unten.
• Das Protokoll (Readcache oder Hlog), in dem sich der Quell-Datensatz, falls vorhanden, befindet. Dies ist Hlog, es sei denn, es gibt einen Readcache-Quell-Datensatz.
• Ob eine LockTable-Sperre erworben wurde. Dies ist exklusiv mit In-Memory-Sperren; nur eine sollte gesetzt sein.

OperationStackContext

Dies enthält alle Informationen auf dem Stapel, die für die Operation notwendig sind, was die Parameterlisten erheblich verkürzt. Es enthält:

• Das HashEntryInfo und RecordSource<TKey, TValue> für diese Operation. Diese werden im Allgemeinen zusammen verwendet, und in einigen Situationen, z. B. wenn sich hlog.HeadAddress aufgrund einer Epochenaktualisierung geändert hat, wird RecordSource<TKey, TValue> während der Operation aus HashEntryInfo neu initialisiert.
• die logische Adresse eines neuen Datensatzes, der für die Operation erstellt wurde. Diese wird in der Kette nach oben weitergegeben, damit try/finally sie bei Ausnahmen als ungültig und nicht-tentativ markieren kann, ohne die Kosten einer verschachtelten try/finally-Anweisung in der Methode CreateNewRecord* tragen zu müssen.

Sperrorte

Dieser Abschnitt erörtert, wo Sperren tatsächlich gespeichert werden.

LockTable

Bei der Hash-Tabellen-Sperrung wird der Schlüssel gehasht, um seinen Code zu erhalten, der dann modulo den Hash-Tabellen-Bucket-Index ermittelt. Dieser Bucket besteht aus einem Vektor von 8 HashBucketEntries (Cache-ausgerichtet, da jede HashBucketEntry nur ein 'long' enthält). Die Einträge sind nach 'Tags' organisiert, die die oberen 14 Bits des Hashcodes sind. Der 8. HashBucketEntry wird als verknüpfte Liste zu einem Überlauf-Bucket verwendet; seine Address-Eigenschaft ist eine separate Zuweisung, die auf einen Überlauf-Bucket verweist. Somit enthält ein Bucket 7 Einträge und einen Zeiger auf einen anderen Bucket, wenn mehr als 7 Tags gefunden wurden.

Folgend eine vereinfachte Übersicht der 'Tag'-Logik, wobei FindOrCreateTag als Beispiel verwendet wird:

• Iterieren Sie die ersten 7 Einträge aller Buckets, einschließlich Überläufe. Wenn das Tag gefunden wird, verwenden Sie diesen Eintrag.
• Andernfalls, wenn ein leerer Eintrag gefunden wurde, weisen Sie dieses Tag dem ersten leeren Eintrag zu und verwenden Sie diesen Eintrag.
• Andernfalls fügen Sie einen Überlauf-Bucket hinzu und wiederholen Sie die ersten beiden Schritte in diesem Bucket. (FindTag ist einfacher, da es keinen Eintrag hinzufügen muss; es gibt false zurück, wenn das Tag nicht gefunden wird).

Für den ersten Bucket werden die Tag-Bits seines Überlaufeintrags zum Sperren verwendet; siehe die Klasse HashBucket für detaillierte Kommentare. Es gibt 16 Tag-Bits; für Sperren werden 15 Bits für geteilte (Lese-) Sperren und ein Bit für exklusive Sperren verwendet.

Somit wird ein Schlüssel indirekt gesperrt, indem sein HashBucket gesperrt wird. Dies kann dazu führen, dass mehrere Schlüssel gesperrt werden (alle Schlüssel, die zu diesem Bucket gehasht werden), anstatt nur des benötigten Schlüssels.

RecordInfo

Einige relevante RecordInfo-Bits:

• Sealed: Ein als Sealed markierter Datensatz wurde durch ein Update abgelöst (und der Datensatz kann sich in der Revivification FreeList befinden). Das Versiegeln ist notwendig, da sonst ein Thread ein RCU (Read, Copy, Update) mit einem Wert durchführen könnte, der zu groß für ein IPU (In-Place Update) ist, während gleichzeitig ein anderer Thread ein IPU mit einem Wert durchführen könnte, der klein genug ist, um hineinzupassen. Ein Thread, der auf einen versiegelten Datensatz trifft, sollte sofort RETRY_LATER zurückgeben (es muss RETRY_LATER statt RETRY_NOW sein, da der Thread, dem die Versiegelung gehört, eine weitere Operation durchführen muss, wie z. B. ein Einfügen am Ende, um die Dinge in einen konsistenten Zustand zu bringen; diese Operation erfordert möglicherweise eine Epochenaktualisierung).

  • Das Versiegeln erfolgt über RecordInfo.Seal. Dies geschieht nur, wenn der LockTable-Eintrag bereits exklusiv gesperrt ist, sodass Seal() eine einfache bitweise Operation durchführt.

• Invalid: Dies zeigt an, dass der Datensatz übersprungen werden soll, indem seine .PreviousAddress verwendet wird, um die Kette entlangzugehen, anstatt neu gestartet zu werden. Diese "Überspring"-Semantik ist hauptsächlich für den Readcache relevant; wir sollten keine ungültigen Datensätze in der Hash-Kette des Hauptprotokolls haben. Tatsächlich muss jeder Hauptprotokoll-Datensatz, der nicht in der Hash-Kette ist, als ungültig markiert werden.

  • Im ReadCache versiegeln wir keine Datensätze; die Semantik von Seal bedeutet, dass die Operation neu gestartet wird, wenn ein versiegelter Datensatz gefunden wird. Für Nicht-readcache-Datensätze bewirkt dies, dass die Ausführung am Ende der Hauptprotokoll-Datensätze neu gestartet wird. readcache-Datensätze befinden sich jedoch am Anfang der Hash-Kette, *vor* den Hauptprotokoll-Datensätzen; daher würde ein Neustart wieder am Hash-Bucket beginnen, die Readcache-Datensätze durchlaufen und den versiegelten Datensatz immer wieder treffen, ad infinitum.
  • Daher setzen wir readcache-Datensätze auf Invalid, wenn sie nicht mehr aktuell sind; dies ermöglicht es der Durchquerung, bis die Readcache-Kette mit dem ersten Hauptprotokoll-Datensatz verknüpft ist.

  Zusätzlich können Datensätze aus folgenden Gründen aus der Tag-Kette entfernt (elidiert) werden:

  • Der Datensatz wurde gelöscht.
  • Der Datensatz war eine "Quelle" für RCU.

  In diesen Fällen, wenn die PreviousAddress des Datensatzes unter hlog.BeginAddress zeigt, entfernen wir den Datensatz, damit wir keinen E/A-Aufwand betreiben müssen, um festzustellen, dass es sich um einen abgelösten Datensatz handelt.

  • Solche elidierten Datensätze werden in die FreeList aufgenommen, wenn diese für Revivification aktiviert ist.

Sperrfluss

Wenn Internalxxx, wenn ConcurrencyControlMode LockTable ist:

Wir rufen den Schlüssel-Hash zu Beginn der Operation ab, sodass wir seinen Bucket sperren, wenn wir uns nicht in einem Lockable*Context befinden (wenn wir es sind, stellen wir später sicher, dass der Schlüssel bereits gesperrt ist).

Danach wird die angeforderte Operation innerhalb eines try/finally-Blocks ausgeführt, dessen 'finally' die Sperre freigibt.

Bei RCU-ähnlichen Operationen wie RMW oder Upsert eines In-Memory-Datensatzes (einschließlich In-ReadCache) wird der Quell-Datensatz versiegelt (und möglicherweise ungültig gemacht, um ihn für Revivification in die FreeList aufzunehmen).

Ähnliche Sperrlogik gilt für die Routinen zur Fortsetzung ausstehender E/A: ContinuePendingRead, ContinuePendingRMW und ContinuePendingConditionalCopyToTail.

ReadCache

Der Readcache ist ein Cache für Datensätze, die von der Festplatte gelesen werden. Im Falle von Datensätzen, die 'heiß' werden (mehrmals gelesen), spart dies mehrere E/A. Er hat eine feste Größe, die beim Start von TsavoriteKV bestimmt wird, und keine Festplattenkomponente. Datensätze im ReadCache werden am Anfang verdrängt, ohne auf die Festplatte geschrieben zu werden, wenn genügend neue Datensätze am Ende hinzugefügt werden, um die Spezifikation der Speichergröße zu überschreiten.

Wenn der ReadCache aktiviert ist, werden Datensätze aus dem ReadCache in die Tag-Kette eingefügt, beginnend mit dem HashBucketEntry (diese Datensätze werden als ReadCache identifiziert durch eine Kombination aus TsavoriteKV.UseReadCache, die gesetzt ist, *und* das ReadCache-Bit in RecordInfo ist gesetzt). Alle ReadCache-Datensätze kommen vor jedem Hauptprotokoll-Datensatz. Also (mit r#### zur Kennzeichnung eines ReadCache-Datensatzes und m#### zur Kennzeichnung eines Hauptprotokoll-Datensatzes):

• Wenn es keine ReadCache-Einträge in einer Hash-Kette gibt, sieht sie so aus: HashTable -> m4000 -> m3000 -> m...
• Wenn es ReadCache-Einträge in einer Hash-Kette gibt, sieht sie so aus: HashTable -> r8000 -> r7000 -> m4000 -> m3000 -> m...

Als terminologische Anmerkung wird die Unterkette von r####-Datensätzen als ReadCache-Präfixkette dieser Hash-Kette bezeichnet.

Wenn der Schlüssel im Readcache gefunden wird, wird RecordSource<TKey, TValue>.Log auf den Readcache gesetzt, und die logicalAddress wird auf die logicalAddress des Readcache-Datensatzes gesetzt (die das ReadCache-Bit enthält). Wenn die Operation ein erfolgreiches Update ist (was immer ein RCU sein wird; Readcache-Datensätze werden niemals selbst aktualisiert), geschehen die folgenden Schritte:

• Die neue Version des Datensatzes wird in die Tag-Kette nach dem Readcache-Präfix "eingefügt".
• Der Readcache-"Quell"-Datensatz wird ungültig gemacht.

Unter Verwendung des obigen Beispiels und unter Annahme eines Updates von r8000 würde die resultierende Kette lauten:

• HashTable -> r8000 (ungültig) -> r7000 -> mxxxx (neu) -> m4000 -> m3000 -> m...
• In diesem Beispiel ist zu beachten, dass die Datensatzadressräume zwischen dem Hauptprotokoll und dem Readcache völlig unterschiedlich sind; "xxxx" wird als "neue Adresse" zur Symbolisierung verwendet.

Diese Einschiebungsoperation erfordert, dass wir sowohl Updates am Ende der Tag-Kette (in HashEntryInfo) als auch am Einschiebepunkt behandeln. Dies kann nicht als einzelne atomare Operation erfolgen. Um dies zu bewältigen, trennen wir die Readcache-Präfixkette, fügen den neuen Datensatz am Ende ein und hängen dann die getrennten Datensätze wieder an. Siehe DetachAndReattachReadCacheChain für Details. Wir können das Wiederanhängen fehlschlagen lassen, aber das ist akzeptabel (im Vergleich zu komplexeren und teureren Sperren), da solche Fehler selten sein sollten und der Readcache nur eine Leistungsoptimierung ist.