treee
Update with Windows10 and MacOS executables
Быстрое индексация двигателя для данных, идентифицированных с помощью идентификатора хэширования и хранящегося в неподвижном файле
Это реализация GO индексации Treee ™. Это как библиотека, которую можно использовать в качестве модуля в ваших проектах GO, и исполняемый файл для работы в качестве микросхемы над HTTP.
Задача состояла в том, чтобы настроить мощную и безопасную поисковую систему для использования, когда данные представляют собой какой-то связанный список элементов, которые сами могут быть подключены друг к другу в подразделениях, индексированные через их идентификаторы, которые сделаны только из хешированных значений (например, представления строк SHA-256), и все хранятся в непомеченном файле.
Его лучшее приложение - файл блокчейна, в котором элемент представляет собой транзакцию, внедряющую интеллектуальный контракт, и каждый подраздел элементов, которые последующие используют и/или модификации этого смарт -контракта. Таким образом, индекс Treee ™ в настоящее время используется в блокчейне Rooot ™.
Здесь мы определяем алгоритм индексации системы на основе идентификаторов, которые являются хэшированными ценностями, которые в то же время очень мощный для письма и чтения.
Индекс Treee ™ построен как ациклический график (дерево). Каждый узел содержит либо адрес узела (его сыновья), либо набор листьев , лист, соответствующий информации, помогающей получить один или несколько связанных элементов.
Количество сыновей узла детерминированно и зависит от глубины дерева. Мы обозначаем количество сыновей узлов на глубине 1, количество сыновей узлов на глубине 2, ..., количество сыновей на глубине.
Цель состоит в том, чтобы создать сбалансированное дерево, ширина которой является адаптивной для уменьшения глубины и оптимизации производительности. Мы стремимся индексировать числа, в данном случае числовое значение уникальных идентификаторов элементов.
Давайте объясним ход индекса.
Для двоичного дерева мы пишем число в двоичной форме (например, 100 ), которое указывает его положение в дереве.
На шаге мы переходим к ребенку, если бит равен 0 , в противном случае мы переходим к ребенку, если бит составляет 1 . Мы останавливаемся, когда узел - лист .
Для дерева мы строим представление этого числа последовательно числа и пересекаем дерево таким же образом. На шаге глубины мы передаем ребенку, если представитель равен 0 , мы передаем ребенку, если представитель составляет 1 , ..., мы передаем ребенку, если представитель. Мы останавливаемся, когда узел - лист .
Чтобы построить представление числа, мы последовательно возьмем модулю основных чисел. В соответствии с теоремой китайских остатков, каждое число имеет уникальный представитель, который может быть написан как продолжение этих модуло. Действительно, число может быть записано в следующей форме:
Значение идентификатора элемента (его число) обозначается и модулирующее число. Модули рассчитываются в целых числах фиксированного размера. Поскольку умножение быстрее, чем деление (необходимое для расчета модуля), можно использовать умножение посредством плавания :.
Учитывая случайный характер чисел (или псевдолупита, поскольку идентификаторы элементов генерируются с помощью криптографических технологий хэширования), дерево сбалансировано. Чтобы разоблачить дерево вредоносным способом, необходимо было бы иметь возможность генерировать хэши, чей модуло следует за определенной траекторией. Однако сложность такой операции увеличивается в геометрической прогрессии (порядок, где есть глубина). В качестве напоминания продукт первых 16 основных чисел равны. Следовательно, как только индекс содержит достаточно большое количество данных, разбалансирование дерева злонамеренным способом станет все более и более невозможным, если это вообще возможно.
Лист содержит следующий список информации о элементе:
Лист , чье следующее поле предмета пустое, является последним элементом в подчинке.
Лист , поле для предмета происхождения которого равна идентификатору текущего элемента, обязательно является источником подчистика. Таким образом, он имеет определенную работу, поскольку, если после этого было одно или несколько элементов, последний элемент подчистия будет идентифицирован здесь как предыдущий элемент. Поэтому последние три поля листа соответствуют круговому списку.
Чтобы добавить элемент в индекс:
Читать/поиск элемента в индексе:
При использовании индекса мы видим, что мы выполним не более 3 чтения или 3 записи, а индекс заказа заказа, где количество элементов в индексе.
Для получения более подробной информации не стесняйтесь читать полную белую бумагу.
$ 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
} Для лучшей производительности, вы должны поместить свои запросы на поиск в различных goroutines (см. Например, в файле goroutines (см. GetLeaf() в файле API/Handlers/Leaf.go).
В целях отладки или хранения вы можете использовать метод PrintAll() на индексе Treee , чтобы распечатать все записанные листья писателю (передавая его true как аргумент для украшения печатного JSON или false для необработанной строки).
// To print to Stdout
fmt . Println ( treee . PrintAll ( true )) Постоянство индекса достигается за счет использования автоматического сохранения, выполненного при вставке, и использования функции Load() вместо экземпляров Treee с помощью New() при запуске.
treee , err := index . Load ( "path/to/treee.json" ) // If empty, will use "./saved/treee.json"Он может быть отключен, используя соответствующую переменную среды или флаг в командной строке или даже программно:
treee . UsePersistence ( false ) // If you're positive you don't want itВы можете просто создать исполняемый файл и запустить экземпляр индексации 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")
Если установлено, следующие переменные среды будут переоценить любую соответствующую конфигурацию по умолчанию или флаг, передаваемую с помощью командной строки:
HOST : адрес хоста;HTTP_PORT : номер порта HTTP для использования;INDEX_PATH : путь к файлу индекса в формате JSON;INIT_PRIME : начальный основной номер (обратите внимание, что он не будет иметь никакого эффекта, если использует файл, потому что последний будет преобладать);USE_PERSISTENCE : установите false , чтобы отключить использование сохранения индекса в файл. Следующие конечные точки доступны в группе /api :
DELETE /leafЭта конечная точка удаляет прошедшие элементы из индекса.
Он ожидает массив идентификаторов в виде аргумента запроса ids , например.
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 Он возвращает код состояния 204 , если все прошедшие элементы были удалены, или 200 кода статуса вместе со следующим списком неосновных идентификаторов JSON, если некоторые не были удалены:
{
"ids" : [ " fedcba0987654321[...] " ]
}GET /leafЭта конечная точка ищет элементы на основе прошедших идентификаторов.
Он ожидает массив идентификаторов в виде аргумента запроса ids и дополнительного логического в takeLast (по умолчанию в false ), например. http://localhost:7000/api/leaf?ids=1234567890abcdef[...]&ids=fedcba0987654321[...]&takeLast=true
Он возвращает код состояния 200 вместе с объектом JSON, относящимся к следующему формату:
[
{
"id" : " 1234567890abcdef[...] " ,
"position" : 0 ,
"size" : 100 ,
"origin" : " 1234567890abcdef[...] " ,
"previous" : " 1234567890abcdef[...] " ,
"next" : " "
},
[ ... ]
] В случае, если элемент не был найден, он возвращает код состояния 404 с пустым корпусом.
GET /lineЭта конечная точка возвращает все идентификаторы в одной и той же подчинке/строке.
Он ожидает любого идентификатора строки в качестве аргумента запроса id , например. http://localhost:7000/api/line?id=1234567890abcdef[...]
Он возвращает код состояния 200 длиной со следующим JSON сортированным массивом идентификаторов (индекс 0 - это происхождение):
[
" 1234567890abcdef[...] " ,
" fedcba0987654321[...] "
] В случае, если элемент не был найден, он возвращает код состояния 404 с пустым корпусом.
POST /leafЭта конечная точка добавляет элемент в индекс.
Он ожидает следующего объекта JSON в качестве тела, первые три поля являются обязательными:
{
"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> "
}Он возвращает код состояния и следующий объект как JSON:
{
"code" : 200 | 303 | 400 | 404 | 412 | 500,
"result" : " <The inserted item ID if success> " ,
"error" : " <The error message if failed> "
}Список кодов статуса (и их значение) заключается в следующем:
200 : вставлен товара;303 : пункт уже существует (не обновляется, поскольку файл должен быть неизменным);400 : неправильный параметр (отсутствующий элемент, отсутствующее обязательное поле и т. Д.);404 : прошел предыдущий пункт, не найденной;412 : что -то в передаваемых данных привело к сбою сервера (неверный формат JSON, ...);500 : на сервере произошла ошибка.В среднем базовая машина должна иметь возможность принимать более 100 миллионов новых записей и обрабатывать около 5 миллиардов поисковых запросов в час.
Например, на Apple MacBook Pro 2,3 ГГц Intel Core I9 с 16 GO DDR4 RAM с тактовой частотой при 2400 МГц я наблюдал следующие выступления при использовании 101 в качестве init prime:
101 в качестве init prime: Этот модуль распределен по лицензии MIT.
Смотрите файл лицензии.
