Wie die Struktur eines index für type ahead für sehr große datasets mit Lucene oder ähnlichen?
Ich habe einen Datensatz von 200million+ Aufzeichnungen und bin auf der Suche um zu bauen ein dediziertes backend macht ein type-ahead-Lösung. Lucene ist von Interesse aufgrund seiner Beliebtheit und Lizenz-Typ, aber ich bin offen für andere open-source-Vorschläge als gut. Ich bin auf der Suche nach Rat, Geschichten aus den Schützengräben, oder noch besser direkte Anweisungen, was ich benötige soweit Menge an hardware und die Struktur der software. Anforderungen:
Müssen:
- Die Fähigkeit zu tun, beginnt mit substring-matching (I-Typ in der 'st' und es sollte mit 'Stephen')
- Die Möglichkeit, die Ergebnisse sehr schnell, ich würde sagen, 500ms ist eine Obere Schranke.
Schön zu haben:
- Die Fähigkeit zu ernähren Relevanz von Informationen in der Indizierung, so dass, zum Beispiel, beliebter Begriffe würde zurückgegeben werden, vor den anderen und nicht nur alphabetisch, aka Google Stil.
- In-Wort-substring-matching, also beispielsweise ('st' würde passen 'bestseller')
Hinweis:
- Dieser index wird rein verwendet werden, für Art Voraus, und braucht nicht zu dienen standard-Suche Abfragen.
- Ich bin nicht besorgt über immer Ratschläge, wie Sie den front-end-oder AJAX, solange der index abgefragt werden kann als service oder direkt über Java-code.
Up Stimmen für jede nützliche Informationen, die mir ermöglicht, näher an eine enterprise-Ebene mit type ahead-Lösung
Du musst angemeldet sein, um einen Kommentar abzugeben.
Wenn jeder Datensatz ist relativ klein (weniger als ein paar Worte) Sie können versuchen, eine Trie-Datenstruktur:
http://en.wikipedia.org/wiki/Trie
Wurde es für Blitz schnell prefix-matching und es ist relativ platzsparend. Ich habe diese Datenstruktur für die genaue auto-complete-Funktionalität, die Sie suchen, und ich weiß von anderen, die dies getan haben, für high-volume-Produktion-websites. Meiner Erfahrung nach können Sie erwarten, dass Reaktionszeiten von mehreren zehn Millisekunden für eine einzelne Abfrage.
Implementieren Sie einen Trie sich ziemlich leicht, oder gibt es Implementierungen, die Sie herunterladen können. Sehen
Wo finde ich ein standard-Trie-basierten map-Implementierung in Java?
Je nachdem welche Implementierung Sie verwenden, es sollte relativ einfach zu-tag jedes indizierten Datensatz mit einem Relevanz-score, den Sie dann verwenden können, um zu Sortieren, wenn Sie bekommen eine Liste von Datensätzen aus einer Abfrage.
Können Sie nicht brauchen, nichts zu Phantasie. Ihre "must have" - Liste kann erfüllt werden, indem eine einfache Datenbank-engine (z.B. BerkeleyDB oder ESENT). Setzen Sie alle Wörter in eine Tabelle und verwenden Sie dann versucht, sich die Worte.
Eines b-Baum 8 Kb-Seiten sollten mindestens 250 Saiten/Seite, die in 1M Blatt Seiten, was ein b-Baum der Höhe 3. Auch mit 5400 RPM laptop-Festplatte, I/O-Latenz weniger als 15ms so, im schlimmsten Fall, werden Sie in der Lage sein, um Ergebnisse in ~50ms im schlimmsten Fall (komplett, nicht zwischengespeicherten Daten und eine langsame Festplatte).
(Baute ich eine typeahead-Anwendung verwendet, die ESENT-basierte PersistentDictionary Klasse. Mit 200K Datensätze bekomme ich eine ~35ms Antwort für die erste lookup, wo die Daten nicht im Cache alle. Nach einer Reihe von Abfragen, die response-Zeit sinkt um ~5ms).
Unterstützen viele gleichzeitige Benutzer haben, können Sie entweder fügen Sie mehr cache oder schnellere Festplatten. Komplett Zwischenspeichern aller Daten ist wahrscheinlich möglich (8 GB RAM ist heutzutage durchaus bezahlbar) und die typeahead-Daten werden sicherlich klein genug, um passen auf eine SSD, die eine lächerliche Anzahl von IOPS. Ich könnte gehen, für die SSD, weil das geben großen Leistung, auch wenn der cache kalt ist (z.B. nach einem Neustart).
Einer Datenbank-engine basierende Lösung sollte es sein extrem schnell zu bauen.
Hier ist, wie wir es tun, in SOLR:
Die Taste, um die Suche zu haben, wenn der korrekte Datentyp mit dem entsprechenden filter Fabriken.
Setup ein Datentyp im schema genannt textPrefix
Beispiel:
Dann in deinem schema-Dokument erstellen Sie ein neues Datenfeld als solche:
Speichern Sie dann eine Kopie für den Kunden Name in diesem CustomerNamePrefix Feld.
Wenn Sie nun die Abfrage für dieses Feld können Sie einfach die ersten Buchstaben des namens ein, und es wird Ihnen die beste übereinstimmung für diese Buchstaben. Je nachdem, wie Sie Ihre Abfrage könnte man boost Ergebnissen basierend auf anderen Faktoren, in Ihnen Dokument.
Beispiel: