_{Bildquelle : www.nikonsmallworld.com}

Anti-Plagiat ist eine spezialisierte Suchmaschine, über die bereits früher geschrieben wurde . Und jede Suchmaschine, was auch immer man sagen mag, um schnell zu arbeiten, benötigt einen eigenen Index, der alle Funktionen des Suchbereichs berücksichtigt. In meinem ersten Artikel über Habr werde ich über die aktuelle Implementierung unseres Suchindex, die Geschichte seiner Entwicklung und die Gründe für die Wahl der einen oder anderen Lösung sprechen. Effektive .NET-Algorithmen sind kein Mythos, sondern eine schwierige und produktive Realität. Wir werden in die Welt des Hashings, der bitweisen Komprimierung und der mehrstufigen Prioritätscaches eintauchen. Was ist, wenn Sie eine Suche schneller als O (1) benötigen?

Wenn jemand anderes nicht weiß, wo sich die Schindeln auf diesem Bild befinden, willkommen ...

Schindeln, Index und warum suchen Sie sie

Eine Schindel ist ein Textstück mit einer Größe von wenigen Wörtern. Schindeln überlappen sich, daher der Name (Englisch, Schindeln - Schuppen, Kacheln). Ihre spezifische Größe ist ein offenes Geheimnis - 4 Wörter. Oder 5? Nun, es kommt darauf an. Selbst dieser Wert gibt jedoch wenig und hängt von der Zusammensetzung der Stoppwörter, dem Algorithmus zum Normalisieren von Wörtern und anderen Details ab, die im Rahmen dieses Artikels nicht von Bedeutung sind. Am Ende berechnen wir den 64-Bit-Hash basierend auf diesem Shingle, den wir in Zukunft als Shingle bezeichnen werden.

Entsprechend dem Text des Dokuments können Sie viele Schindeln erstellen, deren Anzahl mit der Anzahl der Wörter im Dokument vergleichbar ist:

text: string → schindeln: uint64 []

Wenn mehrere Schindeln in zwei Dokumenten zusammenfallen, nehmen wir an, dass sich die Dokumente überschneiden. Je mehr Schindeln übereinstimmen, desto identischer ist der Text in diesem Dokumentpaar. Der Index sucht nach Dokumenten mit der größten Anzahl von Schnittpunkten mit dem zu prüfenden Dokument.

_{Bildquelle: Wikipedia}

Mit dem Shingles-Index können Sie zwei Hauptoperationen ausführen:

1. Indizieren Sie die Schindeln von Dokumenten mit ihren Kennungen:

   
   

   index.Add (docId, Schindeln)

2. Suchen und Anzeigen einer Rangliste von Kennungen für überlappende Dokumente:

   
   

   index.Search (Schindeln) → (docId, score) []

Ich glaube, der Ranking-Algorithmus verdient im Allgemeinen einen separaten Artikel, daher werden wir hier nicht darüber schreiben.

Der Index der Gürtelrose unterscheidet sich stark von bekannten Volltext-Gegenstücken wie Sphinx, Elastic oder größer: Google, Yandex usw. Einerseits erfordert es kein NLP und keine anderen Lebensfreuden. Die gesamte Textverarbeitung wird entfernt und hat keinen Einfluss auf den Prozess sowie die Reihenfolge der Schindeln im Text. Andererseits ist die Suchabfrage kein Wort oder eine Phrase aus mehreren Wörtern, sondern bis zu mehreren hunderttausend Hashes , die alle zusammen und nicht separat von Bedeutung sind.

Hypothetisch können Sie den Volltextindex als Ersatz für den Schindelindex verwenden, aber die Unterschiede sind zu groß. Dies ist der einfachste Weg, um einen bekannten Schlüsselwertspeicher zu verwenden. Wir sägen unsere Fahrradimplementierung , die ShingleIndex heißt.

Warum stören wir uns so? Aber warum.

• Bände :
  
  1. Es gibt viele Dokumente. Jetzt haben wir ungefähr 650 Millionen von ihnen, und dieses Jahr wird es offensichtlich mehr von ihnen geben;
  2. Die Zahl der einzigartigen Schindeln wächst sprunghaft und erreicht bereits Hunderte von Milliarden. Wir warten auf eine Billion.
• Geschwindigkeit :
  
  1. Tagsüber, während der Sommersitzung, werden mehr als 300.000 Dokumente durch das Anti-Plagiat-System überprüft. Dies ist ein wenig nach den Maßstäben der gängigen Suchmaschinen, aber es bleibt im Ton;
  2. Für eine erfolgreiche Überprüfung der Eindeutigkeit von Dokumenten sollte die Anzahl der indizierten Dokumente um Größenordnungen höher sein als die Anzahl der zu prüfenden Dokumente. Die aktuelle Version unseres Index kann durchschnittlich mit einer Geschwindigkeit von mehr als 4000 mittleren Dokumenten pro Sekunde gefüllt werden.

Und alles auf einer Maschine! Ja, wir können replizieren , wir nähern uns allmählich dem dynamischen Sharding in einem Cluster, aber von 2005 bis heute konnte der Index auf einem Computer mit aller Sorgfalt alle oben genannten Schwierigkeiten bewältigen.

Seltsame Erfahrung

Jetzt sind wir jedoch so erfahren. Ob es Ihnen gefällt oder nicht, aber auch wir sind erwachsen geworden und haben im Laufe des Wachstums verschiedene Dinge ausprobiert, an die wir uns jetzt gerne erinnern.

_{Bildquelle: Wikipedia}

Zunächst möchte ein unerfahrener Leser eine SQL-Datenbank verwenden. Sie sind nicht die Einzigen, die dies glauben. Die SQL-Implementierung hat uns seit mehreren Jahren gute Dienste geleistet, um sehr kleine Sammlungen zu implementieren. Trotzdem lag der Fokus sofort auf Millionen von Dokumenten, also musste ich weiter gehen.

Wie Sie wissen, mag niemand Fahrräder, und LevelDB war noch nicht gemeinfrei. 2010 fielen unsere Augen auf BerkeleyDB. Alles ist cool - eine beständige integrierte Schlüsselwertbasis mit geeigneten Btree- und Hash-Zugriffsmethoden und einer langen Geschichte. Alles mit ihr war wunderbar, aber:

• Im Fall einer Hash-Implementierung fiel sie einfach ab, wenn sie ein Volumen von 2 GB erreichte. Ja, wir haben immer noch im 32-Bit-Modus gearbeitet.
• Die Implementierung des B + -Baums funktionierte stabil, aber bei einem Volumen von mehr als einigen Gigabyte begann die Suchgeschwindigkeit erheblich zu sinken.

Wir müssen zugeben, dass wir nie einen Weg gefunden haben, es an unsere Aufgabe anzupassen. Vielleicht liegt das Problem in .net-Bindungen, die noch erledigt werden mussten. Die BDB-Implementierung wurde schließlich als Ersatz für SQL als Zwischenindex verwendet, bevor der Hauptindex ausgefüllt wurde.

Die Zeit verging. 2014 haben sie LMDB und LevelDB ausprobiert, aber nicht implementiert. Die Leute von unserer Anti-Plagiat- Forschungsabteilung verwendeten RocksDB als Index. Auf den ersten Blick war es ein Fund. Aber die langsame Auffüllung und die mittelmäßige Suchgeschwindigkeit selbst bei kleinen Mengen brachten alles umsonst.

Wir haben all das getan, während wir unseren eigenen benutzerdefinierten Index entwickelt haben. Infolgedessen konnte er unsere Probleme so gut lösen, dass wir die vorherigen „Stecker“ aufgaben und uns darauf konzentrierten, sie zu verbessern, die wir jetzt überall in der Produktion verwenden.

Indexebenen

Was haben wir am Ende jetzt? Tatsächlich besteht der Index der Schindeln aus mehreren Schichten (Arrays) mit Elementen konstanter Länge - von 0 bis 128 Bit -, was nicht nur von der Schicht abhängt und nicht unbedingt ein Vielfaches von acht ist.

Jede der Schichten spielt eine Rolle. Einige beschleunigen die Suche, andere sparen Platz und andere werden nie verwendet, aber wirklich benötigt. Wir werden versuchen, sie zu beschreiben, um ihre Gesamteffizienz bei der Suche zu erhöhen.

_{Bildquelle: Wikipedia}

1. Index-Array

Ohne Verlust der Allgemeinheit werden wir nun berücksichtigen, dass dem Dokument eine einzelne Schindel zugewiesen ist.

(docId → Schindel)

Wir tauschen die Elemente des Paares aus (invertieren, da der Index tatsächlich "invertiert" ist!).

(Schindel → docId)

Sortieren Sie nach den Werten der Schindeln und bilden Sie eine Ebene. Weil Die Größe der Schindel und die Kennung des Dokuments sind konstant. Jetzt kann jeder, der die binäre Suche versteht , ein Paar finden, das über die O (logn) -Lesungen der Datei hinausgeht. Was für eine Menge, verdammt viel. Aber das ist besser als nur O (n) .

Wenn das Dokument mehrere Schindeln aufweist, enthält das Dokument mehrere solcher Paare. Wenn es mehrere Dokumente mit demselben Schindel gibt, ändert sich auch nicht viel daran - es gibt mehrere Paare hintereinander mit demselben Schindel. In beiden Fällen wird die Suche für eine vergleichbare Zeit durchgeführt.

2. Array von Gruppen

Wir unterteilen die Elemente des Index aus dem vorherigen Schritt auf bequeme Weise sorgfältig in Gruppen. Damit sie beispielsweise in den Clustersektor passen , bildet der Zuordnungseinheitsblock (gelesen, 4096 Byte) unter Berücksichtigung der Anzahl der Bits und anderer Tricks ein effektives Wörterbuch. Wir erhalten eine einfache Reihe von Positionen solcher Gruppen:

group_map (Hash (Shingle)) -> group_position.

Bei der Suche nach einem Stein suchen wir nun zuerst nach der Position der Gruppe in diesem Wörterbuch, entladen dann die Gruppe und suchen direkt im Speicher. Der gesamte Vorgang erfordert zwei Lesevorgänge.

Das Wörterbuch der Gruppenpositionen benötigt mehrere Größenordnungen weniger Platz als der Index selbst. Oft kann es einfach in den Speicher entladen werden. Es wird also nicht zwei, sondern eine Lesung geben. Insgesamt O (1) .

3. Bloom Filter

Bei Interviews lösen Kandidaten häufig Probleme, indem sie eindeutige Lösungen mit O (n ^ 2) oder sogar O (2 ^ n) herausgeben . Aber wir machen keine dummen Dinge. Gibt es O (0) auf der Welt, das ist die Frage? Versuchen wir es ohne große Hoffnung auf ein Ergebnis ...

Wenden wir uns dem Themenbereich zu. Wenn der Schüler gut gemacht ist und die Arbeit selbst geschrieben hat oder einfach kein Text, sondern Müll vorhanden ist, ist ein wesentlicher Teil seiner Schindeln einzigartig und wird nicht im Index gefunden. Eine solche Datenstruktur wie der Bloom-Filter ist in der Welt bekannt. Überprüfen Sie vor der Suche die Schindel darauf. Wenn der Index keine Schindel enthält, können Sie nicht weiter suchen, andernfalls gehen Sie weiter.

Der Bloom-Filter selbst ist recht einfach, aber es macht keinen Sinn, einen Hash-Vektor für unsere Volumes zu verwenden. Es reicht aus, eins zu verwenden: +1 Messwert aus dem Bloom-Filter. Dies ergibt -1 oder -2 Messwerte aus den nachfolgenden Stufen, falls die Schindel eindeutig ist und im Filter kein falsches Positiv vorhanden war. Pass auf deine Hände auf!

Die Wahrscheinlichkeit eines Bloom-Filterfehlers wird während der Konstruktion festgelegt, die Wahrscheinlichkeit eines unbekannten Schindels wird durch die Ehrlichkeit des Schülers bestimmt. Einfache Berechnungen können zu folgender Abhängigkeit führen:

• Wenn wir der Ehrlichkeit der Menschen vertrauen (d. H. Tatsächlich ist das Dokument original), nimmt die Suchgeschwindigkeit ab.
• Wenn das Dokument klar zusammengefügt ist, erhöht sich die Suchgeschwindigkeit, aber wir benötigen viel Speicher.

Mit dem Vertrauen in die Schüler haben wir das Prinzip „Vertrauen, aber überprüfen“, und die Praxis zeigt, dass der Bloom-Filter immer noch einen Gewinn bringt.

Da diese Datenstruktur auch kleiner als der Index selbst ist und zwischengespeichert werden kann, können Sie den Shingle im besten Fall ohne Datenträgerzugriff löschen.

4. Schwere Schwänze

Es gibt Schindeln, die fast überall zu finden sind. Ihr Anteil an der Gesamtzahl ist gering, aber wenn der Index im ersten Schritt erstellt wird, können im zweiten Schritt Gruppen von zehn und Hunderten von MB erhalten werden. Wir werden sie separat speichern und sie sofort aus der Suchabfrage entfernen.

Als dieser triviale Schritt 2011 zum ersten Mal verwendet wurde, halbierte sich die Größe des Index und die Suche selbst wurde beschleunigt.

5. Andere Schwänze

Trotzdem kann eine Schindel viele Dokumente haben. Und das ist normal. Zehn, Hunderte, Tausende ... Wenn sie im Hauptindex bleiben, wird dies unrentabel. Sie passen möglicherweise auch nicht in die Gruppe. Dadurch wird das Volumen des Wörterbuchs der Gruppenpositionen aufgeblasen. Platzieren Sie sie in einer separaten Reihenfolge mit effizienterer Speicherung. Laut Statistik ist eine solche Entscheidung mehr als gerechtfertigt. Darüber hinaus können verschiedene bitweise Pakete die Anzahl der Festplattenzugriffe und das Volumen des Index verringern.

Aus Gründen der Wartungsfreundlichkeit drucken wir alle diese Ebenen in einem großen Dateiblock. Es gibt zehn solcher Schichten. Ein Teil wird jedoch nicht für die Suche verwendet, ein Teil ist sehr klein und wird immer im Speicher gespeichert. Ein Teil wird nach Bedarf / Möglichkeit aktiv zwischengespeichert.

Im Kampf kommt es bei der Suche nach einem Stein meistens auf ein oder zwei zufällige Dateimessungen an. Im schlimmsten Fall müssen Sie drei machen. Alle Schichten sind effektiv (manchmal bitweise) gepackte Arrays von Elementen konstanter Länge. Das ist Normalisierung. Die Zeit zum Auspacken ist im Vergleich zum Preis des Gesamtvolumens während der Lagerung und der Fähigkeit, besser zwischenzuspeichern, unbedeutend.

Beim Konstruieren werden die Größen der Schichten hauptsächlich im Voraus berechnet und nacheinander geschrieben, so dass dieses Verfahren ziemlich schnell ist.

Wie sind Sie dorthin gekommen, wussten nicht wo

2010 , . , . , .

_{Bildquelle: Wikipedia}

Anfänglich bestand unser Index aus zwei Teilen - einer oben beschriebenen Konstante und einer temporären, deren Rolle entweder SQL oder BDB oder ein eigenes Aktualisierungsprotokoll war. Gelegentlich, zum Beispiel einmal im Monat (und manchmal im Jahr), wird die temporäre Datei sortiert, gefiltert und mit der Hauptversion zusammengeführt. Das Ergebnis war ein einheitliches, und die beiden alten wurden entfernt. Wenn der temporäre nicht in den RAM passen konnte, wurde die Prozedur extern sortiert.

Dieses Verfahren war ziemlich mühsam, es wurde im halbmanuellen Modus gestartet und erforderte das Umschreiben der gesamten Indexdatei von Grund auf neu. Hunderte von Gigabyte für ein paar Millionen Dokumente umschreiben - na ja, so lala Vergnügen, sage ich Ihnen ...

Damit die SSD nicht besonders belastet ist und der Index häufiger aktualisiert wird, haben wir 2012 eine Kette von mehreren Teilen, Chunks nach folgendem Schema, eingebunden:

Hier besteht der Index bis auf die allererste aus einer Kette derselben Art von Chunks. Das erste Addon war ein Nur-Anhängen-Protokoll mit einem Index im RAM. Nachfolgende Brocken nahmen bis zum letzten Mal an Größe (und Alter) zu (Null, Haupt, Wurzel, ...).

Hinweis für Radfahrer ...

Manchmal sollten Sie nicht ratlos sein, Code zu schreiben und nicht einmal nachzudenken, sondern ihn nur gründlicher googeln. Bis zur Notation ähnelt das Diagramm dem aus dem Artikel „Der logarithmisch strukturierte Zusammenführungsbaum“ von 1996 :

Beim Hinzufügen eines Dokuments wurde es zuerst zu einem Addon gefaltet. Wenn es voll war oder nach anderen Kriterien, wurde ein permanenter Block darauf gebaut. Falls erforderlich, wurden die benachbarten mehreren Blöcke zu einem neuen zusammengeführt, und die ursprünglichen wurden gelöscht. Das Aktualisieren oder Löschen eines Dokuments hat auf die gleiche Weise funktioniert.

Zusammenführungskriterien, Kettenlänge, Bypass-Algorithmus, Berücksichtigung gelöschter Elemente und Aktualisierungen, andere Parameter wurden optimiert. Der Ansatz selbst war an mehreren ähnlichen Aufgaben beteiligt und nahm als separates internes LSM- Framework auf einem sauberen .net Gestalt an. Etwa zur gleichen Zeit wurde LevelDB populär.

Der LSM- Algorithmus hat in unserem Fall sehr geeignete Eigenschaften:

1. sofortiges Einfügen / Löschen / Aktualisieren,
2. reduzierte Belastung von SSDs während des Updates,
3. vereinfachtes Chunks-Format,
4. selektive Suche nur nach alten / neuen Stücken,
5. triviales Backup
6. was die Seele sonst noch will.
7. ...

Im Allgemeinen ist es manchmal nützlich, Fahrräder zur Selbstentwicklung zu erfinden.

Makro-, Mikro-, Nano-Optimierung

Und schließlich werden wir technische Tipps dazu geben, wie wir im Antiplagiat solche Dinge auf .Net tun (und nicht nur darauf).

Beachten Sie im Voraus, dass oft alles sehr stark von Ihrer spezifischen Hardware, Ihren Daten oder Ihrem Nutzungsmodus abhängt. Nachdem wir uns an einer Stelle verdreht haben, fliegen wir aus dem CPU-Cache heraus, an einer anderen - wir stoßen auf die Bandbreite der SATA-Schnittstelle, an der dritten - beginnen wir, im GC zu hängen. Und irgendwo in der Ineffizienz der Implementierung eines bestimmten Systemaufrufs.

_{Bildquelle: Wikipedia}

Mit Datei arbeiten

Das Problem mit dem Zugriff auf die Datei ist bei uns nicht eindeutig. Es gibt eine große Terabyte-Exabyte- Datei, deren Volumen um ein Vielfaches größer ist als die RAM-Größe. Die Aufgabe besteht darin, die Millionen verstreuter kleiner Zufallswerte zu lesen. Und das schnell, effizient und kostengünstig. Wir müssen viel quetschen, messen und nachdenken.

Beginnen wir mit einem einfachen. Um das geschätzte Byte zu lesen, benötigen Sie:

1. Datei öffnen (neuer FileStream);
2. Bewegen Sie sich zur gewünschten Position (Position oder Suche, kein Unterschied);
3. Lesen Sie das gewünschte Byte-Array (Lesen);
4. Schließen Sie die Datei (Entsorgen).

Und das ist schlecht, weil es lang und trostlos ist. Durch Versuch, Irrtum und wiederholtes Treten auf den Rechen haben wir den folgenden Aktionsalgorithmus identifiziert:

• Einfach offen, mehrfach gelesen

  
  

  Wenn diese Sequenz für jede Anforderung an die Festplatte in der Stirn ausgeführt wird, werden wir uns schnell biegen. Jedes dieser Elemente geht in eine Anfrage an den Betriebssystemkern ein, was teuer ist.

  
  

  Natürlich sollten Sie die Datei einmal öffnen und nacheinander alle Millionen unserer Werte daraus lesen, was wir auch tun

• Nichts extra

  
  

  Das Abrufen der Dateigröße und der aktuellen Position ist ebenfalls recht schwierig. Auch wenn sich die Datei nicht geändert hat.

  
  

  Fragen wie das Abrufen der Dateigröße oder der aktuellen Position sollten vermieden werden.

• Filestreampool

  
  

  Weiter. Leider ist FileStream im Wesentlichen Single-Threaded. Wenn Sie eine Datei parallel lesen möchten, müssen Sie neue Dateistreams erstellen / schließen.

  
  

  Bis Sie so etwas wie Aiosync erstellen, müssen Sie Ihre eigenen Fahrräder erfinden.

  
  

  Mein Rat ist, einen Pool von Dateistreams pro Datei zu erstellen. So vermeiden Sie Zeitverschwendung beim Öffnen / Schließen einer Datei. Und wenn Sie es mit ThreadPool kombinieren und berücksichtigen, dass die SSD ihre MegaIOPS mit starkem Multithreading ausgibt ... Nun, Sie verstehen mich.

• Zuordnungseinheit

  
  

  Weiter. Speichergeräte (HDD, SSD, Optane) und das Dateisystem arbeiten mit Dateien auf Blockebene (Cluster, Sektor, Zuordnungseinheit). Sie stimmen möglicherweise nicht überein, aber jetzt sind es fast immer 4096 Bytes. Das Lesen von ein oder zwei Bytes an der Grenze zweier solcher Blöcke in einer SSD ist etwa eineinhalb Mal langsamer als im Block selbst.

  
  

  Sie sollten Ihre Daten so organisieren, dass die subtrahierten Elemente innerhalb der Grenzen des Clustersektorblocks liegen .

• Kein Puffer.

  
  

  Weiter. FileStream verwendet standardmäßig einen 4096-Byte-Puffer. Und die schlechte Nachricht ist, dass Sie es nicht ausschalten können. Wenn Sie jedoch mehr Daten als die Größe des Puffers lesen, wird letzterer ignoriert.

  
  

  Für zufälliges Lesen sollten Sie den Puffer auf 1 Byte setzen (es wird nicht weniger funktionieren) und dann berücksichtigen, dass er nicht verwendet wird.

• Puffer verwenden.

  
  

  Neben zufälligen Messwerten gibt es auch sequentielle. Hier kann der Puffer bereits nützlich werden, wenn Sie nicht alles auf einmal lesen möchten. Ich rate Ihnen, mit diesem Artikel zu beginnen. Welche Größe des Puffers eingestellt werden soll, hängt davon ab, ob sich die Datei auf der Festplatte oder auf der SSD befindet. Im ersten Fall ist 1 MB optimal, im zweiten Fall sind 4 KB Standard. Wenn die Größe des zu lesenden Datenbereichs mit diesen Werten vergleichbar ist, ist es besser, ihn sofort zu subtrahieren und den Puffer zu überspringen, wie im Fall des zufälligen Lesens. Große Puffer bringen keinen Gewinn in der Geschwindigkeit, treffen aber auf GC.

  
  

  Wenn Sie nacheinander große Teile der Datei lesen, sollten Sie den Puffer für die Festplatte auf 1 MB und für die SSD auf 4 KB einstellen. Nun, es kommt darauf an.

MMF gegen FileStream

Im Jahr 2011 kam ein Tipp zu MemoryMappedFile, da dieser Mechanismus seit .Net Framework v4.0 implementiert ist. Erstens verwendeten sie es beim Zwischenspeichern des Bloom-Filters, was im 32-Bit-Modus aufgrund der 4-GB-Beschränkung bereits unpraktisch war. Aber als ich in die Welt der 64-Bits einstieg, wollte ich mehr. Die ersten Tests waren beeindruckend. Kostenloses Caching, Freak-Geschwindigkeit und praktische Strukturleseschnittstelle. Aber es gab Probleme:

• Erstens, seltsamerweise, Geschwindigkeit. Wenn die Daten bereits zwischengespeichert sind, ist alles in Ordnung. Wenn nicht, ging das Lesen eines Bytes aus der Datei mit einem „Anheben“ einer viel größeren Datenmenge einher als beim normalen Lesen.
• Zweitens seltsamerweise Erinnerung. Beim Erhitzen wächst der gemeinsame Speicher, das Arbeitsset - nein, was logisch ist. Aber dann beginnen sich die benachbarten Prozesse nicht sehr gut zu verhalten. Sie können in einen Tausch gehen oder versehentlich von OoM fallen. Die vom MMF im RAM belegte Lautstärke kann leider nicht gesteuert werden. Und der Gewinn aus dem Cache in dem Fall, in dem die lesbare Datei einige Größenordnungen größer ist als der Speicher, wird bedeutungslos.

Das zweite Problem konnte noch bekämpft werden. Es verschwindet, wenn der Index im Docker oder auf einer dedizierten virtuellen Maschine funktioniert. Aber das Geschwindigkeitsproblem war fatal.

Infolgedessen wurde der Geldmarktfonds etwas mehr als vollständig aufgegeben. Das Caching im Anti-Plagiat begann in expliziter Form, wobei nach Möglichkeit die am häufigsten verwendeten Ebenen mit den angegebenen Prioritäten und Grenzen gespeichert wurden.

_{Bildquelle: Wikipedia}

Bits / Bytes

Nicht Bytes die Welt ist eins. Manchmal muss man auf die Bitebene gehen.

Beispiel: Angenommen, Sie haben eine Billion teilweise geordneter Nummern, die häufig gespeichert und gelesen werden sollen. Wie arbeite ich mit all dem?

• Einfacher BinaryWriter.Write? - schnell aber langsam. Größe ist wichtig. Das kalte Lesen hängt hauptsächlich von der Größe der Datei ab.
• Eine andere Variante von VarInt? - schnell aber langsam. Konsistenz ist wichtig. Die Lautstärke hängt von den Daten ab, für deren Positionierung zusätzlicher Speicher erforderlich ist.
• Bitverpackung? - schnell aber langsam. Sie müssen Ihre Hände genauer kontrollieren.

Es gibt keine ideale Lösung, aber im speziellen Fall wird durch einfaches Komprimieren des Bereichs von 32 Bit auf das zum Speichern der Schwänze erforderliche 12% mehr (zig GB!) Als durch VarInt gespart (wobei natürlich nur der Unterschied der benachbarten gespeichert wird), und das mehrmals Grundoption.

Ein weiteres Beispiel. Sie haben einen Link in einer Datei zu einem Array von Zahlen. Link 64-Bit-Datei pro Terabyte. Alles scheint in Ordnung zu sein. Manchmal gibt es viele Zahlen im Array, manchmal wenige. Oft ein bisschen. Sehr oft. Nehmen Sie dann einfach das gesamte Array und speichern Sie es im Link selbst. Gewinn Sorgfältig verpacken, aber nicht vergessen.

Struktur, unsicher, Dosierung, Mikrooptionen

Gut und andere Mikrooptimierung. Ich werde hier nicht über das Banale schreiben: "Lohnt es sich, die Länge des Arrays in einer Schleife zu speichern?" Oder "Was ist schneller, für oder für jeden?".

Es gibt zwei einfache Regeln, an die wir uns halten werden: 1. "Alles messen", 2. "Mehr Benchmark".

• Struct . Überall verwendet. GC nicht versenden. Und wie es heute in Mode ist, haben wir auch unsere eigene mega-schnelle ValueList.

• Unsicher . Ermöglicht die Zuordnung (und Nichtzuordnung) von Strukturen zu einem Array von Bytes, wenn diese verwendet werden. Daher benötigen wir keine separaten Serialisierungsmittel. Es gibt zwar Fragen zum Fixieren und Defragmentieren des Haufens, aber bisher wurde dies nicht gezeigt. Nun, es kommt darauf an.

• Batching . Die Arbeit mit vielen Elementen sollte über Packs / Gruppen / Blöcke erfolgen. Datei lesen / schreiben, zwischen Funktionen übertragen. Ein separates Problem ist die Größe dieser Packs. Normalerweise gibt es ein Optimum, und seine Größe liegt häufig im Bereich von 1 KB bis 8 MB (CPU-Cache-Größe, Cluster-Größe, Seitengröße, Größe von etwas anderem). Pumpen Sie durch die Funktion IEnumerable <Byte> oder IEnumerable <Byte [1024]> und spüren Sie den Unterschied.

• Pooling . Jedes Mal, wenn Sie "neu" schreiben, stirbt irgendwo ein Kätzchen. Einmal neues Byte [ 85000 ] - und der Traktor ritt eine Tonne Gänse. Wenn es nicht möglich ist, stackalloc zu verwenden, erstellen Sie einen Pool von Objekten und verwenden Sie ihn erneut.

• Inlining . Wie kann man zwei Funktionen anstelle einer erstellen, um alles zehnmal zu beschleunigen? Einfach. Je kleiner der Funktionskörper (Methode) ist, desto wahrscheinlicher ist es, dass er inline ist. Leider gibt es in der Dotnet-Welt immer noch keine Möglichkeit, partielles Inlining durchzuführen. Wenn Sie also eine Hot-Funktion haben, die in 99% der Fälle nach der Verarbeitung der ersten paar Zeilen herauskommt und die verbleibenden hundert Zeilen die verbleibenden 1% verarbeiten, teilen Sie sie sicher in zwei (oder drei), die den schweren Schwanz in eine separate Funktion tragen.

Was noch?

• Span <T> , Memory <T> - vielversprechend. Der Code wird einfacher und vielleicht etwas schneller. Wir warten auf die Veröffentlichung von .Net Core v3.0 und Std v2.1, um zu ihnen zu wechseln, weil unser Kernel auf .Net Std v2.0, der normalerweise keine Spans unterstützt.

• Async / warten - bisher umstritten. Die einfachsten Benchmarks für zufälliges Lesen zeigten, dass der CPU-Verbrauch tatsächlich sinkt, aber auch die Lesegeschwindigkeit abnimmt. Muss aufpassen. Innerhalb des Index verwenden wir ihn noch nicht.

Fazit

Ich hoffe, dass meine Abgeschiedenheit Ihnen Freude macht, die Schönheit einiger Entscheidungen zu verstehen. Unser Index gefällt uns sehr gut. Es ist effizienter, schöner Code, funktioniert großartig. Eine hochspezialisierte Lösung im Kern des Systems, dem kritischen Ort seiner Arbeit, ist besser als die allgemeine. Unser Versionskontrollsystem merkt sich Assembler-Einfügungen in C ++ - Code. Jetzt gibt es vier Pluspunkte - nur reines C #, nur .Net. Darauf schreiben wir selbst die komplexesten Suchalgorithmen und bereuen es überhaupt nicht. Mit dem Aufkommen von .Net Core, dem Übergang zu Docker, ist der Weg in eine glänzende DevOps-Zukunft einfacher und klarer geworden. Vor uns liegt die Lösung des Problems der dynamischen Shardisierung und Replikation, ohne die Effektivität und Schönheit der Lösung zu beeinträchtigen.

Vielen Dank an alle, die bis zum Ende gelesen haben. Für alle Unstimmigkeiten und sonstigen Inkonsistenzen schreiben Sie bitte Kommentare. Ich freue mich über jeden vernünftigen Rat und jede Widerlegung in den Kommentaren.