안녕하세요. 카카오 분산기술셀에서 분산 스토리지, DBMS 등을 개발하고 있는 yanoo.kim(김연우)이라고 합니다.

여기에서는 카카오 사내 Object Storage인 MetaKage가 이용 중인 분산 Radix Tree 연산에 대해 이야기하고자 합니다.

수천 억 개의 파일과 Ordered Listing

Kage[1]는 원래 Meta가 없는 스토리지입니다. 그래서 SNS성 대규모 업로드/다운로드에도 Meta로 인한 성능 저하가 없었지요. 하지만 Kage에 복잡한 기능을 도입하려면, 파일에 대한 복잡한 정보와 여러 보조 정보를 기록할 Meta가 필요했습니다.

그래서 저희는 Meta를 도입하는 김에 Openstack Object Storage API[2]을 준수하여, 여러 오픈소스 서드파티 사용이 가능한 MetaKage를 만들려 했습니다.

하지만, 파일 개수가 문제였습니다. 저희는 WebScale의 Object Storage를 만들려 했습니다. Kage가 엄청나게 파일이 많은 만큼, MetaKage 역시 많은 것은 자명합니다.

실제로 이 예상은 맞아떨어져서, MetaKage가 서비스된 지 7년여 시간이 지난 현재 MetaKage에는 수천 억 개의 파일이 저장되어 있습니다. 한 파일의 정보가 1k라 했을때, 수백 테라 바이트의 용량이 필요한 규모입니다. 단일 저장소로는 성능으로도 용량으로 다루기 어렵지요.

그렇다면 분산 스토리지에 파일들을 저장해야 합니다.

LSMT(Log-Structured Merge Tree)와 Range Query

HBase와 Cassandra는 가장 널리 사용되는 분산 스토리지들입니다. 둘 다 Range Query 기능을 제공합니다. 그리고 이 Range Query 기능은 LSMT(Log-Structured Merge Tree)[3]를 기반으로 합니다.

Range Query: 일부 값이 상한과 하한 사이에 있는 모든 레코드를 검색하는 데이터베이스 작업

따라서 두 시스템의 Range Query를 이해하려면, LSMT를 이해해야 합니다.

LSMT는 삽입되는 데이터를 모아서 정렬 후 저장하는 식으로 동작합니다. 이렇게 정렬되어 저장된 테이블을 SSTable(Sorted Strings Table)이라고 합니다.

Range Scan은 이 모든 SSTable에서 Binary Search를 통해 Range를 특정하고, 해당 Range의 데이터를 모두 가져오는 일입니다. Get, Put, Delete 등의 연산이라면 Bloom Filter를 통해, 찾을 키-밸류를 소유한 SSTable만 추려서 조회함으로써 비용을 줄일 수 있겠지만, Range Scan은 그럴 수 없습니다. 따라서 짧은 Range Scan도 꽤 많은 CPU, IO 자원을 소모합니다[4].

Bloom Filter: 원소(Element)가 집합(Set) 에 속하는지 여부를 테스트하기 위해 사용되는 확률적 데이터 구조

Range Scan의 비용을 줄이고 싶으면, 여러 SSTable을 하나로 통합하는 Compaction 연산을 해줘야 합니다. 그런데 Compaction 연산은 CPU, IO 연산이 굉장히 비쌉니다.

요새는 NAND Flash가 용량이 커지며 병렬성이 늘어 Throughput 또한 같이 늘어난 만큼 IO 비용에 대한 부담은 줄일 수 있지만, CPU 부담은 그렇지 않아, LSMT는 CPU 자원을 크게 소모하는 자료구조가 되었습니다[5].

이 과정에서 발생하는 Hot Spot을 분산하기 위한 방법으로, Key에 Salt값을 Prefix로 붙여 파티셔닝을 시도하기도 합니다[6]. 이는 적절하고 좋은 방법이지만, 한번 지정한 Salt 범위를 수정하기도 힘들고, 클러스터 전체에 이루어지는 Range Query 부담을 줄일 수는 없습니다.

Salt: 해시 함수 단방향 암호화의 해킹 위험을 낮추기 위해 추가적으로 삽입되는 랜덤 데이터

분산 BTree

LSMT 이전에는 보통 Index하면 BTree였습니다. BTree는 갱신이 있을때 즉시 In-place Update를 통해 Tree를 수정합니다. 그래서 Random Write가 일어납니다.

그에 반해 LSMT는 삽입된 키들을 모아 정렬 후 한꺼번에 저장함으로써, Seuqntial Write가 일어납니다. Write 패턴은 LSMT가 좋습니다. 하지만, 즉시즉시 갱신하는 BTree가 Range Scan에 대해서는 이점을 갖습니다.

처음 저희는 이 점에 주목했습니다. Distributed Key-Value Storage는 Web Scale의 요구로 나타난 시스템으로, Random Write에 강합니다.

Web Scale: 대규모 환경에서 고품질의 서비스를 영속적으로 비즈니스의 요구사항에 맞춰 신속하고 안정적으로 IT 자원을 설계, 구축 및 관리하는 패턴으로, 대형 클라우드 서비스 제공업체들의 클라우드 운영 방식을 말함

따라서 Distributed Key-Value Storage에서, Key-Value를 Tree의 노드 삼아 구현한다면, LSMT 없이도 Ordered Listing을 제공할 수 있을 것 같았습니다.

하지만 여기에는 두가지 문제가 있습니다.

BTree는 Split 같은 SMO(Structure Modification Operations)에 대한 정합성 제공이 어렵습니다.
BTree의 Split은, 새로운 노드를 생성하고, 새 노드로 기존 노드의 Item을 이동시킨 후, 부모 노드에 새 노드의 링크를 추가하는 식으로 이루어집니다. 이렇게 Node 3개가 갱신되는데, 셋 전부 성공해야 합니다. 셋 중 하나라도 실패하면 BTree는 깨집니다. 하지만 분산 환경에서 이러한 Transactional Operation은 비용이 매우 비쌉니다.
둘째, Root Node가 병목이 됩니다.
Insert, Delete, Scan 모두 Root Node를 시작으로 조회가 이루어집니다. 그래서 Root Node는 다른 Node보다 월등히 많은 접근이 이루어집니다. 이에 따라 Root Node를 소유한 스토리지 장비는 I/O가 몰려 병목이 될 수 있습니다. 다른 경우라면 Cache를 이용할 수도 있지만, BTree에서 Cache를 잘못 사용했다간 Tree를 잘못 조회하거나 깨트릴 수도 있습니다.

저희는 위 두 문제를 해결한 새로운 Tree, 분산 Radix Tree를 구현하였습니다.

분산 Radix Tree

이 분산 Radix Tree는 용량이 매우 큰 Hash Table 위에 구축되는 자료구조입니다. 마치 LSMT나 다른 DBMS의 스토리지 시스템이 File System 위에 구축되듯이, Radix Tree는 Hash Table 위에 구축됩니다.

논리구조

위 그림은, 왼쪽의 Key들을 삽입했을때 구축되는 분산 Radix Tree의 논리적 구조입니다. 모든 Node는 하나의 Key-Value 아이템과 1:1 대응됩니다.

모든 Node의 Key는 해당 Node의 Prefix로 표현되지만, $라는 시스템 문자를 접미사로 갖습니다. 각각의 Node는 Child를 갖고 있으며, 자신의 Key + Child를 합친 이름으로 Child node를 갖거나, Data fiag를 통해 실제 Item이 존재함을 확인할 수 있습니다.

예) 탐색 /12345

정해진 시스템 문자인 $를 바탕으로 RootNode를 찾습니다.
루트 Node에서 Binary Search로 ‘/1’을 찾습니다.
Node의 Key인 ‘$’와 Child인 ‘/1’를 합쳐, $/1을 찾습니다
$/1 Node에서 Binray Search로 ‘2345’를 찾습니다.
Node의 Key인 ‘ $/1’와 Child인 ‘/2345’를 합쳐, ‘$ /12345’를 찾습니다
$/12345 Node에서 Binary Search로 Begin Range인 ‘/89’를 찾은 뒤, 그 뒤의 Child들을 순회합니다.

물리적 배치

위의 RadixTree가 실제 물리적으로 배치된다면, 위와 같은 모양새를 갖습니다. Sharding된 데이터노드(Datanode) A, B, C의 3대에 대해, 각 Key들은 Hash되어 Digest값에 따라 각 Datanode에 분산배치됩니다.

즉, 위에서 소개한 SCAN(/12345)에 대한 연산은 Tree에 대한 3번의 GET, 이후 Tree에서 찾아낸 /12345/89과 /1234567의 두 Key에 대해 원본을 각각 GET하여, 3+2=5 총 다섯 번 GET하는 식으로 발생합니다.

분산 RadixTree의 Split

BTree의 경우, 분산 환경에서 사용하기에는 Split 연산에서 Multi node 갱신에 대한 Atomicity 요구로 인해 여러가지 어려움이 있었습니다. 분산 Radix Tree는 이러한 어려움이 없기에, 분산환경에서 사용하기 쉽니다.

분산 Radix에서의 Split은 Node의 공간 부족 시에 발생합니다. Node는 정렬된 Child들의 Array로 구성되어있는데, 이 Array의 Byte size는 4k가 최대치라, 삽입을 계속할 경우 Split이 요구됩니다.

위 그림은 ‘$/foo’라는 노드가 Split하는 과정을 표현한 그림입니다.

$/foo에 cde를 삽입하려다, 공간 부족으로 실패합니다.
삽입할 공간 확보를 위해 Split을 시도합니다.
분산 Radix Tree의 Split은 Child Node를 새로 생성하고, 거기에 일부를 보내는 식으로 동작합니다. 이에 따라 Child Node인 $/fooc를 생성하고, 여기에 $/foo의 ‘ccc’와 새로 삽입할 ‘cde’를 보내며, 이 과정은 한번의 PUT으로 이루어집니다.
$/foo에서 Child Node로 넘어간 Child ‘ccc’를 삭제하고, 새롭게 Child Node를 가리키는 ‘c’를 넣어 PUT 합니다.

Split은 위와 같이 Backend에 두 번 PUT을 하는 것으로 완료됩니다.

이제 정합성을 따져봅시다.

Split을 이루는 두 번의 PUT은 딱히 별다른 Transactional 처리 없이 동작하기에, 2, 3번 둘다 성공하면 좋지만, 환경에 따라 2번만 성공한 채로 남을 수도 있습니다. Split이 되기 전인 1번 상태나, Split이 완료된 상태인 3번은 문제 없지만, 2번은 약간 위험해 보입니다.

일단 Scan 같은 조회 연산에서는 아무 문제 없습니다. Child Node가 Dangling Reference(허상 참조)가 되었을 뿐 Tree는 올바르기 때문이죠.

하지만 ‘/fooccc’라는 하나의 Key가, $/foo, $/fooc 두 개의 Child에 동시에 있는 상태이기에, 하나의 Key를 표현하는 노드가 둘이니까요. 이에 따라 두 노드가 각기 다른 상태를 표현하면서, 어떤 Client는 $/foocde를 읽는데, 다른 Client는 $/foocde를 못 읽는 상황도 벌어질 수 있습니다.

하지만 실제로는 이런일이 발생하지 않습니다. 왜냐하면 $/fooc 라는 Node에 대한 링크가 없기 때문입니다. 모든 탐색은 Root부터 시작되며, Root와의 연결이 끊긴 $/fooc는 읽으려 해도 존재를 모르기에 읽을 수 없습니다.

추가적으로 Scan 과정에서 Stack으로 구성된 Cursor를 이용해 Node가 끊어졌는지 확인하고 읽으며, 또 끊어졌으면 잘못 쓰여진 Child Node를 삭제하는 식으로 복구 로직이 돌아가게 됩니다.

Bloom Filter로 병목 제거하기

위와 같은 구현으로는 BTree와 동일하게 Root Node에 병목이 생긴다는 점은 동일합니다. 또 Root Node만이 아니라 상위 Internal Node 모두에 병목이 생깁니다.

그래서 저희는 Bloom Filter를 추가하여 이 문제를 해결하였습니다.

Bloom Filter는 Tree Traverse를 도와주기 위해 Node의 존재 여부를 표현하는 Hint입니다. 이 Hint는 각 분산 Radix Tree모듈의 Memory에 존재합니다. 그래서 아무리 접근해도 비용이 들지 않습니다.

그리고 Hint라서 정확하지 않아도 됩니다. 그래서 위 Bloom Filter의 예제를 보면, $/foo/abc Node에 대한 마킹이 되어 있지 않음을 보여주고 있습니다.

분산 Radix Tree가 동작하면서, Node의 존재를 확인할 때마다 분산 Radix Tree 로직은 Bloom Filter를 마킹하며, Bloom Filter를 구축합니다.

SCAN(/foo/abcd)를 했을 때의 예로 Bloom Filter의 기능을 설명하겠습니다.

Scan을 시작하면 먼저 탐색할 Key에 시스템 문자인 $를 붙여서, $/foo/abcd를 Bloom Filter에서 찾습니다. 뒷 글자를 하나씩 빼면서 탐색하여, 있을 때까지 찾습니다.

이 연산은 분산 Radix Tree 모듈 내의 메모리에 접근하여 확인하는 작업이라, 비용이 들지 않습니다. 그렇게 최종적으로 $/foo가 있다는걸 확인하면, Root Node($ )부터 시작할 필요 없이, 중간 노드인 $/foo부터 탐색할 수 있게 되었습니다. 이에 따라 Root의 접근 필요성이 없어졌고, Root에 대한 병목이 없어졌습니다.

또한, 이전 경우는 $/foo/abc가 Bloom Filter에 없었기에 $/foo부터 찾은 것일뿐, 다음 번 탐색 시에는 $/foo/abc의 존재가 Bloom Filter에 설정되기에, 다음부터는 $/foo/abc부터 탐색을 이어갈 것입니다.

마치며

이 분산 Radix Tree를 이용하는 Object Storage인 MetaKage는 2015년 개발되었습니다. 이후 자잘한 버그나 오류는 있었지만, 치명적인 오류 없이 수 십 TB에 이르는 수천 억 개의 파일들을 저장하며 서비스 중입니다.

Reference

[1]https://tech.kakao.com/2017/01/12/kage/

[2]https://docs.openstack.org/api-ref/object-store/

[3]O’Neil, Patrick, et al. “The log-structured merge-tree (LSM-tree).” Acta Informatica 33.4 (1996): 351-385.

[4]Zhong, Wenshao, et al. “{REMIX}: Efficient Range Query for {LSM-trees}.” 19th USENIX Conference on File and Storage Technologies (FAST 21). 2021.

[5]Lepers, Baptiste, et al. “Kvell: the design and implementation of a fast persistent key-value store.” Proceedings of the 27th ACM Symposium on Operating Systems Principles. 2019.

[6]https://sematext.com/blog/hbasewd-avoid-regionserver-hotspotting-despite-writing-records-with-sequential-keys/

Object Storage 구현을 위한 분산 Radix Tree