treee
Update with Windows10 and MacOS executables
Schnelle Indizing -Engine für Daten, die durch Hashed -ID identifiziert und in einer unveränderlichen Datei gespeichert sind
Dies ist die GO -Implementierung der Tree ™ Indexing Engine. Es ist sowohl eine Bibliothek als Modul in Ihren GO-Projekten als auch eine ausführbare Datei, um als Micro-Service über HTTP auszuführen.
Die Herausforderung bestand darin, eine leistungsstarke und sichere Suchmaschine einzurichten, die verwendet werden soll, wenn die Daten eine verknüpfte Liste der Elemente sind, die selbst in Subchains selbst miteinander verbunden sein könnten, die durch ihre Identifikatoren indiziert werden, die nur aus Hashed-Werten (wie SHA-256-String-Darstellungen) bestehen und alle in einer unenabbaren Datei gespeichert sind.
Die beste Anwendung ist für eine Blockchain -Datei, in der ein Element eine Transaktion ist, die einen intelligenten Vertrag einbettet, und jede Unterbeamte der Elemente die nachfolgenden Verwendungen und/oder Änderungen dieses intelligenten Vertrags. Daher wird der Treee ™ Index derzeit in der Rooot ™ -Blockchain verwendet.
Wir definieren hier einen Algorithmus zur Indizierung des Systems auf der Grundlage von Identifikatoren, bei denen es sich um Hash -Werte handelt, die gleichzeitig sehr leistungsfähig für das Schreiben und das Lesen sind.
Der Treee ™ -Index ist als acyclischer Graphen (ein Baum) konstruiert. Jeder Knoten enthält entweder die Knotenadresse (ihre Söhne) oder eine Reihe von Blättern , ein Blatt , das den Informationen entspricht, die dazu beitragen, ein oder mehrere verknüpfte Elemente abzurufen.
Die Anzahl der Söhne eines Knotens ist deterministisch und hängt von der Tiefe des Baumes ab. Wir bezeichnen durch die Anzahl der Söhne der Knoten in Tiefe 1, die Anzahl der Söhne der Knoten in Tiefe 2, ... die Anzahl der Söhne in der Tiefe.
Ziel ist es, einen ausgewogenen Baum zu schaffen, dessen Breite anpassungsfähig ist, um die Tiefe zu verringern und die Leistung zu optimieren. Wir möchten Zahlen indexieren, in diesem Fall der numerische Wert der eindeutigen Kennungen der Elemente.
Lassen Sie uns den Verlauf des Index erklären.
Für den binären Baum schreiben wir die Zahl in binärer Form (z. B. 100 ), die ihre Position im Baum angibt.
Bei dem Schritt gehen wir an das Kind, wenn das Bit 0 ist, andernfalls übergeben wir an das Kind, wenn das Bit 1 ist. Wir hören auf, wenn der Knoten ein Blatt ist.
Für den Baum bauen wir eine Darstellung dieser Zahl durch eine Abfolge von Zahlen auf und durchqueren den Baum auf die gleiche Weise. Nach dem Schritt der Tiefe gehen wir an das Kind, wenn der Vertreter 0 ist, wir gehen an das Kind weiter, wenn der Vertreter 1 ist, ..., wir gehen an das Kind weiter, wenn der Vertreter ist. Wir hören auf, wenn der Knoten ein Blatt ist.
Um die Darstellung einer Zahl zu konstruieren, werden wir nacheinander das Modulo der Primzahlen einnehmen. Nach dem Satz der chinesischen Überreste hat jede Zahl einen einzigartigen Vertreter, der als Fortsetzung dieser Modulos geschrieben werden könnte. In der Tat kann eine Zahl in der folgenden Form geschrieben werden:
Der Wert der Kennung des Elements (seine Zahl) wird bezeichnet und die modulierende Nummer. Modulos werden für Zahlen fester Größe berechnet. Da die Multiplikation schneller als die Abteilung ist (für die Berechnung des Modulos erforderlich), kann man Multiplikationen mittels schwimmender Sprache verwenden :.
Angesichts der zufälligen Natur der Zahlen (oder des Pseudo-Randoms, da die Kennungen der Elemente durch kryptografische Hashing-Technologien erzeugt werden), ist der Baum ausgeglichen. Um den Baum auf böswillige Weise auszuwischen, wäre es notwendig, Hashes zu erzeugen, deren Modulo einer bestimmten Flugbahn folgt. Die Schwierigkeit einer solchen Operation nimmt jedoch exponentiell zu (in der Größenordnung von der Tiefe). Zur Erinnerung ist das Produkt der ersten 16 Primzahlen gleich. Sobald der Index eine einigermaßen große Menge an Daten enthält, würde es immer unmöglicher werden, den Baum auf böswillige Weise auszuweichern.
Ein Blatt enthält die folgende Liste von Informationen zu einem Element:
Ein Blatt , dessen nächstes Elementfeld leer ist, ist das letzte Element in der Unterkette.
Ein Blatt , dessen Ursprungsartikel Feld gleich der Kennung des aktuellen Elements ist, ist notwendigerweise der Ursprung der Unterkette. Als solches wird ein bestimmtes Betrieb, da es hier als vorheriger Gegenstand als ein oder mehrere Elemente danach als ein oder mehrerer Punkte der Subchain identifiziert wird. Die letzten drei Felder des Blattes entsprechen daher einer kreisförmigen verknüpften Liste.
Um dem Index ein Element hinzuzufügen:
So lesen/durchsuchen ein Element im Index:
Bei der Verwendung des Index können wir sehen, dass wir höchstens 3 Lesevorgänge oder 3 Schreibvorgänge und Indexläufe der Reihenfolge durchführen würden, wo ist die Anzahl der Elemente im Index.
Für weitere Details lesen Sie das vollständige Weißpapier.
$ go get github.com/cyrildever/treee import (
"github.com/cyrildever/treee/core/index"
"github.com/cyrildever/treee/core/index/branch"
"github.com/cyrildever/treee/core/model"
)
// Instantiate default index (could be any prime number up to the 1000th existing prime number,
// but should be much lower to better leverage the solution, and if 0 will use the default INIT_PRIME value)
treee , err := index . New ( index . INIT_PRIME )
if err != nil {
// Handle error
}
// Add to index
leaf := branch. Leaf {
ID : model . Hash ( "1234567890abcdef" ),
Position : 0 ,
Size : 100 ,
}
err = treee . Add ( leaf )
if err != nil {
// Handle error
}
// Search
if found , err := treee . Search ( leaf . ID ); err == nil {
// Do something with found Leaf
} Für eine bessere Leistung sollten Sie Ihre Suchanfragen in verschiedenen Goroutines einstellen (siehe GetLeaf() Implementierung in API/Handlers/Leaf.go -Datei).
Für Debugging- oder Speicherzwecke möchten Sie möglicherweise die PrintAll() -Methode auf dem Treee -Index verwenden, um alle aufgezeichneten Blätter an einen Schriftsteller zu drucken ( true Sie sie als Argument für die Verschönerung des gedruckten JSON oder false für die Rohschnur).
// To print to Stdout
fmt . Println ( treee . PrintAll ( true )) Die Persistenz des Index wird durch die Verwendung des automatischen Speicherns erreicht, der beim Einfügen hergestellt wurde, und der Verwendung der Load() -Funktion anstelle von Tree-Instanziierung mit New() beim Start.
treee , err := index . Load ( "path/to/treee.json" ) // If empty, will use "./saved/treee.json"Es kann mithilfe der entsprechenden Umgebungsvariablen oder der Flagge in der Befehlszeile oder sogar programmgesteuert deaktiviert werden:
treee . UsePersistence ( false ) // If you're positive you don't want itSie können einfach die ausführbare Datei erstellen und eine Instanz der Tree ™ Indexing Engine starten.
$ git clone https://github.com/cyrildever/treee.git && cd treee && go build
$ ./treee -t.port 7001 -t.host localhost -t.init 101 Usage of ./treee:
-t.file string
File path to an existing index
-t.host string
Host address (default "0.0.0.0")
-t.init string
Initial prime number to use for the index (default "0")
-t.persist
Activate persistence (default true)
-t.port string
HTTP port number (default "7000")
Wenn festgelegt, überschreiben die folgenden Umgebungsvariablen eine entsprechende Standardkonfiguration oder das Flag, das mit der Befehlszeile übergeben wurde:
HOST : Die Host -Adresse;HTTP_PORT : Die zu verwendende HTTP -Portnummer;INDEX_PATH : Der Pfad zur Indexdatei im JSON -Format;INIT_PRIME : Die anfängliche Primzahl (Beachten Sie, dass es keinen Effekt hat, wenn eine Datei verwendet wird, da letztere vorherrschen);USE_PERSISTENCE : Setzen Sie false , um die Verwendung des Speicherns des Index in eine Datei zu deaktivieren. Die folgenden Endpunkte sind unter der /api -Gruppe verfügbar:
DELETE /leafDieser Endpunkt beseitigt die übergebenen Elemente aus dem Index.
Es erwartet eine Reihe von IDs als ids -Abfrageargument, z.
DELETE /api/leaf?ids=1235467890abcdef [ ... ] &ids=fedcba0987654321 [ ... ]
User-Agent: Mozilla/4.0 (compatible; MSIE5.01; Windows NT)
Host: treee.io
Accept-Language: fr-FR
Accept-Encoding: gzip, deflate
Accept: application/json Es gibt einen 204 -Statuscode zurück, wenn alle übergebenen Elemente entfernt wurden, oder einen 200 -Status -Code zusammen mit der folgenden JSON -Liste von ungelösten IDs, wenn einige nicht entfernt wurden:
{
"ids" : [ " fedcba0987654321[...] " ]
}GET /leafDieser Endpunkt durchsucht Elemente basierend auf den bestandenen IDs.
Es erwartet eine Reihe von IDs als ids -Abfrageargument und ein optionales takeLast Boolean (Standard zu false ), z. http://localhost:7000/api/leaf?ids=1234567890abcdef[...]&ids=fedcba0987654321[...]&takeLast=true
Es gibt einen Statuscode 200 zusammen mit einem JSON -Objekt zurück, das das folgende Format respektiert:
[
{
"id" : " 1234567890abcdef[...] " ,
"position" : 0 ,
"size" : 100 ,
"origin" : " 1234567890abcdef[...] " ,
"previous" : " 1234567890abcdef[...] " ,
"next" : " "
},
[ ... ]
] Falls kein Element gefunden wurde, gibt es einen 404 -Statuscode mit einem leeren Körper zurück.
GET /lineDieser Endpunkt gibt alle IDs in derselben Subchain/Linie zurück.
Es erwartet eine ID einer Zeile als id -Abfrageargument, z. http://localhost:7000/api/line?id=1234567890abcdef[...]
Es gibt einen Statuscode 200 lang mit dem folgenden JSON -Sortierarray von IDs zurück (Index 0 ist der Ursprung):
[
" 1234567890abcdef[...] " ,
" fedcba0987654321[...] "
] Falls kein Element gefunden wurde, gibt es einen 404 -Statuscode mit einem leeren Körper zurück.
POST /leafDieser Endpunkt fügt dem Index ein Element hinzu.
Es erwartet das folgende JSON -Objekt als Körper, wobei die ersten drei Felder obligatorisch sind:
{
"id" : " <The item ID as a hash string representation> " ,
"position" : 0 ,
"size" : 100 ,
"previous" : " <An optional item ID of the previous item in the current subchain if any> "
}Es gibt einen Statuscode und das folgende Objekt als JSON zurück:
{
"code" : 200 | 303 | 400 | 404 | 412 | 500,
"result" : " <The inserted item ID if success> " ,
"error" : " <The error message if failed> "
}Die Liste der Statuscodes (und deren Bedeutung) lautet wie folgt:
200 : Element eingefügt;303 : Artikel existiert bereits (nicht aktualisiert, da die Datei unveränderlich sein soll);400 : falscher Parameter (fehlendes Element, fehlendes obligatorisches Feld usw.);404 : Vorheriger Artikel nicht gefunden;412 : Etwas in den übergebenen Daten führte dazu, dass der Server fehlschlug (falsches JSON -Format, ...);500 : Auf dem Server ist ein Fehler aufgetreten.Im Durchschnitt sollte eine Basismaschine in der Lage sein, über 100 Millionen neue Datensätze aufzunehmen und etwa 5 Milliarden Suchanfragen pro Stunde abzuschließen.
Als Beispiel habe ich bei einem Apple MacBook Pro 2,3 GHz Intel Core i9 mit 16 Go DDR4 RAM bei 2400 MHz die folgenden Leistungen beobachtet, wenn ich 101 als Init Prime verwendete:
101 als Init Prime: Dieses Modul wird unter einer MIT -Lizenz verteilt.
Siehe die Lizenzdatei.
