treee
Update with Windows10 and MacOS executables
해시 ID로 식별되고 불변 파일에 저장된 데이터 용 빠른 인덱싱 엔진
이것은 Treee ™ 인덱싱 엔진의 GO 구현입니다. GO 프로젝트에서 모듈로 사용하는 라이브러리이며 HTTP를 통해 마이크로 서비스로 실행할 수있는 실행 파일입니다.
과제는 데이터가 하위 체인에서 서로 연결될 수있는 항목의 링크 된 목록 일 때 사용할 수있는 강력하고 안전한 검색 엔진을 설정하는 것이 었습니다. SHA-256 문자열 표현과 같은 해시 값으로 만 만들어진 식별자를 통해 인덱싱되고 모두 불변의 파일에 저장된 식별자를 통해 인덱스되었습니다.
최상의 응용 프로그램은 항목이 스마트 계약을 포함하는 거래 인 블록 체인 파일 과이 스마트 계약의 후속 용도 및/또는 수정 사항 인 항목의 각 하위 체인에 대한 것입니다. 따라서 Treee ™ 지수는 현재 Rooot ™ 블록 체인에 사용됩니다.
여기서는 서면 및 독서에 매우 강력한 해시 값 인 식별자를 기반으로 시스템을 색인화하기위한 알고리즘을 정의합니다.
Treee ™ 인덱스는 acyclic 그래프 (트리)로 구성됩니다. 각 노드에는 노드 주소 (아들) 또는 리프 세트가 포함되어 있으며, 하나 이상의 연결된 항목을 검색하는 데 도움이되는 정보에 해당하는 리프입니다 .
노드의 아들의 수는 결정적이며 나무의 깊이에 따라 다릅니다. 우리는 깊이 2의 노드의 아들 수, 깊이의 아들의 수인 깊이 1에서 노드의 아들의 수를 나타냅니다.
목표는 폭이 깊이를 줄이고 성능을 최적화하기 위해 적응력이있는 균형 잡힌 트리를 만드는 것입니다. 우리는 숫자를 색인하려고합니다.이 경우 항목 고유 식별자의 숫자 값을 인덱싱하려고합니다.
색인의 과정을 설명해 봅시다.
이진 트리의 경우 트리의 위치를 나타내는 이진 형태 (예 : 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에 넣어야합니다 (예 : API/Handlers/Leaf.go 파일의 GetLeaf() 구현 참조).
디버깅 또는 스토리지 목적을 위해 Treee 인덱스의 PrintAll() 메소드를 사용하여 기록 된 모든 잎을 작가에게 인쇄 할 수 있습니다 (인쇄 된 JSON을 아름답게하기위한 true 또는 원시 문자열의 false ).
// To print to Stdout
fmt . Println ( treee . PrintAll ( true )) 인덱스의 지속성은 삽입시 자동 저장을 사용하고 시작시 New() 와의 Treee 인스턴스화 대신 Load() 함수를 사용하여 달성됩니다.
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이 엔드 포인트는 인덱스에서 전달 된 항목을 제거합니다.
ID 배열이 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 상태 코드 또는 다음 JSON 목록과 함께 제거되지 않은 ID 목록과 함께 200 상태 코드를 반환합니다.
{
"ids" : [ " fedcba0987654321[...] " ]
}GET /leaf이 엔드 포인트는 전달 된 ID를 기반으로 항목을 검색합니다.
IDS 배열은 ids 쿼리 인수와 선택적 takeLast Boolean (기본적으로 false )을 기대합니다. http://localhost:7000/api/leaf?ids=1234567890abcdef[...]&ids=fedcba0987654321[...]&takeLast=true
다음 형식과 관련하여 JSON 객체와 함께 상태 코드 200 반환합니다.
[
{
"id" : " 1234567890abcdef[...] " ,
"position" : 0 ,
"size" : 100 ,
"origin" : " 1234567890abcdef[...] " ,
"previous" : " 1234567890abcdef[...] " ,
"next" : " "
},
[ ... ]
] 항목이 발견되지 않은 경우 빈 본체가있는 404 상태 코드를 반환합니다.
GET /line이 엔드 포인트는 모든 ID를 동일한 서브 체인/라인으로 반환합니다.
그것은 라인의 ID를 id 쿼리 인수로 기대합니다. http://localhost:7000/api/line?id=1234567890abcdef[...]
다음 JSON 정렬 된 ID 배열 (INDEX 0 은 원점)으로 200 길이의 상태 코드를 반환합니다.
[
" 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 : 서버에서 오류가 발생했습니다.평균적으로, 기본 기계는 1 억 명 이상의 새로운 기록을 섭취하고 시간당 약 50 억 개의 검색 쿼리를 처리 할 수 있어야합니다.
예를 들어, Apple MacBook PRO 2.3GHz Intel Core I9에서 16 GO DDR4 RAM이 2400 MHz에서 클럭 된 경우 101 초기 프라임으로 사용할 때 다음과 같은 성능을 관찰했습니다.
101 사용하여 INT PRIME를 사용합니다. 이 모듈은 MIT 라이센스로 배포됩니다.
라이센스 파일을 참조하십시오.
