기본 색인에 aerospike에서 btree를 사용하면 어떤 이점이 있습니까?

Question

나는 Aerospike의 문서를 검토하고있었습니다. 기본 키를 저장하기 위해 Aerospike는 해싱을 사용하고 해시는 BTree를 가리키고 bTree는 실제 레코드에 대한 포인터를 포함한다는 것을 알게되었습니다. Redis가 알고있는 한, 해시 만 사용합니다 (충돌 해결을 위해 해시 목록을 관리합니다). 해시는 실제 레코드를 가리 킵니다.

aerospike에서 Btree를 사용하면 어떤 이점이 있습니까? 그것의 1 차적인 열쇠 aerospike 에의 한 기록에 접근하는 것이 O (logn)를 가지고 갈는 것을 의미하지 않는가? redis는 O (1) 만 사용합니다.

내가 틀릴 수도 있지만 그게 모두 documentation에서 이해할 수 있습니다. 이 주제에 대해 좀 더 밝혀 줄 수 있습니까?

Answer 1

나는 질문의 요점 모르겠지만, 여기 간다 : 사실

Aerospike의 primary index 파티션 당 1 4096 sprigs 사이 red-black trees의 분산 해시,합니다 (partition-tree-sprigs 구성 PARAM 참조).

클러스터의 노드에인 논리 파티션이 4096 개 있습니다. record을 식별하는 키는 (namespace, set, PK) 3 튜플을 RIPEMD-160 (클라이언트가 자동으로 처리 함)을 통과하여 생성 된 20 바이트 다이제스트입니다. 레코드는 이고이 다이제스트의 비트는 파티션 ID를 계산하는 데 사용되므로 특정 파티션에 일관되게 해시 된입니다.

단일 노드에서 실행되는 단일 코어 단일 스레드 응용 프로그램으로 설계된 Redis와 달리 Aerospike는 분산 데이터베이스로 구축되었습니다. 사용자가 응용 프로그램 측 솔루션이나 미들웨어를 사용하여 Redis 클러스터를 임시로 클러스터링 할 수 있습니다. Aerospike의 경우 클러스터의 모든 노드가 있고 모든 클라이언트는 partition map을 공유합니다.

클라이언트는 클러스터의 파티션 맵을 알고 있으므로 마스터 파티션 (또는 복제본 파티션이있는 노드 - 이것은 replica read policy에 의해 제어 됨)을 보유한 노드로부터 항상 한 홉 떨어져 있습니다. 따라서 클러스터의 올바른 노드에 대한 O (1)입니다. 해당 노드 내에서 파티션의 rbTree를 찾으려면 O (1)이고 모든 작업은 O (log n)입니다.

hash table에 많은 데이터가없는 경우 (Redis에서 사용하는 데이터 구조에 대해 옳았다 고 가정 할 때) 레코드를 찾는 것은 O (1)이어야합니다. 그러나 해시 테이블의 슬롯보다 많은 요소가 있으면 O (n) 인 연결된 목록으로 전환됩니다. rbTree의 경우 평균 및 최악의 경우 O (log n)입니다. Aerospike는 예측 가능한 낮은 대기 시간을 갖는 대규모 데이터 세트를 처리하기 위해 의도되었으므로 rbTree가 더 적절했습니다. 레코드를 가져 오는 비용은 클러스터의 데이터 양에 관계없이 동일합니다.