treee
Update with Windows10 and MacOS executables
Moteur d'indexation rapide pour les données identifiées par ID hachée et stockées dans un fichier immuable
Il s'agit de l'implémentation GO du moteur d'indexation Treee ™. C'est à la fois une bibliothèque à utiliser comme module dans vos projets GO et un exécutable à exécuter en micro-service via HTTP.
Le défi était de configurer un moteur de recherche puissant et sûr à utiliser lorsque les données sont une liste liée d'éléments qui pourraient être eux-mêmes connectés les uns aux autres dans les sous-chaînes, indexés via leurs identifiants qui ne sont faits que de valeurs hachées (comme les représentations de chaînes SHA-256), et tous stockés dans un fichier immuable.
Sa meilleure application concerne un fichier blockchain où un élément est une transaction intégrant un contrat intelligent, et chaque sous-chaîne d'articles les utilisations et / ou les modifications ultérieures de ce contrat intelligent. En tant que tel, l'index Treee ™ est actuellement utilisé dans la blockchain Rooot ™.
Nous définissons ici un algorithme pour indexer le système basé sur des identifiants qui sont des valeurs hachés qui sont en même temps très puissantes pour l'écriture et la lecture.
L'index Treee ™ est construit comme un graphique acyclique (une arbre). Chaque nœud contient soit l'adresse de nœud (ses fils) ou un ensemble de feuilles , une feuille correspondant aux informations aidant à récupérer un ou plusieurs éléments liés.
Le nombre de fils d'un nœud est déterministe et dépend de la profondeur de l'arbre. Nous désignons le nombre de fils des nœuds à la profondeur 1, le nombre de fils des nœuds à la profondeur 2, ..., le nombre de fils en profondeur.
L'objectif est de créer un arbre équilibré dont la largeur est adaptative pour réduire la profondeur et optimiser les performances. Nous cherchons à indexer les numéros, dans ce cas la valeur numérique des identificateurs uniques des éléments.
Expliquons le cours de l'indice.
Pour l'arbre binaire, nous écrivons le nombre sous forme binaire (par exemple, 100 ) qui indique sa position dans l'arbre.
À l'étape, nous passons à l'enfant si le bit est 0 , sinon nous passons à l'enfant si le bit est 1 . Nous nous arrêtons lorsque le nœud est une feuille .
Pour l'arbre, nous construisons une représentation de ce nombre par une séquence de nombres et nous traversons l'arbre de la même manière. À l'étape de la profondeur, nous passons à l'enfant si le représentant est 0 , nous passons à l'enfant si le représentant est 1 , ..., nous passons à l'enfant si le représentant l'est. Nous nous arrêtons lorsque le nœud est une feuille .
Pour construire la représentation d'un nombre, nous prendrons successivement le modulo des nombres premiers. Selon le théorème des restes chinois, chaque nombre a un représentant unique qui pourrait être écrit comme la continuation de ces modulos. En effet, un nombre peut être écrit sous la forme suivante:
La valeur de l'identifiant de l'élément (son nombre) est indiquée et le numéro de modulation. Les modulos sont calculés dans les entiers de taille fixe. Étant donné que la multiplication est plus rapide que la division (nécessaire pour le calcul du modulo), on peut utiliser des multiplications au moyen de flotter :.
Compte tenu de la nature aléatoire des nombres (ou du pseudo-aléatoire, puisque les identifiants des éléments sont générés par les technologies de hachage cryptographique), l'arbre est équilibré. Pour déséquilibrer l'arbre de manière malveillante, il serait nécessaire de pouvoir générer des hachages dont le modulo suit une trajectoire particulière. Cependant, la difficulté d'une telle opération augmente de façon exponentielle (de l'ordre de où est la profondeur). Pour rappel, le produit des 16 premiers nombres premiers est égal. Par conséquent, dès que l'indice contient une quantité raisonnablement importante de données, le déséquilibre de l'arbre de manière malveillante deviendrait de plus en plus impossible, si possible.
Une feuille contient la liste des informations suivantes sur un élément:
Une feuille dont le champ d'élément suivant est vide est le dernier élément de la sous-chaîne.
Une feuille dont le champ d'élément d'origine est égal à l'identifiant de l'élément actuel est nécessairement l'origine de la sous-chaîne. En tant que tel, il a un fonctionnement particulier car, s'il devait y avoir un ou plusieurs articles par la suite, le dernier élément de la sous-chaîne sera identifié ici comme l'élément précédent. Les trois derniers champs de la feuille correspondent donc à une liste liée circulaire.
Pour ajouter un élément à l'index:
Pour lire / rechercher un élément dans l'index:
Lorsque nous utilisons l'index, nous pouvons voir que nous effectuerons au plus 3 lectures ou 3 écritures et les exécutions d'index de commande, où est le nombre d'éléments dans l'index.
Pour plus de détails, n'hésitez pas à lire le livre blanc complet.
$ 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
} Pour de meilleures performances, vous devez mettre vos demandes de recherche dans différents Goroutines (voir l'implémentation GetLeaf() dans API / Handlers / Leaf.go Fichier par exemple).
À des fins de débogage ou de stockage, vous voudrez peut-être utiliser la méthode PrintAll() sur l'index Treee pour imprimer toutes les feuilles enregistrées à un écrivain (la transmettre true comme argument pour embellir le JSON imprimé, ou false pour la chaîne brute).
// To print to Stdout
fmt . Println ( treee . PrintAll ( true )) La persistance de l'index est obtenue grâce à l'utilisation de la sauvegarde automatique effectuée lors de l'insertion et à l'utilisation de la fonction Load() au lieu de l'instanciation arborescence avec New() au démarrage.
treee , err := index . Load ( "path/to/treee.json" ) // If empty, will use "./saved/treee.json"Il peut être désactivé en utilisant la variable d'environnement ou l'indicateur correspondant dans la ligne de commande, ou même par programme:
treee . UsePersistence ( false ) // If you're positive you don't want itVous pouvez simplement créer l'exécutable et démarrer une instance du moteur d'indexation Treee ™.
$ 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")
S'il est défini, les variables d'environnement suivantes remplaceront toute configuration ou indicateur par défaut correspondant passé avec la ligne de commande:
HOST : l'adresse de l'hôte;HTTP_PORT : le numéro de port http à utiliser;INDEX_PATH : le chemin du fichier index au format JSON;INIT_PRIME : le numéro de premier ordre initial (notez qu'il n'aura aucun effet si vous utilisez un fichier car ce dernier prévaudra);USE_PERSISTENCE : se définissez false pour désactiver l'utilisation de l'enregistrement de l'index dans un fichier. Les points de terminaison suivants sont disponibles sous le groupe /api :
DELETE /leafCe point de terminaison supprime les éléments passés de l'index.
Il s'attend à un tableau d'IDS comme argument de requête ids , par exemple.
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 Il renvoie un code d'état 204 si tous les éléments passés étaient supprimés, ou un code d'état de 200 avec la liste JSON suivante des ID non supprimés si certains n'étaient pas supprimés:
{
"ids" : [ " fedcba0987654321[...] " ]
}GET /leafCe point de terminaison recherche des éléments basés sur les ID passés.
Il s'attend à un tableau d'IDS en tant qu'argument de requête ids et à takeLast Boolean facultatif (par défaut false ), par exemple. http://localhost:7000/api/leaf?ids=1234567890abcdef[...]&ids=fedcba0987654321[...]&takeLast=true
Il renvoie un code d'état 200 avec un objet JSON concernant le format suivant:
[
{
"id" : " 1234567890abcdef[...] " ,
"position" : 0 ,
"size" : 100 ,
"origin" : " 1234567890abcdef[...] " ,
"previous" : " 1234567890abcdef[...] " ,
"next" : " "
},
[ ... ]
] Dans le cas où aucun élément n'a été trouvé, il renvoie un code d'état 404 avec un corps vide.
GET /lineCe point de terminaison renvoie tous les ID dans la même sous-chaîne / ligne.
Il s'attend à tout ID d'une ligne comme argument de requête id , par exemple. http://localhost:7000/api/line?id=1234567890abcdef[...]
Il renvoie un code d'état 200 long avec le tableau trié JSON suivant (index 0 étant l'origine):
[
" 1234567890abcdef[...] " ,
" fedcba0987654321[...] "
] Dans le cas où aucun élément n'a été trouvé, il renvoie un code d'état 404 avec un corps vide.
POST /leafCe point de terminaison ajoute un élément à l'index.
Il attend l'objet JSON suivant en tant que corps, les trois premiers champs étant obligatoires:
{
"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> "
}Il renvoie un code d'état et l'objet suivant comme JSON:
{
"code" : 200 | 303 | 400 | 404 | 412 | 500,
"result" : " <The inserted item ID if success> " ,
"error" : " <The error message if failed> "
}La liste des codes d'état (et leur signification) est la suivante:
200 : Article inséré;303 : L'article existe déjà (non mis à jour car le fichier est censé être immuable);400 : paramètre mauvais (élément manquant, champ obligatoire manquant, etc.);404 : Article précédent passé non trouvé;412 : Quelque chose dans les données passées a provoqué l'échec du serveur (format JSON incorrect, ...);500 : Une erreur s'est produite sur le serveur.En moyenne, une machine de base devrait être en mesure d'ingrer plus de 100 millions de nouveaux enregistrements et de gérer environ 5 milliards de requêtes de recherche par heure.
À titre d'exemple, sur un Apple MacBook Pro 2.3 GHz Intel Core i9 avec 16 GO DDR4 RAM chronométrés à 2400 MHz, j'ai observé les performances suivantes lors de l'utilisation 101 comme Init Prime:
101 comme Init Prime: Ce module est distribué sous une licence MIT.
Voir le fichier de licence.
