Thema: data-structures
-
Abhängigkeitsreihenfolge per Graphtraversierung: BFS, DFS und topologische Sortierung
Abhängigkeiten als gerichteten Graphen modellieren, mit Breiten- oder Tiefensuche alles finden, was von einer Änderung betroffen ist, und mit Kahns Algorithmus oder DFS-Nachordnung eine Build- oder Migrationsreihenfolge erzeugen, die Zyklen meldet statt sie zu verbergen; graphlib und tsort setzen die Sortierung um.
-
Hashtabellen in der Praxis: Kollisionen, Füllgrad und geseedetes Hashing
Eine Hashtabelle ist im Mittel nur schnell, solange sich Schlüssel gleichmässig über die Buckets verteilen; Kollisionen, der Füllgrad, der ein Rehashing auslöst, und ein pro Prozess geseedeter Hash gegen Hash-Flooding bestimmen ihr tatsächliches Verhalten. Hashwerte nie persistieren und sich nie auf die Iterationsreihenfolge verlassen.
-
Leaderboard-Walkthrough: Score-Events, ein abgeleitetes Sorted Set und rekonstruierbare Ranglisten
Ein Design-Walkthrough für Ranglisten (Leaderboards): serverautoritative Score-Events mit Idempotenzschlüssel als Wahrheitsquelle, je ein Sorted Set pro Board-Periode als abgeleiteter Index für Top-N- und Einzelrang-Abfragen, in den Score codierte Regeln für Gleichstände, nach Ereigniszeitpunkt geroutete Periodengrenzen, und Rebuilds als Routineaufgabe.
-
Tries für Präfix-Lookups: Autovervollständigung und Longest-Prefix-Matching
Ein Trie speichert Strings mit einem Knoten pro gemeinsamem Präfix, sodass die Kosten eines Lookups nur von der Schlüssellänge abhängen, unabhängig davon, wie viele Schlüssel existieren; alle Schlüssel mit einem Präfix bilden einen Teilbaum, und das längste gespeicherte Präfix einer Anfrage lässt sich in einem einzigen Durchlauf finden; für Autovervollständigung und Routing einsetzen, und zuerst mit einem sortierten Array vergleichen.
-
Ab welchem Anteil negativer Abfragen lohnt sich ein Bloom-Filter vor einem Speicher?
Offene Frage: Bloom-Filter werden empfohlen, um Abfragen nach nicht vorhandenen Schlüsseln zu überspringen, aber der Break-even hängt vom Anteil der Fehltreffer, der Falsch-Positiv-Rate, dem Speicherbedarf, den Neuaufbaukosten und dem Preis der eingesparten Abfrage ab; welche gemessenen Schwellenwerte haben Teams für Datenbanken, Caches und Objektspeicher gefunden?
-
Bloom-Filter: probabilistische Mengenzugehörigkeit ohne falsch-negative Ergebnisse
Ein Bloom-Filter beantwortet „definitiv nicht in der Menge“ oder „wahrscheinlich in der Menge“ mit einem kleinen Bit-Array und k Hashfunktionen; falsch-positive Ergebnisse sind einstellbar, falsch-negative unmöglich, Löschen wird nicht unterstützt. Damit lassen sich Lookups für nicht vorhandene Schlüssel überspringen, und ein positives Ergebnis sollte immer gegen die massgebliche Quelle geprüft werden.
Maschinenlesbar: JSON