treee
Update with Windows10 and MacOS executables
Mecanismo de indexação rápida para dados identificados por ID de hash e armazenados em um arquivo imutável
Esta é a implementação Go do mecanismo de indexação Treee ™. É uma biblioteca usar como um módulo em seus projetos GO e um executável para executar como micro-serviço sobre o HTTP.
O desafio era configurar um mecanismo de pesquisa poderoso e seguro para usar quando os dados são uma lista vinculada de itens que poderiam ser conectados entre si em subcains, indexados por meio de seus identificadores que são feitos apenas de valores de hash (como representações de string sha-256) e todos armazenados em um arquivo imutável.
Seu melhor aplicativo é para um arquivo blockchain em que um item é uma transação que incorpore um contrato inteligente e cada subchain de itens os usos e/ou modificações subsequentes desse contrato inteligente. Como tal, o índice Treee ™ é atualmente usado no Rooot ™ Blockchain.
Definimos aqui um algoritmo para indexar o sistema com base em identificadores que são valores de hash que são ao mesmo tempo muito poderosos para a escrita e a leitura.
O índice Treee ™ é construído como um gráfico acíclico (uma árvore). Cada nó contém o endereço do nó (seus filhos) ou um conjunto de folhas , uma folha correspondente às informações que ajudam a recuperar um ou mais itens vinculados.
O número de filhos de um nó é determinístico e depende da profundidade da árvore. Denotamos pelo número de filhos dos nós na profundidade 1, o número de filhos dos nós na profundidade 2, ..., o número de filhos em profundidade.
O objetivo é criar uma árvore equilibrada cuja largura é adaptativa para diminuir a profundidade e otimizar o desempenho. Estamos buscando números de índice, neste caso o valor numérico dos identificadores exclusivos dos itens.
Vamos explicar o curso do índice.
Para a árvore binária, escrevemos o número em forma binária (por exemplo, 100 ) que indica sua posição na árvore.
Na etapa, passamos para a criança se o bit for 0 , caso contrário, passamos para a criança se o bit for 1 . Paramos quando o nó é uma folha .
Para a árvore, construímos uma representação desse número por uma sequência de números e atravessamos a árvore da mesma maneira. Na etapa de profundidade, passamos para a criança se o representante for 0 , passamos para a criança se o representante for 1 , ..., passamos para a criança se o representante for. Paramos quando o nó é uma folha .
Para construir a representação de um número, levaremos sucessivamente o módulo de números primos. De acordo com o teorema dos restos chineses, cada número tem um representante único que pode ser escrito como a continuação desses módulos. De fato, um número pode ser escrito na seguinte forma:
O valor do identificador do item (seu número) é denotado e o número de modulação. Os módulos são calculados para números inteiros de tamanho fixo. Como a multiplicação é mais rápida que a divisão (necessária para o cálculo do módulo), pode -se usar multiplicações por meio de flutuação :.
Dada a natureza aleatória dos números (ou pseudo-aleatório, como os identificadores dos itens são gerados por tecnologias de hash criptográficas), a árvore é equilibrada. Para desequilibrar a árvore de uma maneira maliciosa, seria necessário poder gerar hashes cujo módulo segue uma trajetória específica. No entanto, a dificuldade de tal operação aumenta exponencialmente (da ordem de onde está a profundidade). Como lembrete, o produto dos 16 primeiros números primos é igual. Portanto, assim que o índice contém uma quantidade razoavelmente grande de dados, desequilibrar a árvore de maneira maliciosa se tornaria cada vez mais impossível, se possível.
Uma folha contém a seguinte lista de informações sobre um item:
Uma folha cujo próximo campo de item está vazio é o último item no subchain.
Uma folha cujo campo de item de origem é igual ao identificador do item atual é necessariamente a origem do subchain. Como tal, ele tem uma operação específica, pois, se houver um ou mais itens posteriormente, o último item do subchain será identificado aqui como o item anterior. Os últimos três campos da folha correspondem, portanto, a uma lista ligada circular.
Para adicionar um elemento ao índice:
Para ler/pesquisar um item no índice:
Ao usar o índice, podemos ver que executaríamos no máximo três leituras ou 3 gravações e execuções de índice de ordem, onde é o número de itens no índice.
Para mais detalhes, fique à vontade para ler o white paper completo.
$ 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
} Para melhor desempenho, você deve colocar suas solicitações de pesquisa em diferentes goroutines (consulte a implementação GetLeaf() no arquivo API/Handlers/Leaf.go, por exemplo).
Para fins de depuração ou armazenamento, convém usar o método PrintAll() no índice Treee para imprimir todas as folhas gravadas para um escritor (passando por true como argumento para embelezar o JSON impresso, ou false for the Raw String).
// To print to Stdout
fmt . Println ( treee . PrintAll ( true )) A persistência do índice é alcançada através do uso do salvamento automático feito após a inserção e o uso da função de Load() em vez de instanciação de árvores com New() na inicialização.
treee , err := index . Load ( "path/to/treee.json" ) // If empty, will use "./saved/treee.json"Pode ser desativado usando a variável ou sinalizador de ambiente correspondente na linha de comando, ou mesmo programaticamente:
treee . UsePersistence ( false ) // If you're positive you don't want itVocê pode simplesmente criar o executável e iniciar uma instância do mecanismo de indexação 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")
Se definido, as seguintes variáveis de ambiente substituirão qualquer configuração padrão correspondente ou sinalizador passada com a linha de comando:
HOST : o endereço do host;HTTP_PORT : o número da porta HTTP a ser usado;INDEX_PATH : o caminho para o arquivo de índice no formato json;INIT_PRIME : o número primitivo inicial (observe que não terá nenhum efeito se usar um arquivo porque o último prevalecerá);USE_PERSISTENCE : Defina false para desativar o uso de salvar o índice em um arquivo. Os seguintes pontos de extremidade estão disponíveis no grupo /api :
DELETE /leafEste terminal remove os itens passados do índice.
Ele espera uma variedade de IDs como ids de consulta, por exemplo.
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 Ele retorna um código de status 204 se todos os itens passados foram removidos ou um código de status de 200 , juntamente com a seguinte lista JSON de IDs não selecionados se alguns não foram removidos:
{
"ids" : [ " fedcba0987654321[...] " ]
}GET /leafEste terminal pesquisa itens com base nos IDs aprovados.
Ele espera uma variedade de IDs como ids , argumento de consulta e um takeLast booleano opcional (padrão para false ), por exemplo. http://localhost:7000/api/leaf?ids=1234567890abcdef[...]&ids=fedcba0987654321[...]&takeLast=true
Ele retorna um código de status 200 , juntamente com um objeto JSON, respeitando o seguinte formato:
[
{
"id" : " 1234567890abcdef[...] " ,
"position" : 0 ,
"size" : 100 ,
"origin" : " 1234567890abcdef[...] " ,
"previous" : " 1234567890abcdef[...] " ,
"next" : " "
},
[ ... ]
] No caso de nenhum item ter sido encontrado, ele retorna um código de status 404 com um corpo vazio.
GET /lineEste terminal retorna todos os IDs na mesma subchain/linha.
Ele espera qualquer identificação de uma linha como argumento de consulta de id , por exemplo. http://localhost:7000/api/line?id=1234567890abcdef[...]
Ele retorna um código de status 200 de comprimento com a seguinte matriz JSON classificada de IDs (índice 0 sendo a origem):
[
" 1234567890abcdef[...] " ,
" fedcba0987654321[...] "
] No caso de nenhum item ter sido encontrado, ele retorna um código de status 404 com um corpo vazio.
POST /leafEste endpoint adiciona um item ao índice.
Ele espera o seguinte objeto JSON como corpo, sendo os três primeiros campos obrigatórios:
{
"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> "
}Ele retorna um código de status e o seguinte objeto como JSON:
{
"code" : 200 | 303 | 400 | 404 | 412 | 500,
"result" : " <The inserted item ID if success> " ,
"error" : " <The error message if failed> "
}A lista de códigos de status (e seu significado) é o seguinte:
200 : item inserido;303 : O item já existe (não atualizado como o arquivo deve ser imutável);400 : parâmetro errado (item ausente, campo obrigatório ausente, etc.);404 : Passado item anterior não encontrado;412 : algo nos dados passados fez com que o servidor falhasse (formato JSON incorreto, ...);500 : ocorreu um erro no servidor.Em média, uma máquina básica deve ser capaz de ingerir mais de 100 milhões de novos registros e lidar com cerca de 5 bilhões de consultas de pesquisa por hora.
Como exemplo, em um Apple MacBook Pro 2,3 GHz Intel Core i9 com 16 Go Ddr4 Ram com 2400 MHz, observei as seguintes apresentações ao usar 101 como init Prime:
101 como init Prime: Este módulo é distribuído sob uma licença do MIT.
Veja o arquivo de licença.
