Authenticated Data Structures for Dynamic Workloads

디지털 세상에서 신뢰는 종종 단순한 약속, 즉 기록이 변경되지 않았다는 약속 위에 구축됩니다. 이 약속을 지키기 위해 시스템은 '커밋먼트(commitment)'라고 불리는 특별한 종류의 디지털 지문(fingerprint)을 사용합니다. 모든 책이 데이터의 한 조각인 거대한 도서관을 상상해 보십시오. 사로테는 전체 컬렉션을 요약하는 단 하나의 작은 노트를 가지고 있습니다. 만약 당신이 특정 책이 도서관에 있다는 것을 증명하고 싶다면, 건물 전체를 보여줄 필요 없이, 당신의 책에서 그 하나의 노트로 이어지는 짧은 단서의 경로만을 보여주면 됩니다. 이 시스템을 '인증된 데이터 구조(authenticated data structure)'라고 합니다. 이는 수백만 건의 트랜잭션을 전 세계의 모든 역사를 다운로드하지 않고도 빠르고 안전하게 검증해야 하는 블록체인과 같은 현대 기술의 중추 역할을 합니다.

하지만 현실 세계는 결코 완벽하게 균형 잡혀 있지 않습니다. 어떤 대규모 시스템에서는 일부 항목이 끊임없이 확인되는 반면, 다른 항목들은 몇 년 동안 무시되기도 합니다. 전통적인 디지털 도서관은 모든 항목을 동일하게 취급하여, 인기 있는 항목을 찾는 데나 잊혀진 항목을 찾는 데나 시스템이 똑같이 길고 구불구불한 경로를 거치도록 강제합니다. 이러한 비효율성은 병목 현상을 일으켜 전체 네트워크의 속도를 늦추고 에너지를 낭비하게 만듭니다. 연구자들이 오랫동안 직면해 온 질문은, 이러한 디지털 구조가 보안 규칙을 깨뜨리거나 패턴이 바뀔 때마다 완전히 재구축할 필요 없이, 사람들이 실제로 필요로 하는 것들에 대해 더 빨라질 수 있도록 사용 패턴에 적응할 수 있는지 여부였습니다.

한 연구팀은 변화하는 작업 부하를 놀라운 효율성으로 처리하도록 설계된 '허프만-머클 트리(Huffman-Merkle Tree)'라는 새로운 솔루션을 도입했습니다. 모든 데이터를 하나의 경직된 구조에 밀어 넣는 대신, 그들은 사용 빈도에 따라 데이터를 두 개의 뚜렷한 구역으로 분리했습니다. 가장 자주 액세스되는 항목인 '핫(hot)' 데이터는 특화되고 조밀한 배치 속에 배치되어 상단에 가깝게 위치함으로써 접근하기 쉽게 만들었습니다. 덜 인기 있는 '콜드(cold)' 항목들은 표준적이고 질서 정연한 구조에 그대로 남겨두었습니다. 이러한 분리는 흔치 않은 항목을 관리하는 비용은 낮게 유지하면서, 가장 흔한 작업에 대한 성능을 최적화할 수 있게 해줍니다.

이 접근 방식의 탁월함은 데이터가 두 구역 사이를 이동하는 방식을 관리하는 데 있습니다. 과거에는 디지털 구조를 새로운 사용 패턴에 적응시키기 위해 전체를 허물고 처음부터 다시 구축해야 하는 경우가 많았는데, 이는 느리고 비용이 많이 드는 과정이었습니다. 새로운 시스템은 사용량을 추적하는 영리한 방법을 사용하여 이를 피합니다. 시스템은 모든 데이터 조각에 대해 완벽하고 무거운 기록을 유지하는 대신, 항목이 얼마나 자주 액세스되었는지에 대한 가볍고 근사적인 수치를 유지합니다. 시스템이 특정 항목을 '핫' 구역으로 이동시킬 만큼 인기가 높아졌다고 판단할 때, 즉시 전체 라이브러리를 재배열하지 않습니다. 대신, 변경 사항이 일정량 축적될 때까지 기다린 다음, 레이아웃을 조정하기 위해 일련의 작고 표적화된 교환(swaps)을 수행합니다. 이는 시스템이 대규모의 재구축 오버헤드 없이도 변화하는 습관에 적응할 수 있음을 의미합니다.

아이디어를 테스트하기 위해 연구진은 실제 수백만 건의 트랜잭션에서 추출한 실제 세계의 데이터를 처리하며, 현재 주요 블록체인 네트워크에서 사용되는 표준들과 새로운 시스템을 비교 실험했습니다. 그들은 두 가지 중요한 요소, 즉 시스템을 업데이트하는 데 필요한 계산 작업량과 단일 항목을 검증하기 위한 멤버십 증명(proof of membership)의 크기를 측정했습니다. 결과는 놀라웠습니다. 새로운 시스템은 업데이트에 훨씬 적은 작업을 요구했으며, 기존의 선도적인 방식보다 약 2.5배 적은 계산 단계를 사용했습니다. 동시에, 가장 흔한 항목을 검증하는 데 필요한 증명의 크기는 현재의 표준과 비교했을 때 거의 절반 가까이 줄어들었습니다. 이러한 크기와 작업량의 감소는 이 구조에 의존하는 네트워크의 속도를 높이고 비용을 낮추는 것으로 직결됩니다.

연구진은 또한 아이템을 콜드 존에서 핫 존으로 이동시키기로 결정하는 다양한 전략들을 탐구했습니다. 그들은 최근의 활동, 즉 지난 수천 블록의 트랜잭션 동안 발생한 일에 집중하는 방법이 가장 좋은 성능을 보인다는 것을 발견했습니다. 이 접근 방식은 특정 디지털 자산에 대한 활동 급증과 같은 사용자 행동의 갑작스러운 변화에 빠르게 반응할 수 있게 하면서도, 오래되고 무관한 데이터는 무시할 수 있게 해주었습니다. 전체 사용 이력을 살펴보는 또 다른 전략은 더 안정적이었지만 적응 속도가 느렸습니다. 피드백을 바탕으로 규칙을 자동 조정하려는 더 복able한 세 번째 방법은 유망해 보였으나, 이를 관리하기 위해 더 많은 계산 노력이 필요했습니다. 이 연구는 최선의 접근 방식이 네트워크의 구체적인 요구 사항에 달려 있음을 시示하지만, 핫 데이터와 콜드 데이터를 분리하는 핵심 설계가 실제 사용의 역동적인 특성을 다루는 강력한 방법임을 입증했습니다.

데이터의 보안을 레이아웃의 최적화로부터 분리함으로써, 이 새로운 구조는 무결성을 희생하지 않으면서 디지털 장부의 효율성을 높이는 방법을 제시합니다. 이는 살아있는 시스템에서는 어떤 것들이 다른 것들보다 더 중요하다는 점을 인정하며, 우리가 이를 관리하기 위해 사용하는 도구 역시 그 현실을 반영해야 한다는 점을 시사합니다. 연구 결과는 데이터를 균일한 형태에 강제로 맞추는 대신 사용 방식에 따라 조직하는 것만으로도 상당한 성능 향상을 달할 수 있음을 보여줍니다. 이것은 이론적인 연습이 아닙니다. 현재 사용 중인 가장 크고 복잡한 데이터 세트를 대상으로 측정한 실질적인 개선이며, 더 스마트한 배치가 우리의 디지털 인프라가 작동하는 방식에 얼마나 심오한 차이를 만들 수 있는지를 보여줍니다.