지오카우치: 대량 삽입

그리고 새 릴리스 의 지오카우치 는 공간 인덱스 구축 시간을 크게(최대 10배) 개선합니다. 이는 새로운 대량 삽입 알고리즘을 사용했기 때문입니다. 공간 인덱스( R-tree)는 CouchDB의 B-트리와 마찬가지로 추가 전용 데이터 구조로 구현되며, 한 번에 큰 블록의 인덱스를 추가할 수 있어 대량 삽입의 특성을 활용할 수 있습니다.

이전 구현

이전 버전의 GeoCouch에서는 각 지오메트리 항목이 하나씩 삽입되었습니다. 이로 인해 인덱스에 추가할 때마다 엄청난 양의 작은 디스크 작업이 발생했습니다. 다음은 이전 알고리즘에 대한 요약입니다.

• 루트 노드에서 시작
• 바운딩 박스의 확장이 가장 적게 필요한 첫 번째 자식 찾기
• 대상 잎에 도달할 때까지 R-Tree를 따라 이동합니다.
• 새 노드를 리프 노드에 삽입합니다.
• 새로 삽입된 노드에서 루트 노드까지 경로의 모든 노드를 다시 작성합니다.

첫 번째 단계는 모든 R-tree 구현에 삽입하는 데 필요한 기본 단계입니다. 이 방법의 문제점은 추가 전용 데이터 구조를 사용할 때 삽입된 노드부터 루트 노드까지 모든 노드를 다시 작성하여 인덱스에 추가해야 하므로 쓰기 횟수가 많이 필요하다는 것입니다. 추가 전용 데이터 구조의 특성에 대한 자세한 내용은 내 새 인덱서 자습서 만들기

현재 구현

공간 인덱스는 보기와 비슷한 방식으로 구현되며, 새 문서가 삽입될 때가 아니라 인덱스 사용 요청이 있을 때 인덱스가 업데이트됩니다. 따라서 인덱스에 액세스하면 가장 최근에 삽입된 문서를 따라잡아야 합니다. 둘 이상의 문서가 변경된 경우, 이를 일괄 처리하여 인덱스의 디스크 내 수정 작업을 줄이고 전반적인 업데이트 성능을 개선하는 것이 더 합리적입니다.

대량 로딩 및 대량 삽입

일괄 로딩과 일괄 삽입에는 차이가 있습니다. 로드는 처음부터 새로운 데이터 구조를 만드는 것을 의미합니다. 대량 삽입은 이미 존재하는 구조에 여러 개의 새 항목을 삽입하는 것을 의미합니다. GeoCouch의 구현에는 이 두 가지가 모두 필요하며 주로 두 가지 논문을 기반으로 합니다. 삽입의 경우 시드 클러스터링을 통한 R-트리의 대량 삽입 그리고 대량 로딩의 경우 OMT: R-tree를 위한 하향식 대량 로딩 알고리즘의 중복 최소화 가 구현되었습니다(약간의 수정이 있었습니다).

알고리즘

전체 설명을 읽고 싶지 않은 분들을 위해 대량 삽입 알고리즘에 대한 간략한 요약을 소개합니다. 기본 아이디어는 전체 대량 업데이트에서 현재 존재하는 인덱스 구조와 일치하는 클러스터를 생성하는 것입니다(예 대상 트리). 그런 다음 이러한 클러스터는 대상 트리에 그대로 삽입되어 R-트리에 일괄 로드됩니다.

각 단계를 자세히 살펴 보겠습니다. 알고리즘은 대상 트리의 상위 레벨을 메모리에 로드하는 것으로 시작하며(최대 3개, 그렇지 않으면 메모리 소비가 폭발적으로 증가함), 이를 소위 시드 트리. 그런 다음 리프는 클러스터링을 수행하는 데 사용됩니다. 대량 삽입의 각 항목은 일반적인 R-트리 삽입 알고리즘과 유사한 알고리즘을 사용하여 시드 트리에 통합됩니다. 차이점은 새 항목이 디스크에 기록되지 않고 나머지 대량 삽입 프로세스가 계속되는 동안 일시적으로 메모리에 보관된다는 것입니다.

모든 항목이 처리되면 시드 트리 탐색이 시작됩니다. 아래로 이동 깊이 우선 방식 리프 노드에 도달하면 일부 처리가 완료됩니다. 현재 노드에 임시로 저장된 모든 항목은 새 R-트리에 일괄 로드됩니다( 소스 트리)를 OMT 알고리즘을 사용하여 생성합니다. 이 트리는 시드 트리 리프의 원래 자식 노드에 추가됩니다. 하지만 문제가 있습니다. R-트리는 항상 균형이 잘 잡혀 있지만 소스 트리의 높이를 그대로 추가하면 맞지 않을 수 있습니다. 기본적으로 세 가지 경우가 있습니다:

1. 소스 트리가 맞습니다: 트리를 그대로 삽입할 수 있습니다.
2. 소스 트리가 너무 작음: 새 시드 트리가 만들어집니다. 루트 노드는 현재 시드 트리의 리프 노드입니다. 재귀적으로 진행합니다.
3. 소스 트리가 너무 큰 경우: 소스 트리의 루트 노드 대신 자식 노드를 사용합니다(재귀적으로 높이가 일치할 때까지 아래로 내려갑니다).

소스 트리의 루트 노드는 삽입되는 노드가 커버하는 영역의 대부분을 차지할 수 있으므로 쿼리 성능을 개선하기 위해 일부 재포장이 수행됩니다. 소스 트리 노드와 교차하는 모든 노드의 자식과 소스 트리의 자식이 차지하는 영역을 최소화하기 위해 재포장됩니다(OMT 알고리즘이 사용됨). 이 프로세스가 완료되면 재포장된 노드가 최종적으로 디스크에 기록됩니다.

하위 트리가 완료될 때마다 부모 노드가 디스크에 기록됩니다. 그 결과, 대량 인덱스 업데이트 프로세스는 모든 삽입 시 루트까지의 모든 상위 노드를 다시 작성하는 기존의 단일 항목 삽입 전략에 비해 많은 물리적 디스크 쓰기 횟수를 절약할 수 있습니다.

대량 삽입의 과제

기본 알고리즘은 간단하지만, 이를 달성하는 데 필요한 코드가 왜 그렇게 복잡한지 궁금해하는 분들도 계실 것입니다. 가장 큰 문제는 결과물인 R-트리 높이의 균형을 맞추고 노드당 자식 수를 최대 수 이하로 유지하는 것입니다. 대량으로 삽입하면 오버플로(따라서 분할)를 초래하는 삽입이 있을 수 있으며, 이 작업을 트리의 맨 위까지 재귀적으로 수행해야 합니다.

또 다른 과제는 대상 트리의 현재 높이, 대상/시드 트리 내의 현재 위치, 삽입될 소스 트리의 예상 높이를 메모리에서 추적하는 것입니다. 이 작업은 메모리를 너무 많이 소모하지 않도록 효율적으로 수행해야 합니다.

향후 개선 사항

현재 대량 삽입은 트리의 효율적인 재구성과 밸런싱, 디스크에 대한 물리적 쓰기 감소를 통해 기존의 단일 항목 삽입에 비해 훨씬 더 나은 성능과 파일 크기를 제공합니다. 구현에서는 종종 노드를 조회하여 바운딩 박스를 가져와야 하는데, 그 외의 다른 항목(예: 자식)을 요청할 필요가 없습니다. 현재 데이터 구조(GeoCouch용으로 작성된 최초의 코드 조각)를 변경하면 조회 횟수가 훨씬 더 줄어들 수 있습니다.