Wie funktioniert die Suche?

    Andrey Aksyonov

    Andrey Aksenov ( Shodan , Sphinx-Suchmaschinenentwickler)


    Die Suche ist folgendermaßen organisiert: Die

    Schnellsuchgerät

    Indizierung ist im Großen und Ganzen nichts Kompliziertes. Es ist klar, dass im Großen und Ganzen in jedem der drei „Details“ nicht nur der Dämon verborgen ist, sondern die ganze Herde, irgendwo eine Legion, es ist nicht ganz klar. Das Konzept ist aber immer einfach. Alles beginnt mit einem einfachen kleinen Patch für Mnogoserch, und dann machst du diesen Müll seit 15 Jahren.

    Sie nehmen die Dokumente und unterteilen sie in Stichwörter. Nehmen Sie das Dokument und unterteilen Sie es in die Schlüsselwörter "Mutter, Seife, Rahmen". Sie sind nicht weit von grep entfernt, da Sie diese Schlüsselwörter dann sowieso sortieren. Es ist notwendig, etwas Besonderes zu bauen. Struktur ist ein Volltextindex. Einmal hatte die Menschheit viele Möglichkeiten, es zu bauen, aber Gott sei Dank lehnte sie alle ab und in normalen Produktionssystemen gewann im Großen und Ganzen genau eine Option. Ich werde über ihn reden. Alle anderen haben eher historische Bedeutung oder ähnliches und sind nicht von praktischem Interesse.




    Dann, wenn wir so besonders sind. Es wurde eine magische Struktur namens "Index" erstellt, die leider nicht nur durchsucht werden muss. Relativ gesehen reicht Ihnen eine Textsuche im Allgemeinen noch nie aus. Das heißt Ich kann mir einen solchen Anwendungsfall nicht vorstellen, wenn Sie nur Textdaten für eine Suche benötigen. Wenn Sie nach Protokollen suchen, müssen Sie einen Schlüssel oder eine Maske suchen und höchstwahrscheinlich die Daten sortieren, gruppieren oder einige zusätzliche Vorgänge ausführen. Nur Text ist nicht genug für Sie. Um zu finden, müssen Sie noch mindestens nach Datum sortieren oder die Anzahl der Dateien in der Tabelle angeben und die Suchergebnisse nach Tag usw. gruppieren.

    Wenn Sie eine illusorisch einfache Websuche betreiben ... oder eine Websuche, eine Art Suche in einer lokalen Sammlung von juristischen Dokumenten, die anscheinend ausreichte, um alles zu finden, zu arrangieren und - hurra, hier ist es. Nicht so eine verdammte Sache. Auch der Text reicht dafür nicht aus, denn bei der Websuche im Allgemeinen die Hölle und der Holocaust. Das Ranking basiert nicht nur auf dem Text der Dokumente, sondern auch auf Dutzenden und Hunderten weiterer Faktoren. Und selbst bei einer vernünftigen Desktopsuche nach einer ziemlich interessanten Sammlung wird es neben dem Text noch viel mehr geben.

    Ich habe viele kostbare Sekunden damit verbracht zu erklären, dass es ein Extra gibt. Verarbeitung, und wenn es früher Ideen gab, die in der Regel nicht benötigt werden, gibt es heute keine solchen Ideen. Überall und immer wirst du definitiv eine Art ext haben. verarbeitung. Im Prinzip habe ich keine einzige Anfrage gesehen, die nur einen Volltextabgleich durchführen und einfach nach einer Art Brute-Force-Relevanz sortieren würde. Das ist natürlich übertrieben. Es ist klar, dass Sie bei der Suche in einem Forum höchstwahrscheinlich einen Standardmodus verwenden. Dies ist die Sortierung nach dieser Relevanz, wenn Sie sich nicht wirklich darum kümmern. Aber Sie müssen verstehen, dass Sie in diesem Fall immer noch drei Übereinstimmungen für Ihre göttlichen 2000 Posts für die durchschnittliche Anfrage haben und da Sie sie nicht sortieren, erhalten Sie immer noch drei Übereinstimmungen.



    Daten sind alles. Um zu verstehen, wie es angeordnet ist, müssen Sie natürlich aus den Daten tanzen, mit denen wir arbeiten, aus dem Gerät desselben Specials. eine magische Struktur namens "Volltextindex".

    Tatsächlich ist der Volltextindex in erster Linie völlig dumm wie ein Stab. Da ist er:



    Der Index sieht so aus. In der Tat sieht es völlig falsch aus, in der Tat ist alles viel komplizierter. Sobald Sie jedoch über den ersten Entwurf hinausgehen, den Sie auf Ihr Knie geschrieben haben, werden alle Metainformationen an das Wörterbuch angehängt. Dokumentenlisten werden nicht nur benötigt, sondern auch Positionslisten, einige morphologische Informationen sind in diesen Positionslisten gespeichert ... Und dann herrscht immer noch große Freude, und die Zuschreibung auf der Seite liegt irgendwo. Aber ich wiederhole es in erster Näherung: Visualisierung dieser Struktur.

    Hier wurde ein bestimmter obskurer Pfeiloperator (=>) eingeführt, der nicht 2/3 des Operators zum Vergleichen von zwei Elementen zum Sortieren ist, der in alle Arten von esoterischen Sprachen geschoben wird. Dies ist eine Art Verbindung, die besagt, dass wir ein separates Wörterbuch haben - die linke Spalte. Wenn wir die rechte Hälfte verstecken, haben wir ein Wörterbuch und einen Pfeil - dies ist auch Teil des Wörterbuchs. Wir können davon ausgehen, dass dies für jedes Wort ein anderer Zeiger ist. Er verweist entsprechend auf die Dokumentenliste. Nach diesem Wörterbuch können wir alle Dokumente finden, in denen "abyrvalg" gefunden wird - es gibt offensichtlich 123; oder alle Dokumente, in denen es Petja Petrow gibt - offensichtlich sind dies die Dokumente Nr. 8 und 2. Und aus irgendeinem Grund wird Wassja Wasseschkin nirgendwo gefunden. Kein Glück, Vasya.



    In der Tat ist das Element des Wörterbuchs nicht nur ein Wort, es gibt typischerweise noch zusätzliche Füllung. Hier ist ein Beispiel für Hackfleisch am Ende. Zum Beispiel das Wort selbst, erstens ein Versatz zur Liste der Dokumente, zweitens ein Versatz zur Liste der Positionen, drittens ... Darüber hinaus könnte all dies in die Listen selbst gestellt werden, in separate Dateien, in denen wir zeigen, und damit mehr kompaktes Wörterbuch zu tun. Aber dann ist es laut Wörterbuch selbst nicht klar, aber wie oft kommt dieses Wort vor? Und die Häufigkeit dieses Wortes selbst oder die Häufigkeit der Positionen wird benötigt, um einerseits einen optimaleren Abfrageplan zu erstellen und andererseits Statistiken zu Schlüsselwörtern zu erstellen, ohne die grundlegenden gesunden Indexdaten abzurufen. Außerdem können einige zusätzliche Informationen gespeichert werden. So speichern wir die Feldmaske in Sphinx,

    Auch hier kann sich alles als etwas falsch herausstellen, dies ist ein erfundenes Beispiel, wenn das so ist. Das heißt Tatsächlich ist dies bei Open-Source-Systemen, die auf der Welt verfügbar und für normale Menschen zugänglich sind, nicht der Fall. Was ist in Sphinx, was ist in Lucene, das Wörterbuch ist eigentlich anders, mit unterschiedlichen Daten, einem etwas anderen Format usw. Aber konzeptionell unterscheidet es sich nicht viel. Das heißt Ja, das ist nicht so, etwas andere Felder, wir haben keinen Positionsversatz, und das ist es.

    Ein weiterer interessanter Punkt, der wahrscheinlich erwähnenswert ist, ist, dass Zeiger möglicherweise nicht immer gespeichert werden, was bedeutet, dass die Daten nur inline sind und das Wörterbuch danach geschüttelt werden sollte. Das heißt Nicht nur solche Strukturen sind

    sozusagen ... Wie führt ein Hipster eine Suche durch? Er nimmt solchen Müll, ein json-Dokument, auf die Festplatte und lädt es dann in jQuery ...



    Aber es funktioniert nicht gut genug, nicht effizient genug. Daher ist es erstens nicht erforderlich, ein JSON-Dokument mit all diesen Daten zu erstellen, sondern natürlich in einem Binärformat. Zweitens wäre dieses Wörterbuch gut zu rütteln, damit es mehr oder weniger kompakt ist und gut funktioniert. Um eine schnelle Suche zu ermöglichen, erstellen wir einen sortierten Vektor. Idealerweise und in der Praxis wäre es natürlich notwendig, nur einen Hash für die Suche zu erstellen. Natürlich wurde mit allen Wörtern ein Hash erstellt und dann sofort ein bestimmtes Wort gesucht.

    Es gibt jedoch zwei Probleme mit dem Hash:

    1. Es wird eine sofortige Suche geben, aber dann ist es notwendig, vollständig unkomprimierte Elemente im Wörterbuch zu behalten, und aus diesem Grund schwillt es viermal an.
    2. Wenn Sie einen Hash haben, gibt es außerdem keine Bereichssuche im Hash und im Allgemeinen nicht nach physischen Einschränkungen. Suchen Sie daher nach Teilzeichenfolgen. Grundsätzlich haben wir Sie sofort gehasst, aber Benutzer fordern ständig aus irgendeinem Grund. Natürlich hätte ich einen Hash erstellt, aber ich verstehe die Suche nach Teilzeichenfolgen nicht.

    Das größte Glück bei der Komprimierung im Wörterbuch ... Natürlich möchte ich jetzt keine konkreten Zahlen nennen, da "genau 37% der gesamten Komprimierung auf diese und die restlichen 69% auf eine andere zurückzuführen sind", aber der Großteil der Komprimierung im Wörterbuch liegt nach Ihnen Sortanul im menschlichen, dann normalen Wörterbuch wird durch das Präfix der Sprache erreicht. Das heißt Menschen sind im Gegensatz zu Robotern eher dumme und begrenzte Wesen, und daher ist das Wörterbuch aller menschlichen Sprachen gleichzeitig extrem klein. Was war eigentlich das Lexikon von Puschkin? Übrigens ist alles ein Denkmal, fast in jeder Stadt, und es gibt sicherlich Straßen. Ein Lexikon, Gott bewahre, 30 Tausend Lem. Nun, wie viele dieser 30.000 Lems können Wortformen erzeugen? Schlafen Sie nicht, kommunizieren Sie, maximal 200 Tausend.

    Nehmen Sie jemanden, der akademischer ist als Puschkin, zum Beispiel das klassische morphologische Wörterbuch von Zaliznyak und alles, was allmählich aus ihm herauswuchs. Die Reihenfolge in russischer Sprache ist 100-200 Tausend lem mehr oder weniger laufend, und natürlich ist die russische Sprache aus der Sicht des Programmierers immer noch ziemlich wandelbar und aus der Sicht eines Menschen, der die Philologie nicht vergessen hat, wenn er es sofort wusste. Und dies bedeutet, dass aus jedem spezifischen Lem, aus jedem spezifischen Root, viele verschiedene Präfixe generiert werden können - Laufen, Laufen, Laufen, Laufen, Laufen usw. In der russischen Sprache gibt es viele solche Deklinationen, daher gibt es viele Wortformen. Jede Wortform in der Begrenzung wird als separates Wort indiziert. Aber selbst sie, sogar das ganze Wörterbuch, sehen erbärmlich aus. Dies ist tatsächlich: 1. sehr klein und 2. sie ähneln sich als Zwillingsbrüder.

    Nachdem Sie das Lexikografische Wörterbuch sortiert haben, erhalten Sie ... Und Sie haben natürlich auch Tippfehler. Menschen - sie sind sozusagen dumm und begrenzt, und dies äußert sich nicht nur in der Tatsache, dass das Wörterbuch ziemlich begrenzt ist, sondern auch in der Tatsache, dass sie ständig danach streben, auf irgendeine Art und Weise alltäglich zu schreiben. Entweder fällt ihnen ein Albaner ein, dann der Drecksack, dann sind sie einfach stumpf und versiegelt, wie ich zum Beispiel in jedem anderen Wort Gott sei Dank, dass die Autokorrekturen behoben haben. Und es stellt sich heraus: Abyr, Abyrrr, Abyrvalg, etc.

    Es gibt keine menschliche Möglichkeit, zusätzliche 8 Bytes für jeden verdammten Abyr zu speichern, da es in Unicode genau 8 Bytes sind. Es ist viel interessanter, das Präfix "Abyr" einmal zu speichern und dann, zum Beispiel "Abyrr", den kleinen Code in ein paar Bits zu speichern, was kürzer ist. Jetzt fügen wir am Ende ein +1-Zeichen hinzu und speichern dieses Zeichen und fügen dann zwei weitere Zeichen hinzu am Ende, und dann schneiden Sie zwei ab und speichern Sie die "valg". Durch diesen einfachen Trick wird, wie ich betone, das Wörterbuch der menschlichen Sprache sehr stark verkleinert.

    Leider hilft das nichts gegen Bots. Ich hasse Bots mit heftigem Hass, weil es an den Bots liegt, die alle Arten von intelligenten URLs, alle Arten von session_ID, utm_campaign und alle anderen Stuffing-Sitzungen generieren - aus diesem Grund schwillt Ihr Wörterbuch an, wenn Sie beispielsweise url indizieren höllische Entfernungen, und nichts Besonderes kann damit getan werden. Sie haben eine solche session_ID zufällig und spärlich, und es gibt keine Präfixe. Dieser Mist saugt das Wörterbuch.

    Für eine normale Sprache mit einem Wörterbuch ist alles interessant. Hier beklagte er sich zum Leben, dass für alle automatisch generierten Daten mit einem Wörterbuch alles schlecht ist. Eigentlich schlecht, aber nicht schlecht, schlecht. Das Wörterbuch ist in einigen Fällen hässlich, wenn Sie keinen echten Text haben, aber es gibt viele, viele automatisch und zufällig generierte Daten. Wenn Sie also 100 Millionen eindeutige Stichwörter zufällig generieren und indizieren, haben Sie natürlich den größten Teil der Indizes im Wörterbuch. Sie im Großen und Ganzen entartet der gesamte Index in ein Wörterbuch. Glücklicherweise sind die Daten in den normalerweise indexüblichen Sammlungen mehr als aussagekräftig. Daher gibt es neben dem Wörterbuch auch grundlegende Daten, Dokumente und Positionen.

    Ich habe viel über Präfixe gesprochen und vergessen, über Inlining zu sprechen. Inlining ist eine extrem dumme Sache. Warum sollte ein Versatz von acht Bit pro Dokument gespeichert werden, wenn Sie nur ein Dokument und eine Position haben? Mit diesem einfachen Trick haben wir vor einigen Jahren in Sphinx mit einem Schlag und einem einfachen Upgrade die Größe des Index meiner Meinung nach entweder um 30% oder um 40% reduziert. Und dann wurde uns in Lucene diese Idee gestohlen, oder sie ist unabhängig entstanden, was tatsächlich wahrscheinlicher ist.



    Der größte Teil des Index besteht jedoch aus Dokumenten und Positionen. Dies sind nur sortierte Listen. Immer sortiert, sonst nichts. Andernfalls können sie nicht effektiv gekreuzt werden, wenn Sie gleichzeitig nach zwei Schlüsselwörtern suchen. Wahrscheinlich versuchen sie, sie nicht zu sortieren, sondern nach einem leichten Rang usw. zu sortieren. nur zwei Kategorien von Personen. Erstens sind dies Typen, die ihre Dissertation wirklich verteidigen müssen, sonst werden sie den Militärkommissar rufen. Und die zweite Kategorie von Leuten sind Leute, die ihre Dissertation verteidigen müssen, weil dies bedeutet, dass die interne Karriereleiter von Yandex und Google verbessert wird. Ich habe keine anderen wissenschaftlichen Arbeiten zu diesem Thema gesehen, d.h. Es gibt keinen Beweis dafür, dass Sie Dokumente auf eine unnatürliche Weise und nicht in einer natürlichen, nach ID sortierten Reihenfolge geschickt und effizient ablegen können.

    Positionen Positionen werden zu einem Zeitpunkt benötigt, an dem Sie erstens nach mehr als einem Keyword suchen, um ein Ranking zu erstellen, und zweitens, wenn Sie einen weniger trivialen Suchoperator haben, als nur "Gib mir alles und verdammt". Es ist klar, dass, wenn Sie nach einer Phrase suchen, dann die exakte Übereinstimmung der Phrase, ganz zu schweigen von der Suche in der Nähe usw., Sie sofort Positionen benötigen. Auch wenn Sie diese Daten später nicht einstufen, müssen Sie nur die Position betrügen, um die Phrase zu erfassen. Und wenn Sie zumindest eine Rangfolge benötigen, dann möchte eine mehr oder weniger vernünftige Rangfolge auch Positionen betrachten und dies sehr langsam tun.

    Es gibt eine Menge dieser Daten, es gibt wirklich eine Menge davon. Denken Sie selbst, für jedes Vorkommen jedes Wortes in jedem Dokument müssen wir irgendwo eine interne Dokumentennummer speichern. Tatsächlich spielt es für die Suchmaschine keine Rolle, ob die Nummer extern oder intern ist, aber wir müssen sie speichern. Grob gesagt sind solche Daten mindestens so groß wie der ursprüngliche Text, und wenn schlampig und viel Aufwand ungenau ist, dann um ein Vielfaches mehr als der ursprüngliche Text. Es gibt keine menschliche Möglichkeit, mit einem Index zu arbeiten, der dreimal so groß ist wie der ursprüngliche indizierte Text. Es ist langsam, schlecht und im Allgemeinen frisst das Gedächtnis. Es ist wesentlich besser, alles geschickt zu schütteln, damit es nicht 300% der Größe des Ausgangstextes einnimmt, sondern idealerweise 5%. Wenn Sie 60-mal weniger Daten haben, arbeitet natürlich jede Operation mit diesen Daten schneller.

    Kompression Komprimierung ist alles. Plötzlich über Implementierungsdetails in bestimmten Suchmaschinen.



    Soweit ich mich erinnere, sehen die Hauptdaten, die im Volltextindex gespeichert sind, in Lucene heute so aus. Separat gibt es einen Stream mit Blöcken geernteter Ausweisdokumente. Abgesehen davon sind zusätzlich grob gesagt in einer separaten Datei oder bei separaten Offsets Frequenzblöcke, d.h. nicht nur die Tatsache, dass wir hier Dokumente 1, 2, 3 und 17 haben, sondern auch die Tatsache, dass in Dokument Nr. 1 die Häufigkeit des dreifachen Auftretens des Wortes in Dokument Nr. 2 - 17 usw. vorkam. Ein solcher Häufigkeitsblock in einem bestimmten Dokument. Dieser Frequenzblock bestimmt natürlich die Länge der Anzahl der Positionen für den dritten Megavektor, in denen bestimmte Positionen gespeichert sind. Dort ist dementsprechend, wie viel tf im Block ist, so viel Daten in den Buchungen.

    Dementsprechend speichern Jungs dies mit drei verschiedenen Strömen. Diese Daten werden nicht verwechselt. Bei uns sind sie in der aktuellen Version etwas durcheinander, d.h. docids, tfs, Häufigkeiten nach Dokumenten sowie einige kleine zusätzliche Metainformationen, insbesondere ein Offset zur Liste der Posts, und meiner Meinung nach gibt es einige einfache Tricks zur Anzahl der Posts, eine Maske, die nicht immer vorhanden ist usw. Wir haben einen solchen Grundgedanken für diejenigen, die an der Indexdatei mit der SPD-Erweiterung interessiert sind, und separat liegt die Datei, in der alle Positionen liegen.

    Und wieder funktioniert Inlining gut. Wenn Sie eine Position haben, müssen Sie diese speichern und keinen Zeiger darauf speichern. In diesem Fall, wenn Sie genau eine Position haben, genau ein Vorkommen, entspricht dies auch der allgemeinen Megakischka von Dokumenten.

    Wie es in der seit langem vorbereiteten Neufassung arrangiert wird und worüber ich in letzter Zeit zu reden begonnen habe, weiß ich noch nicht. Zuvor funktionierte das Layout im Prototyp ziemlich cool, wenn wir im Allgemeinen alle Daten gemischt haben, d. H. und docids und postings liegen in einem glatten darm. Das ist schlecht, weil Sie, wenn Sie nur die Bezeichner von Dokumenten benötigen und grob gesagt, nach einem Schlüsselwort suchen, die Positionen und Vorkommen dieses Wortes im Dokument absolut egal sind. Sie haben in diesem Fall nicht mehr die Möglichkeit, die relativ kleine Liste der Dokumentenkennungen anzusehen, sie wegzuwerfen und die Positionsnummern überhaupt nicht mehr anzusehen. Andererseits wird auf diese Weise die Gesamtgröße des Index spezifisch reduziert und der Code vereinfacht. Dementsprechend hat sich noch nicht entschieden. Einerseits möchte ich Posts separat verschieben, Nur um solche Ein-Wort-Suchen oder Booleschen Suchen zu optimieren, bei denen Positionen im Allgemeinen nicht benötigt werden. Andererseits erhöht es den Index erheblich. Muss noch nachdenken, Benchmarking, etc.

    Ich denke, es wird besonders lustig und ironisch sein, wenn irgendwo in der Halle ein miserabler Kosake von Google sitzt, leise grinst und sich denkt, dass "mit uns alles nicht stimmt". Dies ist nicht die einzige Methode, um ein Format zu erstellen, und vor allem nicht die einzig wahre. Es gibt viele Experimente, wie wir diese Daten speichern können (Listen von Dokumenten und Listen von Positionen), es ist notwendig, sie irgendwie effizient zu speichern und dann effizient zu lesen und zu arbeiten. Die Experimente werden wahrscheinlich nie aufhören.

    Ich erinnere mich vage, dass ich einmal ein Stück Papier von Google gelesen habe. Google ist im Allgemeinen ein bekanntes "offenes", "Open Source" -Unternehmen. Sie können keinen Patch nach außen geben und kein einziges Dokument, das jünger als fünf Jahre ist. Aber ich habe trotzdem ein Dokument gelesen, das unklar ist, wie alt es ist, in dem kurz und knapp erwähnt wurde, dass Google ein noch interessanteres Format hat, um alles zu speichern. Anstatt einige separate Listen von Dokumenten, tfs und anderen Dingen zu speichern, speichern sie eine riesige Liste von Positionen. Oder war es eine Art Experiment, Google oder Battle Index? Als "offene" Firma ist nichts zu verstehen. Aber ich erinnerte mich an die folgende Idee, die auf jeden Fall interessant war - eine gigantische allgemeine Liste von Positionen wurde im Übrigen dicht gehalten. Wie hier haben wir das erste Dokument, es hat 1000 Wörter bzw. es besetzt die Positionsnummern vom 1. bis zum 1000., und hier ist das zweite Dokument, es hat 12 Wörter, es nimmt Positionen von 1001 bis 1012 ein, und hier ist das dritte Dokument usw. Und sozusagen las ich beiläufig, dass das coole Format gut geworden ist und die Grenzen von Dokumenten durch externe Metainformationen bestimmt werden, d. H. separat liegt ein so kleiner Darm, in dem die spezifischen Ränder der Dokumente ausgeschrieben sind, dass bei uns der erste von Position Nr. 1 aus und endete bei Nr. 1000, der zweite - von Nr. 1001 aus und endete bei Nr. 1012 einschließlich usw.

    Die Daten sind wie folgt - siehe Folie oben. In Lucene, in Sphinx - in Sphinx der nächsten Version - ist nicht klar, wie und für "große Onkel" auch nicht klar, wie sie sich regelmäßig ändern. Warum erzähle ich das alles? Egal, egal. Aber es ist gut, wenn Sie sich keine Gedanken darüber machen, mit was Sie arbeiten werden, vor allem, wenn Sie darüber gesprochen haben, wie es im Inneren funktioniert, aber leider beeinflusst dieses Geschäft zwei wichtige Merkmale ziemlich gut - die Geschwindigkeit von allem und ein anderes Volumen.



    Denn selbst der Codierungsmechanismus der Daten, die Sie in den Index aufnehmen wollten, ändert das Volumen dieser Daten und zumindest die Lesegeschwindigkeit für die Verarbeitung dieser Daten in einem Zeitraum, der etwas kürzer als unendlich ist. Und über "ein bisschen weniger als unendlich" - das ist kein Witz. Hier ist ein Beispiel für ein Frequenzwort. In der Tat ist das Wort "was" weniger häufig. Das meiner Meinung nach häufigste Wort in russischer Sprache ist nicht das, was Sie dachten, sondern die Präposition "und", aber es ist gut für ein Beispiel. Angenommen, wir haben eine solche Liste von Dokumentenkennungen [1,3,4,5,6 usw.]. Es wächst und es hat ziemlich dichte Dokumente. Warum müssen wir große Mengen speichern, die im Allgemeinen nach und nach auf eine Million anwachsen und viele Bits benötigen? Zählen wir die Deltas zwischen den benachbarten Ziffern. Ich habe gezählt und es stellte sich heraus [1,2,1,1,1,4 ... etc]. Vielleicht habe ich mich irgendwo verrechnet aber nicht der Punkt. Es ist wichtig, dass die absolute Reihenfolge der Ziffern im zweiten Vektor, der mit "varint" gekennzeichnet ist, deutlich kleiner ist. Nehmen wir also einfach diese kleinen Ziffern und kodieren sie mit einer variablen Anzahl von Bytes. Sieben-Bit-Werte - 8 Bytes, 14-Bit-Werte - 16 Bytes usw. Einige haben bereits geraten, wie das geht, und in nur vier Stunden werden sie die Implementierung in PHP schreiben und rausschmeißen.

    Anstelle von 32 Bit oder Gott verbietet sogar 64 Bit für jede ID, speichern wir, Gott schütze, im Durchschnitt 8 Bit. Und natürlich stoßen wir gelegentlich auf einige hässliche Spitzen, wenn die Hauptliste sofort von 11 Millionen auf 12 Millionen springt. Es wird 12 Millionen minus 11 Millionen geben, für diesen Wert werden 24 Bits benötigt, für dieses Delta, und es ist immer noch in vier Bytes codiert. Sie können es nicht in drei Schritten codieren, da Sie einen zusätzlichen Codierungsaufwand haben. Im Durchschnitt haben Sie jedoch ein Byte und nicht vier.

    Plötzlich sind die Daten viermal zusammengebrochen, und dies ist eine Wissenschaft vor 20 Jahren. Moderne Wissenschaft (also erst vor 10 Jahren) ist also ein lustiger Blockcode, der erstens einen weiteren subtrahiert, weil Sie ein Delta haben müssen - Ihre Zahlen beginnen bei einem, nicht bei Null. Subtrahiert man - Bitik gespart. Es stellt sich heraus, dass so etwas und eine Folge dieser Nullen und Einsen (gelegentlich dreifach), sie können je nach Annäherung an das Projektil und manchmal in 0 (Null) -Bit codiert werden. Ich meine, wenn Sie einen ausreichend langen Block haben, in dem es ausschließlich Nullen gibt, d.h. Sie haben viele Dokumente, die der Reihe nach übereinstimmen - ein Block von beispielsweise 128 Dokumenten in einer Reihe, 1,2,3, ein sehr häufiges Wort. Oder Sie haben nur die Posten derselben Person aus dem Blozik geraubt, und offensichtlich ist seine Rassel in all diesen Dokumenten hintereinander zu finden. Und es passiert. Natürlich sind Deltas zwischen benachbarten ID-Dokumenten eins nach dem anderen und alle Konstanten, und diese Tatsache kann relativ gesehen mit 0 Bits pro Dokument plus einem kleinen festen Overhead verwackelt werden. Wir schreiben ein Byte, das heißt, die nächsten 128 Deltas, die wir haben. Ein solches Glück in realen Daten ist in der Tat äußerst selten. Wenn ich mich an meine Versuche mit dem Codec richtig erinnere, hat das Codieren der Blöcke mit genau null Bits nicht viel Spaß gemacht, aber das Codieren eines ausreichend großen Blockes von Dokumenten in ein, zwei oder drei Bits im Vergleich zu acht reduziert die Indexgröße erneut um ein Vielfaches . Ich hoffe, der Effekt ist verständlich - es ist eine Sache, wenn wir 100 MB von der Festplatte oder aus dem Speicher lesen und schaufeln müssen. Wenn wir überhaupt keine Daten geerntet haben, hat varint 25 MB geerntet, der Codec ist anständiger, dann drückt er sehr gut. Ich glaube,



    Plötzlich erinnern wir uns an die üble Tatsache, dass es zusätzlich zum Text im Index diese sehr göttlichen Ziffern gibt, d. H. bestimmte Arten von Metainformationen, die an ein Dokument gebunden sind, Zuordnung in der einen oder anderen Form. Das heißt Daten, die wir nicht mit einem Volltext-Indexer indizieren, die aber dennoch vorhanden und zusammengesetzt sein müssen, weil zusätzliche Operationen auf ihnen unvermeidlich sind. Die offensichtlichen sind Filtern, Gruppieren, Sortieren. Weniger offensichtlich sind Rangfolgen einerseits und einfache Speicherung andererseits in dem Moment, in dem Sie aus einer Suche plötzlich eine gekrümmte Datenbank machen.

    Leider hat die Menschheit im Moment viele Konzepte und eine Million verschiedene Speichermethoden entwickelt, und eine bestimmte hat noch nicht gewonnen. Die Daten können wir sozusagen als relational mit einem fest vorgegebenen Schema bezeichnen. Im Gegenteil, wir können sagen, dass wir völlige Dynamik und Ausschweifung wollen und daher eine völlige Schematik haben. Danach können Sie Daten auch auf verschiedene Arten speichern.

    Nicht-relationale Daten können schief gespeichert werden. Einerseits werden Schemata normalerweise besonders gut aufbewahrt, d. H. Im besten Fall in einer Art Binärformat.

    In dieser Hinsicht lässt mich die Geschichte von PostgreSQL, die json unterstützt und in der ersten Iteration beibehalten hat, nicht los, mich zu überraschen. Im Allgemeinen ohne zusätzliche Versuche, die Arbeit mit diesem Json irgendwie zu beschleunigen.

    Gott sei Dank, auch Lucene speichert Daten nicht so schrecklich, aber soweit ich weiß (ich kann hier wilde Fehler machen, weil ich sie nicht jeden Tag anschaue). Sie haben das sehr sehr flexible Innere, aber dementsprechend wird die Bremsstruktur, die ich liebevoll FlexiTormoz nenne, zumindest diese Datenstruktur verwendet, um zusätzliche Attribute in einer Standardweise zu speichern. Das heißt Wenn Sie das Attribut speichern, wird die relationale Verbündeten-Datenbank nicht mit extrem schnellem Zugriff erstellt, sondern relativ gesehen wird das json-Dokument gespeichert. Oder vielmehr ein Bson-Dokument in einem Binärformat, bei dem der Zugriff schneller ist als das Parsen von Text. Und damit sich das alles nicht so höllisch verlangsamt, ist alles mit mehrstufigen Caches ausgestattet, so dass nach dem ersten Mal der Zugriff schnell und nach dem ersten Mal der Zugriff sehr langsam ist.

    Bei Sphinx heißt die Lösung nicht, dass es grundsätzlich besser ist, aber an manchen Stellen funktioniert es, scheint es mir trotzdem fröhlicher. Im Gegenteil, wir haben einen höllisch relationalen Ansatz, einen riesigen Tisch mit einem festen Schaltkreis im Speicher, was natürlich unpraktisch ist, wenn Sie spärliche Daten wie json dort hochladen möchten. Aber wir wollen es wahrscheinlich nicht ablehnen, weil ich glaube, dass eine Person die Wahl haben sollte - entweder sie schießt sich in den Kopf oder sie schießt sich in die Arterie an seinem Bein und blutet. Dementsprechend ist die Auswahl ein relationales Attributspeicherschema, wenn Sie im Voraus wissen, dass Sie in jedem Dokument eine Preisspalte haben und diese flach ist. Dies ist nicht länger etwas, das in die Arterie zieht, sondern im Prinzip mit zwei Fingern am Fuß - um Preise mit Wohnungen zu speichern. Wenn Sie jedoch im Voraus wissen, dass Sie es in jedem Dokument haben, bringen Sie es direkt in das Diagramm. effektiv gespeichert, belegen vier Bytes pro Dokument, und der Zugriff darauf erfolgt sofort. Es ist nicht erforderlich, Json, Bson zum Herunterladen oder durch eine Million Caches zu analysieren, um durch Lucene zu gelangen. Aber natürlich ändern sich die Schemata manchmal im laufenden Betrieb, und an manchen Stellen treten alle möglichen Ausnahmen auf, sodass niemand json stornierte. Wir haben auch Unterstützung für das interne Format.

    Ich habe versucht, mich selbst zu einem guten Entwickler zu machen und die gute Implementierung eines anderen zu stehlen, aber es stellte sich heraus, dass ich ein schlechter Entwickler war. Daher mussten alle anderen Implementierungen, die schlechter sind als ich schreiben kann, meine eigenen geschrieben werden.



    Es reicht nicht nur aus, Attribute zu speichern, sondern es ist auch wünschenswert, sie irgendwie zu indizieren. Soweit ich weiß, macht das niemand mehr oder weniger anständig. Ich betone hier das Stichwort "mehr oder weniger anständig".

    Es scheint, dass Lucene an einigen Stellen eine coole, absolut höllische Füllung mit der Emulation von Indizes für Spalten im Großen und Ganzen mit Elementen eines Volltextindex macht. Das ist auf der einen Seite. Es gibt jedoch keine nativen Indizes.

    Und Sphinx hat eine nicht weniger monumentale Lösung. Wir haben einen winzigen Blockindex für einzelne Aufzeichnungsblöcke. Wenn also irgendwann eine vollständige Aufzählung aller Datensätze erfolgt, müssen Sie nicht alle Datensätze sortieren, sondern zuerst die oberste Ebene überspringen und eine bestimmte Anzahl von Blöcken auf einmal verwerfen.

    Soweit ich weiß, gibt es in Suchmaschinen jedoch noch kein Motiv mit Attributspeicher. Das heißt Wenn Sie ein Schema haben, können Sie kreativ sein - um nicht nur eine dumme zeilenweise Matrix zu speichern, sondern auch alle Arten von zeilenweisen Komprimierungen, Aufreihungen und komprimierten Ansichten, um dies zumindest für einzelne Spalten zu tun. Wenn Sie noch nicht einmal eine Schaltung haben, ist auch alles interessant - Sie können dieses schemenlose Dokument in eine Wolke von Schlüsselwert-Tags reduzieren und dann linear nach dieser Wolke suchen.

    Sie können dies nicht tun, aber Gott sei Dank speichert niemand den Text. Sie können, entschuldigen Sie, nicht nur eine Wolke von Schlüsselwert-Tags erstellen, sondern zumindest einen Hash für den schnellen Zugriff hinzufügen. Und Sie können es nicht abflachen, Sie können eine ehrliche Hierarchie beibehalten, Sie können eine Schlüsselkomprimierung durchführen - eine Million verschiedener Tricks, aber bis jetzt sind die Suchanfragen nach zumindest Open Source nicht wirklich gewachsen. Wir arbeiten an etwas, haben es aber noch nicht fertiggestellt. Ich denke, es ist etwas zu früh, um damit anzugeben.

    Plötzlich über das Ranking.



    Beim Ranking gehe ich derzeit davon aus, dass es im Großen und Ganzen zwei Situationen gibt - entweder gibt es sie überhaupt nicht oder Sie brauchen sie idealerweise sehr, aber Sie kommen leicht davon. Das heißt Wenn Sie im Allgemeinen keine Aufgabe haben, eine Rangfolge festzulegen, ist alles in Ordnung. Boolescher Abgleich. Es ist keine umfangreiche Dokumentverarbeitung erforderlich.

    Wenn Sie im Prinzip eine Suchqualität haben, die etwas bedeutet, wenn Sie möchten, dass das Ranking interessanter ist, Sie aber nicht wissen wie, Sie nicht wissen wie oder im Prinzip "drei Ergebnisse erzielen". Dann steigen Sie mit ein paar einfachen Shnyaga wie dem eingebauten kanonischen BM25-Ranking aus, das vor 40 Jahren erfunden und überall gut beschrieben wurde. Dies ist eine natürliche einfache Formel, die nur beängstigend aussieht. Tatsächlich sind in ihr zwei Variablen im Großen und Ganzen durch alle übereinstimmenden Wörter integriert. TF (Termhäufigkeit) ist die Häufigkeit des Wortes, das in das Dokument gelangt ist, und IDF (inverse Dokumenthäufigkeit) ist die inverse Häufigkeit der Sammlung. Dies ist eine logarithmische Metrik, die grob gesagt für Dokumente, die sich überall befinden, 0 (Null) ist. Das heißt ein Dokument, das überall ist - in jedem Dokument der gesamten Sammlung, es bedeutet nichts in Bezug auf das Ranking. Die Tatsache, dass wir ihn gefunden haben, hat nichts zu bedeuten. Und umgekehrt, das Dokument, das sich in einem Dokument aus der Sammlung befindet, hat hier die maximale IDF-1 (Einheit). Und die Funktion dort ist nicht linear, es gibt einen bestimmten Logarithmus, so dass das Leben nicht wie Honig zu sein scheint. TF ist linear, also ist TF glatt. Anstelle von F, Q, I, D muss hier grob gesagt TF geschrieben werden. Da es jedoch bereits das vierte Jahr ist, in dem Photoshop die gestohlene Formel aus Wikipedia nicht mehr in Händen hält, sieht es beängstigender aus, als es könnte. D ist es eigentlich notwendig, TF zu schreiben, grob gesagt. Da es jedoch bereits das vierte Jahr ist, in dem Photoshop die gestohlene Formel aus Wikipedia nicht mehr in Händen hält, sieht es beängstigender aus, als es könnte. D ist es eigentlich notwendig, TF zu schreiben, grob gesagt. Da es jedoch bereits das vierte Jahr ist, in dem Photoshop die gestohlene Formel aus Wikipedia nicht mehr abfärbt, sieht es beängstigender aus, als es könnte.

    Es gibt einen dritten Faktor in dieser Formel, dieser Faktor ist nicht mehr in Textform - es ist die durchschnittliche Länge des Dokuments. Dort avgdl in der Formel und avg_doc_length auf der Folie. Diese einfache Rechnung, die etwas mit der Länge des Dokuments zu tun hat, bezieht sich auf die Länge des Dokuments. Je näher das Dokument an der durchschnittlichen Länge liegt, desto besser für diese Formel. Es ist gut untersucht worden, wird seit 100 Jahren von jedem benutzt und liefert rein statistisch gesehen ziemlich gute Ergebnisse, ohne die Position zu berücksichtigen.

    Die Position wird nicht berücksichtigt, und eine Art Repack, bei der alle Keywords millionenfach wiederholt werden und die Datenbank kraftvoll durch das genaue Zusammentreffen des Ausdrucks "Ich fühle dich" gespammt wird, bringt den gleichnamigen Song von Depeche Mode auf eine Position von ungefähr 112. 12 -14 Jahre zuvor hat unser Standard-Ranger in BM25 die Komponente auf der Grundlage der Annäherungspositionen, des Übereinstimmungsgrads der Abfragephrase und des Dokuments gemischt. Auch er ist eine ziemlich leichte Sache in den Berechnungen, aber er sieht zumindest irgendwie in Position.

    Wenn Sie ein starkes, qualitativ hochwertiges Ranking benötigen, macht in der Tat alles Spaß, denn es gibt wahrscheinlich viele Faktoren, um alles gut zu machen. Niemals zwei. Die Sache ist nicht auf BM25 beschränkt, genauer gesagt, BM25 geht nirgendwo hin, sondern Sie müssen anstelle des nativen BM25 alle möglichen Modifikationen verwenden, viele dieser BM25 zusammenstellen, zusätzliche interessante Faktoren betrachten, die aus dem Text berechnet wurden, und was noch interessanter ist, viele Faktoren betrachten Nicht-Text, der an ein bestimmtes Dokument gebunden ist. Tatsächlich ist dies der Hauptgrund für Kopfschmerzen und maschinelles Lernen bei großen Suchmaschinen. Die Variablen, die bei diesen Berechnungen berücksichtigt werden, sind natürlich Hunderte und Tausende, d.h. 800 Faktoren für jedes Dokument, die in der Rangfolge berücksichtigt werden - einfach, es passiert. So ist das Ranking kurz gegliedert. Es ist klar,



    Dann der nächste plötzliche Zug. Wir haben über ein bestimmtes Grundformat gesprochen, das in Ordnung ist, es gibt ein Wort, es gibt eine Liste von Dokumenten usw., und Suchanfragen geben manchmal an, dass sie in Echtzeit ablaufen. Wie ist es im Inneren angeordnet? Es sollte ein Bild geben (aber es ist nicht so), das jeder kennt, wie dieser Typ "es gibt keinen Löffel" und er ist wie "kein verdammter Philosoph". Tatsächlich gibt es auch keine Echtzeit im vollen Sinne des Begriffs Echtzeit. Das heißt volles Verständnis - es wäre, als ob die natürliche Indexstruktur ehrlich in Echtzeit aktualisiert würde.

    In der Natur gibt es keine wirkliche Echtzeit, da die Liste der Dokumente, die mit jedem Wort verknüpft sind, potenziell umfangreich und komprimiert ist. Die Aktualisierung ist eine unmenschliche Hämorrhoide. Bestenfalls können Sie am Ende etwas hinzufügen - ja, das ist einfach, aber es ist praktisch unmöglich, ein Dokument in die Mitte zu stecken. Daher hat die Menschheit viele seltsame Konzepte verfolgt, damit der Volltextindex so tut, als ob er in Echtzeit abläuft. Als Ergebnis hat man gewonnen - die gesamte Echtzeit wird auf einfache Weise emuliert: Wenn neue Dokumente eintreffen oder neue Versionen alter Dokumente, dann erstellen wir einen neuen kleinen Nanoindex mit diesen neuesten Dokumenten oder neuen Versionen. Wenn es sich um Wiederholungen handelt, nämlich um neue Versionen, dann setzen wir in den alten vorhandenen Indizes (egal ob Nano oder Mega) ein paar Flaggen, Was sagen Sie, wenn Sie dieses Dokument finden, dann finden Sie es nicht, es ist in der Tat nicht mehr. Und wir bauen ständig Kaskaden solcher Indizes. Um zu verhindern, dass sie drei Millionen werden, halten wir sie und wischen genau zum Zeitpunkt der Zusammenführung der Nanoindizes physisch die Datensätze ab, die zuvor von Flags aus diesem Index unterdrückt wurden. Hier ist die kanonische Technologie.

    Das Wort, das in Lucene erfunden wurde und das die ganze Welt jetzt kennt, wird "Segment" genannt. Wir haben also nicht begonnen, unsere eigene Terminologie zu erfinden, wir haben die gleichen Segmente, konzeptionell das gleiche. Das heißt Es gibt wirklich keine Echtzeit. Wenn Sie neue Daten in ein Echtzeitsystem einfügen, erstellt es schnell einen zusätzlichen winzigen Index, den so genannten Index Ein Segment, alte Versionen, das möglicherweise mit einer Kill-Liste, Masken oder etwas anderem unterdrückt wird, spielt keine Rolle. Später, wenn zwei Segmente in Ekstase zusammengeführt werden, werden diese Daten physisch gelöscht. Alle Echtzeit ist immer so angeordnet. Eine neue coole Methode wurde derzeit noch nicht erfunden. Zum Beispiel, komprimierte Daten, legen Sie ein weiteres Zip-Archiv in das Zip-Archiv ...



    Mehr über unterschiedliche Physik, über unterschiedliche physikalische Unterschiede, denn sie stellen regelmäßig die Frage: „Warum nicht Lucene?“. Ich freue mich besonders, wenn Sie einen Artikel über den Hub schreiben wie "Hier machen wir eine Reihe von Verbesserungen" und den ersten Kommentar im Stil von "Niemand braucht sie, töten Sie sich selbst gegen die Wand". Nein, wir werden natürlich früher oder später töten, die Leute sind alle sterblich, aber verdammt noch mal, niemand kümmert sich darum, dreimal schneller zu indexieren, und einige andere nette kleine Dinge machen Spaß. Manchmal nicht jeden Tag, aber sie stellen eine Frage. Die Antwort ist so zwiespältig. Konzeptionell ist im Inneren alles gleich. Diese Struktur mit einem Wörterbuch, mit Listen, Segmenten, um Echtzeit und andere Freuden des Lebens zu gewährleisten - sie ist konzeptionell überall gleich. Wir haben alle möglichen Ansätze ausprobiert, dieser funktioniert am besten. Es wird überall implementiert.

    Es gibt jedoch einen subtilen Punkt namens „Implementierungsdetails, verschiedene Formate usw.“. Leider ändern dieselben "Implementierungsdetails, unterschiedlichen Formate usw." alles an Orten, an Orten in Größenordnungen. Nebenbei kam ich auf die Idee und schrieb drei Unterschiede auf die Folie. Wir haben ein gemeinsames Wörterbuch aller Wörter für alle Felder aller Dokumente, die Lucene hat, bzw. für jedes einzelne Wort ein eigenes Wörterbuch.

    Ich möchte noch eines Tages einen interessanten Benchmark namens "Lasst uns eine Million Json-Dokumente einwerfen" arrangieren, und zwar in jedem Bereich mit einem eindeutigen Namen. Das ist nicht schwer, ich bin gespannt, wie es sich danach verhält, wenn die gesamte Sammlung auf einmal durchsucht wird. Oder ich lese Java-Code nicht richtig, was im Prinzip wahrscheinlich ist, aber nicht, weil Java eine komplexe Sprache ist, sondern weil Java Sie dazu anregt, 20 verschiedene Fabriken, Dekorateure und anderen Quatsch zu erstellen, um vier Codezeilen damit zu verbinden in der eigentlichen Arbeit beschäftigt. Es steht im Weg. Wenn ich mich also durch einen Dekorateur irrtümlich durchgeschlagen habe, ist vielleicht alles nicht so schlimm, aber es sieht so aus - wenn Sie viele Felder machen, wird sich das arme Ding für immer biegen.

    In unserem Land wird es sich im Gegenteil nicht für immer verbiegen, aber wenn Sie ein niederfrequentes und hochselektives Feld suchen, d. H. Sie haben eine riesige Sammlung von Dokumenten, Meter für Meter, und einen winzigen Titel, und Sie suchen nach diesem Titel, es gibt zwei Wörter von einer Million. Es ist effektiv, für diese beiden Wörter aus einer Million einen separaten Index für dieses separate Feld zu haben, aber wir haben ihn nicht implementiert. Wir haben das Beste, was implementiert wird, ist eine Maske in der Dock-Liste, aber das ist nicht gut genug. Dementsprechend werden wir in diesem Fall den gesamten Index und nicht ein einzelnes konkretes Feld auspeitschen, was wiederum ineffizient ist.

    Unterschiedliche Verwendungen, unterschiedliche Dinge brechen an unterschiedlichen Orten.

    Wir haben eine Tabelle mit Speicherattributen, über alle möglichen Feinheiten der Implementierung, über die Sie lange sprechen können, und die Möglichkeit, nur JSON-Dokumente als separate Attribute in diese Attributtabelle zu verschieben. Lucene hat keine solche Beziehung, sie hat Dokumente auf der Festplatte. Als wir das letzte Mal ein Benchmarking durchgeführt haben, hatten sie überraschend langsamen Kaltzugriff auf ein separates Feld eines separaten Dokuments. Dies ist jedoch nie sichtbar, da die Richtlinie lautet: "Sie müssen 64 GB Arbeitsspeicher auf den Server übertragen und 62 davon in den Cache geben."

    Die physische Ebene ist anders, die auffälligsten Unterschiede, die ich kenne, sind so. Sicher gibt es noch mehr.



    Um das Thema "Was ist Sphinx nicht Lucene und wie statten wir Russland aus?" Zu öffnen und schnell zu schließen, habe ich neben der Physik einen so allgemeinen Eindruck vom Code, dass es konzeptionell unterschiedliche Ansätze für das Projektil gibt. Wo wir es vorziehen, etwas nicht zu tun, als es schlecht zu machen, und wenn wir es tun, dann hat Lucene das Gegenteil: "Lassen Sie uns in der Lage sein, alles schnell und schnell zu zählen, und der Benutzer wird auf seiner eigenen Ebene, auf welcher Ebene, cachen." "Lassen Sie uns viel Speicher verbrauchen, es zumindest irgendwie zählen und dann auf beiden Ebenen (sowohl in der Bibliothek selbst als auch auf allen Servern) eine Million Caches auf verschiedenen Ebenen innerhalb des Servers oder der Bibliothek. Es ist unmöglich, es an einigen Stellen überhaupt zu deaktivieren."

    In der Tat sind beide Ansätze schlecht. In Sphinx werden Sie eine Art Cache aktivieren, den Sie auf Serverebene aktivieren möchten. In Lucene ist es jedoch schlecht, einen verständlichen Benchmark zu erstellen. Du hast es geschafft, er wiederholte sie tausendmal auf zehn Anfragen, na ja, großartig - du hast gerade die Geschwindigkeit gemessen, mit der der Cache zurückkehrt. Da Sie die Meerrettich-Caches ausschalten, ist es außerdem so, als würden Sie das Wetter auf dem Mars auch dann messen, wenn Sie bis zu zehn von zehn Anfragen stellen.

    Und dann plötzlich die Geschichte von Xapian. Erhöht das Konzept zum Absoluten. Es ist ein seltsames esoterisches System, das schon lange gestorben ist. Wahrscheinlich wird es von nur einer Person auf der Welt in der Produktion verwendet, die es geschrieben hat, genannt Xapian. Ich habe einmal versucht, es zu vergleichen. Ich habe eine Art Testsuche gestartet, sie hat mir das Ergebnis für 0,000 zurückgegeben. "Keine verdammte Sache", dachten die russischen Männer. Ich habe noch ein paar Anfragen entlassen, sie hat noch ein paar Antworten gegeben und auch auf 0,000. Ich war völlig überrascht und begann bereits, die Wand zu polieren, um an dieser Stelle Selbstmord zu begehen, und dann wurde das Porträt dort eingraviert, aber ich schätzte immer noch, einen zweiten Test durchzuführen und etwas einzuschalten, entweder nach Attributen zu sortieren oder nach Phrasen zu suchen und so weiter. .d. Plötzlich wurde das Geheimnis offenbar - ein dummes Schaf nahm bei der Suche nach einzelnen Stichwörtern 10 Dokumente heraus, Im Voraus, nach einer magischen Formel, die von niemandem benötigt wurde, fügte man nach jedem Wort sortiert diese Listen zusammen, berücksichtigte die BM25-Annäherung und gab dem Set sehr schnell ein völlig unnötiges Ergebnis. Es wurde nicht einmal die genaue Anzahl der Übereinstimmungen ermittelt, da die vollständigen Dokumentenlisten nicht sortiert wurden, die vollständige Übereinstimmungsergebnismenge nicht berücksichtigt wurde, sondern die Annäherung berücksichtigt wurde. Typ: „Hier haben wir eine Million Dokumente, dieses Wort kommt in 1% und dieses Wort in 3% vor. Wir nähern uns, und so geht es. Sie sind Trottel, hahaha. " Sobald Sie etwas Interessanteres als diese Schlüsselwortsuche aktivieren und selten, wenn Sie es benötigen und selten, wenn es gute Ergebnisse liefert, sinkt die Leistung sofort um das 30-fache unter die von Sphinx. Und damit habe ich auch den Benchmark und meine Systemkenntnisse beendet. Fassen Sie diese Listen zusammen, berücksichtigen Sie die BM25-Näherung und geben Sie sehr schnell völlig unnötige Ergebnisse an das Set zurück. Es wurde nicht einmal die genaue Anzahl der Übereinstimmungen ermittelt, da die vollständigen Dokumentenlisten nicht sortiert wurden, die vollständige Übereinstimmungsergebnismenge nicht berücksichtigt wurde, sondern die Annäherung berücksichtigt wurde. Typ: „Hier haben wir eine Million Dokumente, dieses Wort kommt in 1% und dieses Wort in 3% vor. Wir nähern uns, und so geht es. Sie sind Trottel, hahaha. " Sobald Sie etwas Interessanteres als diese Schlüsselwortsuche aktivieren und selten, wenn Sie es benötigen und selten, wenn es gute Ergebnisse liefert, sinkt die Leistung sofort um das 30-fache unter die von Sphinx. Und damit habe ich auch den Benchmark und meine Systemkenntnisse beendet. Fassen Sie diese Listen zusammen, berücksichtigen Sie die BM25-Näherung und geben Sie sehr schnell völlig unnötige Ergebnisse an das Set zurück. Es wurde nicht einmal die genaue Anzahl der Übereinstimmungen ermittelt, da die vollständigen Dokumentenlisten nicht sortiert wurden, die vollständige Übereinstimmungsergebnismenge nicht berücksichtigt wurde, sondern die Annäherung berücksichtigt wurde. Typ: „Hier haben wir eine Million Dokumente, dieses Wort kommt in 1% und dieses Wort in 3% vor. Wir nähern uns, und so geht es. Sie sind Trottel, hahaha. " Sobald Sie etwas Interessanteres als diese Schlüsselwortsuche aktivieren und selten, wenn Sie es benötigen und selten, wenn es gute Ergebnisse liefert, sinkt die Leistung sofort um das 30-fache unter die von Sphinx. Und damit habe ich auch den Benchmark und meine Systemkenntnisse beendet. Da die vollständigen Dokumentenlisten nicht sortiert wurden, wurde die vollständige Übereinstimmungsergebnismenge nicht berücksichtigt, aber die Annäherung wurde berücksichtigt. Typ: „Hier haben wir eine Million Dokumente, dieses Wort kommt in 1% und dieses Wort in 3% vor. Wir nähern uns, und so geht es. Sie sind Trottel, hahaha. " Sobald Sie etwas Interessanteres als diese Schlüsselwortsuche aktivieren und selten, wenn Sie es benötigen und selten, wenn es gute Ergebnisse liefert, sinkt die Leistung sofort um das 30-fache unter die von Sphinx. Und damit habe ich auch den Benchmark und meine Systemkenntnisse beendet. Da die vollständigen Dokumentenlisten nicht sortiert wurden, wurde die vollständige Übereinstimmungsergebnismenge nicht berücksichtigt, aber die Annäherung wurde berücksichtigt. Typ: „Hier haben wir eine Million Dokumente, dieses Wort kommt in 1% und dieses Wort in 3% vor. Wir nähern uns, und so geht es. Sie sind Trottel, hahaha. " Sobald Sie etwas Interessanteres als diese Schlüsselwortsuche aktivieren und selten, wenn Sie es benötigen und selten, wenn es gute Ergebnisse liefert, sinkt die Leistung sofort um das 30-fache unter die von Sphinx. Und damit habe ich auch den Benchmark und meine Systemkenntnisse beendet. Wenn es gute Ergebnisse liefert, sinkt die Leistung sofort um das 30-fache unter die von Sphinx. Und damit habe ich auch den Benchmark und meine Systemkenntnisse beendet. Wenn es gute Ergebnisse liefert, sinkt die Leistung sofort um das 30-fache gegenüber Sphinx. Und damit habe ich auch den Benchmark und meine Systemkenntnisse beendet.



    Unterschätzen Sie nicht die Macht nur dummer Käfer. Das heißt Es gibt Unterschiede in der Herangehensweise, es gibt immer noch Probleme bei den Benchmarks, aber ich möchte auch darauf hinweisen, dass es in einigen Fällen immer unvermeidlich ist, dass sie in Implementierungen, in einem bestimmten System, nur dumme Esel sind. Hier unvermeidlich und hier nichts.

    Ich erinnerte mich an die Geschichte über die Präfixe, weil sie cool und aufschlussreich ist. Nachdem Lucene ein Benchmarking für eine Präfix-Suche durchgeführt hat, spielt es keine Rolle, für welche, ob es sich um eine direkte Präfix- oder eine Teilstringsuche handelt, und fragte sich: "Warum so langsam?" Dort war es üblich, dass Dekorateure insgesamt 15 und nicht 25 schrieben, so dass das Problem besonders schnell auf den Grund ging. Es stellte sich heraus, dass in der Präfixsuche die Implementierung für die Bewertung "ausgezeichnet" in Lucene. Sie hat nur dumm das ganze Wörterbuch linear durchsucht, im Allgemeinen das ganze. Vielen Dank, dass Sie keine Regex-Engine sind. Nun, eine lineare Wörterbuchsuche mit 10 Millionen Stichwörtern war ebenfalls eine sehr gute Idee. Ich war sozusagen froh, und danach gab es eine Episode, in der die Realität zeigte, dass man nicht glücklich sein sollte, wenn Sphinx im selben Fall auch nach Teilstrings suchte, aber in einer etwas anderen Situation. Es gibt einen bestimmten Index im Wörterbuch, damit wir bei der Suche nach Teilzeichenfolgen nicht 10 Millionen des Wörterbuchs aussortieren müssen. Im Allgemeinen ist alles linear. Wir hatten es sofort, aber die Situation hieß "Wenn ein Bastard eine Anfrage wie" a * "scheißt." nicht, dass man sie sich nicht vorgestellt hätte, aber bei unseren Tests verhielt sie sich mehr oder weniger angemessen. Und dann stürzt der Server plötzlich in Produktionsclients ab und stürzt nicht nur ab, sondern die Schaltfläche ist erforderlich. Und nicht die Taste, die Strg, Alt, Entf, sondern die Taste, die "aus der Steckdose ziehen". Eine Autopsie ergab, dass der Kunde sich in den Einstellungen ein wenig geirrt hat, wir uns in den Standardeinstellungen ein wenig geirrt haben usw. und die Anfrage "Zhuravlev" mit einem Sternchen (*) am Ende ersetzte den Buchstaben "ё" durch ein Leerzeichen, weil charset_table. Danach gab es eine Anfrage "in" mit einem Stern am Ende. Und alles wäre in Ordnung, wenn die Grenze der Erweiterungen vernünftig wäre und nicht 175.000 Wörter. Ich erinnere mich nicht Es spielt keine Rolle, ob es sich in der Konfiguration um einen Konfigurationsfehler oder einen Fehler unserer Standardeinstellungen handelt. Wenn jedoch für diese 175.000 Wörter (von denen 174500 Wörter in einem Dokument einmal vorkamen) Puffer mit einer Größe gelesen werden, ist dies in jedem Fall nicht der Fall 4 MB pro Wort wäre der Server auch etwas einfacher. Aber sie haben nicht herausgefunden, warum er gefallen ist, haben sich an den Rüben gekratzt und sie repariert, das bedeutet, dass es allen gut geht. Und Lucene korrigierte, und es wurde ihnen klar, dass erschöpfende Suche nicht cool ist, und es wurde uns klar, dass das Wort, mit dem drei Datenbytes gelesen werden sollen, nicht durch einen 4-MB-Puffer gelesen werden muss. Wir geben jetzt nur 8 Kb dafür aus. Tatsächlich lesen wir es im Allgemeinen nicht durch den Puffer, aber dies ist eine separate, komplizierte Geschichte. Wörter (von denen 174500 Wörter einmal in einem Dokument gefunden wurden) würden keinen Lesepuffer von 4 MB pro Wort erzeugen, dann wäre der Server auch etwas einfacher. Aber sie haben nicht herausgefunden, warum er gefallen ist, haben sich an den Rüben gekratzt und sie repariert, das bedeutet, dass es allen gut geht. Und Lucene korrigierte, und es wurde ihnen klar, dass erschöpfende Suche nicht cool ist, und es wurde uns klar, dass das Wort, mit dem drei Datenbytes gelesen werden sollen, nicht durch einen 4-MB-Puffer gelesen werden muss. Wir geben jetzt nur 8 Kb dafür aus. Tatsächlich lesen wir es im Allgemeinen nicht durch den Puffer, aber dies ist eine separate, komplizierte Geschichte. Wörter (von denen 174500 Wörter einmal in einem Dokument gefunden wurden) würden keinen Lesepuffer von 4 MB pro Wort erzeugen, dann wäre der Server auch etwas einfacher. Aber sie haben nicht herausgefunden, warum er gefallen ist, haben sich an den Rüben gekratzt und sie repariert, das bedeutet, dass es allen gut geht. Und Lucene korrigierte, und es wurde ihnen klar, dass erschöpfende Suche nicht cool ist, und es wurde uns klar, dass das Wort, mit dem drei Datenbytes gelesen werden sollen, nicht durch einen 4-MB-Puffer gelesen werden muss. Wir geben jetzt nur 8 Kb dafür aus. Tatsächlich lesen wir es im Allgemeinen nicht durch den Puffer, aber dies ist eine separate, komplizierte Geschichte. Nun, dann geht es allen gut. Und Lucene korrigierte, und es wurde ihnen klar, dass erschöpfende Suche nicht cool ist, und es wurde uns klar, dass das Wort, mit dem drei Datenbytes gelesen werden sollen, nicht durch einen 4-MB-Puffer gelesen werden muss. Wir geben jetzt nur 8 Kb dafür aus. Tatsächlich lesen wir es im Allgemeinen nicht durch den Puffer, aber dies ist eine separate, komplizierte Geschichte. Nun, dann geht es allen gut. Und Lucene korrigierte, und es wurde ihnen klar, dass erschöpfende Suche nicht cool ist, und es wurde uns klar, dass das Wort, mit dem drei Datenbytes gelesen werden sollen, nicht durch einen 4-MB-Puffer gelesen werden muss. Wir geben jetzt nur 8 Kb dafür aus. Tatsächlich lesen wir es im Allgemeinen nicht durch den Puffer, aber dies ist eine separate, komplizierte Geschichte.



    Plötzlich über Benchmarks. Jeder weiß, dass Sie richtig, falsch und im Allgemeinen benchmarken können. Jeder weiß, dass es notwendig ist, ungefähr dasselbe zu vergleichen, auf die Zeit zu schauen, und dann beginnen die Gedanken, dass manchmal Caches existieren, sie etwas anklopfen usw. Und im Idealfall müssen Sie sich die durchschnittliche Zeit ansehen, im Idealfall das Histogramm, die Anzahl der Quantile, die Mediane ... Leider ist dies speziell bei Suchmaschinen und nicht beim Datenbankauswahl-Benchmark der Ansatz:



    Dieselbe Abfrage, Karl, dieselbe! Leider ist es bei der Suche aufgrund des Mangels an einer bestimmten Standardisierung, ob das oder etwas anderes das eigentliche Konzept derselben Anfrage ist, diese gleiche Anfrage ist nicht dasselbe. Es kann im Inneren sehr unterschiedlich betrachtet werden.



    Hier ist ein lebendiges Beispiel dafür, wie der Volltextteil betrachtet wird.

    Shpinx. Standard - Wir möchten alle Wörter finden, und dies wird relativ schnell berechnet, da Sie das seltenste Wort nehmen, dann alle nach dem seltensten Wort gefundenen Wörter weiter reduzieren, diesen Fall nach einem häufigeren, einem häufigeren usw. filtern. Es ist klar, dass das Wort, das in drei Dokumenten vorkommt und dann gefiltert wird, am Ausgang zwei Dokumente ergibt und abfeuert. Das Halten von drei Dokumenten + 1 Million Dokumenten + 1 Million Dokumenten im zweiten Wort + weiteren 2 Millionen im dritten Wort ist relativ langsam. Gleichzeitig haben wir aber ein relativ hohes Ranking. Standardmäßig berücksichtigt das Ranking, bei dem nicht nur die Häufigkeit der dort gefundenen Keywords, sondern auch zumindest ein wenig die Häufigkeit der Anfrage und des Dokuments berücksichtigt wird, einen nicht sehr schwierigen Faktor, der als Nähe bezeichnet wird

    Lucene verwendet eine bedingt langsame Implementierung, wobei die Wörter einer Art von ODER-Verknüpfung entsprechen, d. H. Das grundlegende boolesche Matching ist theoretisch langsamer, aber das Ranking ist viel weniger schwer. Und plötzlich diese Geschichte über Xapian - wir lächeln und winken. Wir gaben für jedes Keyword eine vorab zwischengespeicherte, grobe Ergebnismenge an, was im Kampf keine verdammte Sache bedeutet.

    Hier sind drei "identische" Abfragen. Und aus Sicht des Anwenders sind sie genau gleich. Wir haben einfach das System genommen und, ohne das Bewusstsein wiederzugewinnen, in jede Anfrage den Text "Mutter, Seife, Rahmen" hineingemischt.



    Und das ist immer noch ein bisschen wie eine Blume, weil der Moment mit internen Caches ist, wie es auf der Folie geschrieben steht. Caches sind überall, nur die Hölle. Einmal haben wir uns auf das Benchmarking bestimmter Dinge konzentriert, einfach weil wir nicht alle Caches deaktivieren konnten. Das heißt Sie können eine bestimmte externe Benchmark-Schnittstelle in Lucene verwenden und sie einfach mit Anfragen bombardieren, in der Hoffnung, dass diese Caches leer werden. Fügen Sie ein Virtualochka mit 1 GB Arbeitsspeicher und einem Index von 10 GB ein und löschen Sie es mit Abfragen. In keiner anderen Weise ist es möglich, die Leistung von echtem Code zu messen, der interessant zu messen war, und nicht die Leistung des Caches.



    Und mein Lieblingsbeispiel für Marketing Driven Default 3 sind Snippets, so ein separat stehender Moment, der nicht immer und nicht für alle wichtig, aber sehr bedeutsam ist. Wiederholt, nicht jeden Tag, wahrscheinlich auch nicht jede Woche, aber dennoch wiederholt, stellten sie die Frage: „Warum haben Sie solche Bremsstücke gerade? In Solr wirkt ein Nyashka im Allgemeinen wie ein verbrühtes Kaninchen mit Amphetaminen, aber ist es langsamer? “ Eine Autopsie ergab, dass es drei Hauptpunkte gibt:

    • Erstens haben wir Syntax-Hervorhebung, aber in Solr gibt es standardmäßig keine Syntax-Hervorhebung. Wenn Sie sie aktivieren, wird sie mit Gottes Hilfe zehnmal langsamer. Das heißt Jede Anfrage, die wir haben, wird ehrlich in den Syntaxbaum geparst und funktioniert schnell, einschließlich dummer Abfragen, bei denen es keinen Syntaxbaum gibt, sondern nur eine Reihe von Schlüsselwörtern in großen Mengen. Und Sie müssen alles markieren.
    • Der zweite Punkt ist, dass sie einen Index im Voraus erstellt haben, eine Art Hilfsstruktur, obwohl es seltsamerweise genug ist, um Schnipsel hervorzuheben, wird uns nicht zehnmal geholfen.
    • Und ich habe einen Balsam im Herzen - das nennt man "Optimierung um 64 Kb". Was meinst du, hier geht es wieder um den Puffer, den wir dort hatten und 4 MB die Worte lesen? Nein, alles ist viel einfacher, Solr hat eine sehr gute Hintergrundbeleuchtung für große Dokumente, weil er von ihnen die ersten 64 KB hervorhebt und „komm schon“. Und Sphinx hebt ehrlich den gesamten Text hervor und versucht, standardmäßig im gesamten Text des Dokuments zu suchen. Trotzdem haben wir meiner Meinung nach einen Splitter gemacht, um auch zu lesen und hervorzuheben.

    Dies waren alles Wehklagen zum Thema "Richtiges Benchmarking und was ist das gleiche Anliegen." Es gibt keine identische Anfrage. Das richtige Benchmarking ist selbst einem Volltext-Systementwickler nicht klar. Und Ärger. Um ein klares Benchmarking zu erzielen, müssen Sie daher leider zumindest grob verstehen, wie alles im Inneren angeordnet ist, sonst ist Ihr Benchmark auf der einen Seite bestenfalls etwas falsch, im schlimmsten Fall zeigt er plötzlich eine exakt 100-mal schlechtere Leistung als in der Produktion waren auf den tests dagegen. So wie der Cache endet, wird die Trefferquote von 99% 1% betragen und alles wird falsch sein.

    Die Ergebnisse.

    Hier ist die Suche so angeordnet. Ich habe versucht zu sagen, wie es im Prinzip auf einer physischen Ebene angeordnet ist - Wörterbücher, Dokumentblätter, plötzlich Komprimierung, es ist plötzlich wichtig.

    Es gibt genau zwei Open-Source-Systeme und eine Vielzahl von kommerziellen Systemen. In der Tat, dass diejenigen, die andere begrifflich genau gleich angeordnet sind, gibt es auch keinen Durchbruch bei kommerziellen. Im Inneren befinden sich dieselben Wörterbücher, Listen, Listen, Wörterbücher usw. Alles ist genau gleich, die Implementierungsdetails ändern sich jedoch. Ich habe auch versucht, einige Implementierungsdetails hervorzuheben, sie sagen, hier macht Lucene es, wir machen es ein wenig anders und werden Orte wiederholen, usw. Und aus diesen Implementierungsdetails und den allgemeinen Ansätzen für das Projektil, die als "Wir wollen ehrlich zählen und sie wollen tapfer zwischenspeichern" bezeichnet werden, ergeben sich so seltsame Probleme, die heute für eine Suche mit dem Titel "fuck you will cache me, I have a cache inside" spezifisch sind einen solchen Cache, dass Sie immer nur diesen Cache benchmarken. " Unglaublich beleidigend, aber die Tatsache, die uns in den Empfindungen gegeben wurde,

    Kontaktdaten


    » Shodan@sphinxsearch.com
    » Shodan

    Dieser Bericht ist eine Abschrift einer der besten Reden auf der Entwicklerkonferenz für hoch belastete Systeme HighLoad ++ . Jetzt bereiten wir die Konferenz 2016 aktiv vor - dieses Jahr wird HighLoad ++ am 7. und 8. November in Skolkovo stattfinden.

    Einige dieser Materialien werden von uns auch in einer Online-Schulung zur Entwicklung von hochbelasteten Systemen HighLoad verwendet. Guide ist eine Kette speziell ausgewählter Briefe, Artikel, Materialien, Videos. Bereits in unserem Lehrbuch mehr als 30 einzigartige Materialien. Vernetzen Sie sich!

    Jetzt auch beliebt: