[번역] Anti-Caching: A New Approach to Database Management System Architecture

Anti-Caching: A New Approach to Database Management System Architecture

Justin DeBrabant, Andrew Pavlo, Stephen Tu
원문

ABSTRACT

디스크 기반 관계형 데이터베이스 관리 시스템(DBMS)을 구축하는 전통적인 방법은 메인 메모리 블록 캐시와 함께 디스크에 저장된 고도로 인코딩된 블록으로 데이터를 구성하는 것입니다. 이러한 시스템은 높은 디스크 대기 시간을 고려하여 성능을 개선하기 위해 여러 트랜잭션이 동시에 데이터베이스에 액세스할 수 있는 동적 레코드 수준 잠금 기능을 갖춘 다중 스레드 아키텍처를 사용합니다. 이전 연구에 따르면 이로 인해 온라인 트랜잭션 처리(OLTP) 애플리케이션에 상당한 오버헤드가 발생하는 것으로 나타났습니다[15]. 차세대 DBMS는 메인 메모리 상주 데이터에 기반한 아키텍처를 통해 이러한 한계를 극복하고자 합니다. 모든 데이터가 메인 메모리에 들어맞는다는 제약을 극복하기 위해 데이터베이스의 크기가 커짐에 따라 트랜잭션에 안전한 방식으로 콜드 데이터를 디스크로 이동하는 안티캐싱이라는 새로운 기술을 제안합니다. 데이터는 처음에 메모리에 상주하기 때문에 안티캐싱 아키텍처는 디스크 기반 시스템의 기존 스토리지 계층구조를 뒤집습니다. 이제 메인 메모리가 기본 저장 장치가 됩니다.
퓨어스토리지는 안티캐싱 제안의 프로토타입을 고성능 메인 메모리 OLTP DBMS에 구현하고 다양한 데이터베이스 크기, 워크로드 스큐, 읽기/쓰기 혼합에 대해 일련의 실험을 수행했습니다. 분산형 메인 메모리 캐시가 선택적으로 제공되는 오픈 소스 디스크 기반 DBMS와 성능을 비교했습니다. 그 결과, 왜곡이 심한 워크로드의 경우 안티캐싱 아키텍처가 메모리보다 8㎇ 큰 데이터 크기에 대해 최대 9㎇까지 테스트한 다른 아키텍처보다 성능 우위를 보였습니다.

1. INTRODUCTION

역사적으로 DBMS의 내부 아키텍처는 고도로 인코딩된 디스크 블록에 데이터를 저장하고 관리하는 것을 전제로 합니다. 대부분의 시스템에서는 시스템에서 특정 작업을 용이하게 하기 위해 각 디스크 블록의 시작 부분에 헤더가 있습니다. 예를 들어, 이 헤더는 일반적으로 블록 앞쪽에 튜플에 대한 방향 지정을 지원하기 위해 "line table"을 포함합니다. 이를 통해 DBMS는 인덱스 포인터를 변경할 필요 없이 블록을 재구성할 수 있습니다. 디스크 블록을 주 메모리로 읽을 때는 반드시 주 메모리 형식으로 변환해야 합니다.

DBMS는 빠른 액세스를 위해 메인 메모리에 블록의 버퍼 풀을 항상 유지합니다. 실행 중인 쿼리가 디스크 블록을 읽으려고 할 때 DBMS는 먼저 이 버퍼 풀에 블록이 이미 존재하는지 확인합니다. 그렇지 않은 경우, 필요한 블록을 위한 공간을 확보하기 위해 블록이 제거됩니다. 블록을 메인 메모리에 고정해야 하고 시스템이 퇴출 순서 정책(예: 가장 최근에 사용된 블록)을 유지해야 하므로 버퍼 풀을 관리하는 데 상당한 오버헤드가 발생합니다. 15]에서 언급했듯이, 모든 데이터가 메인 메모리에 들어갈 때 버퍼 풀을 유지하는 데 드는 비용은 DBMS가 사용하는 모든 CPU 사이클의 거의 1/3에 달합니다.

디스크 상주 데이터를 관리하는 데 드는 비용 때문에 전체 데이터베이스를 메인 메모리에 저장하여 버퍼 풀이 없는 새로운 종류의 DBMS가 등장했습니다[11]. TimesTen은 이 접근 방식을 초기에 지지했으며[31], 최근의 예로는 H-Store[2, 18], MemSQL[3], RAMCloud[25] 등이 있습니다. H-Store(및 상용 버전인 VoltDB[4])는 이러한 메인 메모리 지향성뿐만 아니라 동시성 제어 및 대용량 데이터 로깅의 오버헤드를 피할 수 있기 때문에 표준 OLTP 벤치마크[29]에서 디스크 기반 DBMS보다 훨씬 우수한 성능을 보였습니다[22].

그러나 주 메모리 DBMS의 근본적인 문제점은 데이터베이스가 시스템에서 사용 가능한 물리적 메모리의 양보다 작은 경우에만 이러한 성능 향상을 달성할 수 있다는 것입니다. 데이터베이스가 메모리에 맞지 않으면 운영 체제가 가상 메모리를 페이징하기 시작하고 주 메모리 액세스로 인해 페이지 오류가 발생합니다. 페이지 오류는 사용자(이 경우 주 메모리 DBMS)에게 투명하게 표시되므로 디스크에서 페이지를 가져오는 동안 트랜잭션 실행이 중단됩니다. 이는 H-Store와 같이 강력한 잠금 및 래칭을 사용하지 않고 트랜잭션을 순차적으로 실행하는 DBMS에서 중요한 문제입니다. 이 때문에 모든 주 메모리 DBMS는 사용자에게 실제 메모리 양을 초과하지 않도록 경고합니다[5]. 메모리가 초과되는 경우(또는 향후 어느 시점에 초과될 가능성이 있는 경우) 사용자는 (1) 새 하드웨어를 프로비저닝하고 데이터베이스를 더 큰 클러스터로 마이그레이션하거나 (2) 성능 문제가 내재된 기존 디스크 기반 시스템으로 되돌아가야 합니다.

널리 채택된 성능 향상 방법 중 하나는Memcached[14]와 같은 메인 메모리 분산 캐시를 디스크 기반 DBMS 앞에 사용하는 것입니다. 이 2계층 아키텍처에서는 애플리케이션이 먼저 캐시에서 관심 있는 튜플을 찾습니다. 이 튜플이 캐시에 없는 경우 애플리케이션은 DBMS에서 쿼리를 실행하여 원하는 데이터를 가져옵니다. 애플리케이션이 DBMS에서 이 데이터를 받으면 향후 빠른 액세스를 위해 캐시를 업데이트합니다. 데이터베이스에서 튜플이 수정될 때마다 애플리케이션은 캐시 항목을 무효화해야 다음에 액세스할 때 애플리케이션이 DBMS에서 현재 버전을 검색할 수 있습니다. Facebook과 같은 많은 유명 웹사이트는 샤드된 MySQL 설치 앞에 대규모 Memcached 노드 클러스터를 사용합니다.

Figure 1: DBMS 아키텍처 - (a) 및 (b)에서 디스크는 데이터베이스의 기본 스토리지이며 데이터는 필요할 때 주 메모리로 가져옵니다. (c)에 표시된 안티캐싱 모델에서는 메모리가 기본 스토리지가 되고 콜드 데이터는 디스크로 이동합니다.

이 2계층 모델에는 두 가지 문제가 있습니다. 첫째, 데이터 개체가 캐시(주 메모리 형식)와 DBMS 버퍼 풀(디스크 형식)에 모두 존재할 수 있습니다. 이러한 데이터의 이중 버퍼링은 리소스 낭비입니다. 두 번째 문제는 개발자가 애플리케이션에 로직을 삽입하여 두 시스템을 독립적으로 동기화해야 한다는 것입니다. 예를 들어, 객체가 수정되면 업데이트가 백엔드 DBMS로 전송됩니다. 하지만 이제 DBMS와 캐시에 있는 객체의 상태가 달라집니다. 애플리케이션에 최신 값이 필요한 경우 애플리케이션은 캐시에 있는 오브젝트도 업데이트해야 합니다.

이러한 문제를 극복하기 위해 우리는 안티캐싱이라고 하는 새로운 메인 메모리 DBMS 아키텍처를 제시합니다. 안티캐싱이 적용된 DBMS에서는 메모리가 고갈되면 DBMS가 "coldest" 튜플을 수집하여 주 메모리 형식에서 최소한의 변환을 거쳐 디스크에 기록하므로 최근에 액세스한 튜플을 위한 공간을 확보할 수 있습니다. 따라서 "hotter" 데이터는 메인 메모리에 상주하고, 더 차가운 데이터는 시스템의 안티 캐시 부분에 있는 디스크에 상주합니다. 기존 DBMS 아키텍처와 달리, 각 튜플은 메모리 또는 디스크 블록 중 하나에 상주하지만 동시에 두 곳에 모두 상주하지는 않습니다. 이 새로운 아키텍처에서는 디스크가 아닌 메인 메모리가 기본 저장 위치가 됩니다. 디스크의 데이터로 시작하여 핫 데이터를 캐시로 읽는 대신, 데이터는 메모리에서 시작하고 콜드 데이터는 디스크의 안티 캐시로 내보냅니다.

이 접근 방식은 운영 체제(OS)의 가상 메모리 스와핑과 유사합니다. 가상 메모리를 사용하면 데이터의 양이 사용 가능한 메모리 양을 초과하면 콜드 데이터가 일반적으로 가장 최근에 사용한(LRU) 순서대로 페이지 단위로 디스크에 기록됩니다. 퇴거된 페이지에 액세스하면 해당 페이지가 다시 읽혀져 다른 페이지가 퇴거될 수 있습니다. 이렇게 하면 가상 메모리의 양이 프로세스에 할당된 물리적 메모리의 양을 초과할 수 있습니다. 마찬가지로 안티캐싱은 콜드 데이터를 블록 단위로 디스크로 내보냄으로써 데이터 양이 사용 가능한 메모리를 초과할 수 있도록 합니다. 데이터 액세스가 왜곡되면 작업 세트는 주 메모리에 남아 있습니다.

안티캐싱을 사용하면 필요에 따라 데이터를 읽고 쓰는 것은 DBMS의 책임입니다. 다른 대안은 가상 메모리 시스템이 디스크와 데이터를 주고받는 페이징을 수행하도록 하는 것입니다. 실제로 이것은 [28]에서 취한 접근 방식입니다. 그러나 안티캐싱은 메인 메모리 DBMS의 맥락에서 가상 메모리에 비해 몇 가지 장점이 있습니다. 특히, 디스크로 퇴거되는 데이터를 세밀하게 제어할 수 있고 디스크에서 퇴거된 데이터의 읽기를 차단하지 않습니다. 이 두 가지 주요 차이점은 아래에 자세히 설명되어 있습니다:

Fine-Grained Eviction (세분화된 퇴거): 메인 메모리 DBMS의 맥락에서 가상 메모리에 비해 안티캐싱의 주요 장점은 데이터를 퇴출할 수 있는 세분성입니다. 안티캐싱에서는 퇴출 결정이 튜플 수준에서 수행됩니다. 즉, 가장 콜드한 튜플이 디스크에 기록됩니다. 가상 메모리에서는 OS가 페이지 수준에서 퇴거 결정을 내립니다. 가상 메모리 페이지는 일반적인 OLTP 튜플보다 훨씬 클 가능성이 높습니다. 따라서 퇴거를 위해 선택된 각 페이지에는 여러 개의 튜플이 포함되며, 각 튜플은 잠재적으로 다양한 수준의 콜드 상태를 갖습니다. 페이지에 핫 튜플이 하나만 있으면 다른 튜플이 콜드 상태일지라도 전체 페이지가 핫 상태가 되어 메모리에 유지됩니다. 따라서 데이터에 액세스하는 것과 동일한 수준의 세분성(DBMS에서는 튜플 수준)에서 퇴출을 수행하는 것이 가장 좋습니다. 안티캐싱은 콜드 튜플로만 페이지를 구축하여 퇴거된 데이터를 보다 세밀하게 제어할 수 있는 방법을 제공합니다.

Non-Blocking Fetches: 또 다른 차이점은 필요할 때 퇴거된 데이터를 검색하는 방식입니다. 가상 메모리 시스템에서 OS는 디스크에 있는 메모리 주소를 읽다가 페이지 오류가 발생하면 프로세스를 차단합니다. 특정 DBMS[29, 34]의 경우, 이는 가상 메모리 페이지를 디스크에서 가져오는 동안 트랜잭션이 실행되지 않음을 의미합니다. 안티캐싱 DBMS에서는 퇴거된 데이터에 액세스하는 트랜잭션이 중단되었다가 나중에 필요한 데이터가 디스크에서 검색되면 다시 시작됩니다. 그 동안 DBMS는 다른 트랜잭션을 차단하지 않고 계속 실행합니다. 마지막으로, 모든 페이지 오류는 디스크 읽기를 트리거하기 때문에, 퇴거된 여러 페이지에 액세스하는 쿼리는 순차적으로 여러 번 페이지 오류를 발생시킵니다. 대신 트랜잭션에 필요한 모든 퇴거된 블록을 식별하려고 시도하는 사전 패스 실행 단계를 사용하여 모든 블록을 함께 읽을 수 있도록 합니다[23].

이 논문에서는 안티캐싱 제안의 세부 사항을 살펴봅니다. 우리는 H-Store DBMS [2]에서 프로토타입을 구현하고 세 가지의 서로 다른 그림 1에 표시된 세 가지 DBMS 아키텍처에 대한 철저한 실험 평가를 수행했습니다:
1. 기존 디스크 기반 DBMS(MySQL).
2. 분산 캐시 프론트엔드가 있는 기존 디스크 기반 DBMS(MySQL + Memcached).
3. 메인 메모리 DBMS(H-Store)의 안티캐싱.

이 실험의 결과는 안티 캐시 아키텍처가 널리 사용되는 OLTP 워크로드에서 기존 디스크 기반 아키텍처와 하이브리드 아키텍처보다 성능이 뛰어나다는 것을 보여줍니다. 이러한 차이는 기울기(skew) 수준이 높을수록 더욱 뚜렷하게 나타나며, 안티캐싱 아키텍처를 중심으로 설계된 메인 메모리 데이터베이스는 사용 가능한 메인 메모리보다 훨씬 더 큰 규모로 확장하면서도 처리량 저하를 거의 경험하지 않을 수 있음을 보여줍니다.

Figure 2: H-Store 메인 메모리 OLTP 시스템

안티 캐시 설계는 두 가지 주요 가정을 기반으로 합니다. 가장 중요한 것은 현재 프로토타입이 쿼리 범위를 주 메모리에 맞도록 제한한다는 것입니다. OLTP 워크로드에서 이러한 대용량 쿼리는 흔하지 않기 때문에 이 점이 큰 장애가 된다고 생각하지 않습니다. 다른 설계 가정은 모든 인덱스가 메모리에 맞는다는 것입니다. 대규모 보조 인덱스 사용의 장단점은 데이터베이스 최적화 분야에서 잘 연구된 주제이며, 이 요구 사항이 지나치게 제한적이라고 생각하지 않습니다. 저희는 보조 인덱스를 메모리에 보관할 필요성을 없애기 위한 대체 설계를 제안합니다.

2. H-STORE SYSTEM OVERVIEW

안티캐싱 모델의 세부 사항을 논의하기 전에 먼저 H-Store의 아키텍처와 그 설계 동기를 살펴보겠습니다. 디스크 지향 DBMS에서 시스템은 트랜잭션이 요청할 때 디스크의 블록에서 튜플을 검색합니다. 이러한 블록은 인메모리 버퍼 풀에 저장됩니다. 트랜잭션이 메모리에 없는 데이터에 액세스하는 쿼리를 호출하면 DBMS는 해당 데이터가 포함된 블록이 디스크에서 검색되어 버퍼 풀에 추가될 때까지 해당 트랜잭션을 일시 중단합니다. 버퍼 풀이 가득 차면 DBMS는 들어오는 블록을 위한 공간을 확보하기 위해 다른 블록을 선택하여 퇴출합니다. 트랜잭션은 이 디스크 작업이 완료될 때까지 대기하므로 이러한 시스템에서는 동시성 제어 체계를 사용하여 대기 중인 트랜잭션이 디스크를 기다리는 동안 다른 트랜잭션이 실행될 수 있도록 합니다. 이러한 데이터 이동과 동시 트랜잭션 간의 조정으로 인한 오버헤드는 상당한 것으로 나타났습니다[15].

이 DBMS 아키텍처는 전체 데이터베이스를 메모리에 저장할 수 있는 충분한 RAM이 없거나 엄청나게 비싼 컴퓨팅 노드가 존재하지 않을 때 적합했습니다. 그러나 최신 분산형 DBMS는 가장 큰 OLTP 데이터베이스를 제외한 모든 데이터베이스를 전체 메모리에 저장할 수 있습니다[29].

이러한 관찰 결과에 따라, H-Store는 메인 메모리 전용 노드에서 OLTP 워크로드를 효율적으로 실행하도록 설계되었습니다[18, 29]. 그림 2에서 볼 수 있듯이, H-Store 노드는 하나 이상의 파티션을 관리하는 단일 물리적 컴퓨터 시스템입니다. 파티션은 데이터의 분리된 부분 집합입니다[26]. 각 파티션에는 해당 노드에 해당 파티션에 대한 트랜잭션 및 쿼리 실행을 담당하는 단일 스레드 실행 엔진이 할당됩니다.

H-Store는 애드혹 쿼리를 지원하지만, 주로 트랜잭션을 저장 프로시저로 실행하는 데 최적화되어 있습니다. 이 백서에서는 트랜잭션이라는 용어를 저장 프로시저의 호출을 지칭하는 데 사용합니다. 저장 프로시저는 전적으로 데이터 노드에서 실행되므로 클라이언트와 데이터베이스 간의 왕복 횟수를 줄여주므로OLTP 애플리케이션을 최적화하는 효과적인 방법입니다. 저장 프로시저에는 사전 정의된 매개변수화된 SQL 명령을 호출하는 제어 코드(즉, 애플리케이션 로직)가 포함되어 있습니다. 클라이언트 애플리케이션은 클러스터의 모든 노드에 요청을 전송하여 트랜잭션을 시작합니다. 각 트랜잭션 요청에는 저장 프로시저의 이름과 해당 프로시저의 제어 코드에 대한 입력 매개변수가 포함됩니다. H-Store는 다음과 같은 구성의 트랜잭션 워크로드를 가정합니다:

Single-Partition Transactions (단일 파티션 트랜잭션): 이 경우, 대부분의 트랜잭션이 단일 노드에 로컬인 방식으로 각 테이블의 다양한 파티션을 노드에 할당하는 데이터베이스 설계가 있습니다[26]. 은행 계좌 잔액 조회 또는 구매 주문은 단일 파티션 트랜잭션의 예입니다. 단일 파티션 트랜잭션은 사용자 공간 HStore 클라이언트 라이브러리에서 검사되며, 여기서 매개 변수가 대체되어 실행 가능한 트랜잭션이 형성됩니다. 사용자 레벨 라이브러리는 H-Store의 분할 방식[26]을 알고 있기 때문에 트랜잭션이 처음부터 끝까지 차단 없이 실행되는 올바른 노드로 전송될 수 있습니다. 따라서 단일 파티션 트랜잭션은 각 노드에서 직렬화되며, 단일 파티션 트랜잭션으로만 구성된 모든 애플리케이션은 최대 병렬성을 얻을 수 있습니다.

Multi-Partition Transactions (다중 파티션 트랜잭션): 이 트랜잭션들은 여러 단계로 구성되며, 각 단계는 다음 단계가 시작되기 전에 완료되어야 합니다. 또한 하나 이상의 단계가 여러 파티션에 영향을 미칩니다.

각 H-Store 트랜잭션에는 시스템에 도착한 시간을 기준으로 고유한 트랜잭션 ID가 부여됩니다. 표준 클럭 스큐 알고리즘은 다양한 CPU 클럭을 동기화하기 위해 사용됩니다. 만약 더 높은 트랜잭션 ID를 가진 트랜잭션이 이미 애노드에 도착했다면 들어오는 트랜잭션은 거부됩니다. 이러한 방식으로 트랜잭션은 교착 상태를 감지할 필요 없이 다양한 노드에서 타임스탬프 순서대로 동기화됩니다. 다중 파티션 트랜잭션은 이 프로토콜의 확장을 사용하는데, 각 로컬 실행자는 다중 파티션 트랜잭션이 실행을 완료할 때까지 다른 트랜잭션을 실행할 수 없습니다. 이 방식은 단일 파티션 트랜잭션이 우세한 워크로드에 우수한 처리량을 제공합니다.

데이터베이스에 대한 모든 수정 사항이 내구성과 지속성을 갖도록 하기 위해 각 DBMS 노드는 전체 데이터베이스의 비동기 스냅샷을 고정된 간격으로 디스크에 지속적으로 씁니다[21, 29]. 이러한 스냅샷 사이에 DBMS는 성공적으로 완료된 각 트랜잭션에 대해 명령 로그에 레코드를 기록합니다[22]. DBMS는 여러 레코드를 함께 결합하고 그룹으로 기록하여 디스크에 쓰는 비용을 상각 (상환? amortize)합니다[16, 34]. 트랜잭션에 의해 수행된 모든 수정 사항은 이 레코드가 기록될 때까지 애플리케이션에 표시되지 않습니다. 이 레코드는 클라이언트가 보낸 원본 요청 정보만 포함하므로 레코드 수준 로깅보다 더 가볍습니다[22].

3. ANTI-CACHING SYSTEM MODEL

이 아키텍처는 기존 DBMS 버퍼 풀 접근 방식과 반대되는 아키텍처이기 때문에 안티캐싱이라고 부릅니다. 데이터베이스의 크기가 주 메모리의 크기를 초과할 때 디스크는 콜드 튜플을 유출하는 장소로 사용됩니다. 앞서 설명한 것처럼 일반 캐싱과 달리 튜플은 복사되지 않습니다. 메인 메모리 또는 디스크 기반 안티 캐시에 존재합니다.

런타임의 DBMS는 데이터베이스가 사용하는 메인 메모리의 양을 모니터링합니다. 노드에서 사용 가능한 메모리 양과 관련된 데이터베이스의 크기가 관리자가 정의한 임계값을 초과하면 DBMS는 새 데이터를 위한 공간을 확보하기 위해 콜드 데이터를 안티캐시로 '퇴출(evicts)'합니다. 이를 위해 DBMS는 데이터베이스에서 가장 최근에 사용된(LRU) 튜플을 포함하는 고정 크기 블록을 구성하고 해당 블록을 안티 캐시에 씁니다. 그런 다음 퇴출된 모든 튜플을 추적하는 메모리 상주 카탈로그를 업데이트합니다. 트랜잭션이 이러한 퇴거된 튜플 중 하나에 액세스하면 DBMS는 해당 트랜잭션을 'pre-pass' 모드로 전환하여 트랜잭션에 필요한 모든 튜플에 대해 학습합니다. 이 사전 통과가 완료되면 DBMS는 해당 트랜잭션을 중단하고(변경 사항을 롤백) 시스템이 백그라운드에서 튜플을 검색하는 동안 해당 트랜잭션을 보류합니다. 데이터가 인메모리 테이블로 다시 병합되면 트랜잭션이 해제되고 다시 시작됩니다.

Figure 3: 인메모리 EvictedTable과 디스크 상주 블록 테이블의 레이아웃을 논리적으로 표현한 그림입니다. 화살표는 블록에 있는 튜플의 정수 오프셋을 나타냅니다.

이제 안티캐시 구현의 기본 스토리지 아키텍처를 설명하겠습니다. 그런 다음 메모리에서 콜드 데이터를 제거하여 비휘발성 안티캐시에 저장하는 프로세스에 대해 설명한 다음, DBMS가 안티캐시에서 데이터를 검색하는 방법을 설명합니다. 안티캐시에 대한 DBMS의 모든 작업은 트랜잭션 방식으로 이루어지며 모든 변경 사항은 영구적이고 내구성 있게 유지됩니다.

3.1 Storage Architecture

각 파티션 내의 안티 캐시 스토리지 매니저에는 세 가지 구성 요소가 포함되어 있습니다: (1) 블록 테이블이라고 하는 퇴거된 튜플 블록을 저장하는 디스크 상주 해시 테이블, (2) 퇴거된 튜플을 블록 ID에 매핑하는 인메모리 퇴거 테이블, (3) 각 테이블에 대한 튜플의 인메모리LRU 체인입니다. H-Store의 모든 테이블 및 인덱스와 마찬가지로, 이러한 데이터 구조는 한 번에 하나의 트랜잭션만 액세스가 허용되므로 래치가 필요하지 않습니다.

튜플을 퇴출하는 주된 목적이 메모리를 확보하는 것이라는 점을 고려할 때 고려해야 할 절충점 중 하나는 이 bookkeeping의 스토리지 오버헤드입니다. 분명히 퇴거된 튜플을 추적하는 데 사용되는 메모리의 양은 튜플을 퇴거하여 얻은 테마 메모리의 극히 일부에 불과해야 합니다. 현재 구현에서는 데이터베이스의 모든 기본 키와 보조 인덱스가 메모리에 맞아야 합니다. 이 문제는 섹션 5.6에서 자세히 살펴보겠습니다.

Block Table: DBMS의 메인 메모리 저장소에서 퇴출된 튜플 블록을 유지하는 해시 테이블입니다. 각 블록은 동일한 고정 크기이며 4바이트의 고유 키가 할당됩니다. 블록의 헤더에는 해당 튜플이 퇴출된 싱글테이블의 식별자와 블록이 생성된 타임스탬프가 포함됩니다. 블록 본문에는 단일 테이블에서 직렬화된 퇴거된 튜플이 포함됩니다. 블록에 저장된 모든 튜플에는 크기가 접두사로 붙으며, 디스크 기반 스토리지용으로 특별히 설계된 형식이 아닌 인메모리 형식과 매우 유사한 형식으로 직렬화됩니다. 블록 테이블의 키 부분은 메모리에 유지되며, 블록 테이블의 값(즉, 블록 데이터)은 OS 또는 파일 시스템 캐싱 없이 디스크에 저장됩니다.

Evicted Table: 퇴거된 테이블은 디스크의 블록에 기록된 튜플을 추적합니다. 튜플이 퇴출되면 DBMS는 테이블을 위한 일반 저장 공간에서 제거하고 동적으로 구성된 블록에 추가한 다음 블록 테이블에 저장합니다. 블록에서 퇴거된 각 튜플에는 해당 튜플이 위치한 블록의 오프셋에 해당하는 4바이트 식별자가 할당됩니다. 퇴거된 튜플을 포함하는 모든 인덱스는 퇴거된 테이블을 참조하도록 DBMS가 업데이트합니다. 섹션 3.4에서 설명한 것처럼, 퇴거 테이블은 DBMS가 트랜잭션에 필요한 모든 퇴거된 튜플을 식별할 수 있도록 합니다.

Figure 4: 튜플 헤더에 포함된 LRU 체인의 물리적 표현. 각 튜플 헤더에는 비트 플래그(가장 왼쪽 상자)를 위한 1바이트와 링크된 목록에서 인접한 튜플의 4바이트 튜플 ID 두 개가 포함되어 있습니다.

LRU Chain: 마지막으로, H-Store는 각 테이블에 대한 모든 튜플의 인메모리 목록을 LRU 순서로 유지합니다. 이를 통해 DBMS는 런타임에 최근에 가장 적게 사용된 튜플을 신속하게 확인하여 새로운 블록으로 결합하여 퇴출할 수 있습니다. LRU 체인은 이중으로 연결된 목록으로, 각 튜플은 해당 테이블에서 가장 최근에 사용된 다음 및 이전 튜플을 가리킵니다. 튜플은 트랜잭션에 의해 액세스, 수정 또는 삽입될 때마다 체인의 후미에 추가되며, 튜플을 읽거나 업데이트하면 먼저 체인의 원래 할당에서 제거되어 후미에 삽입됩니다. 그런 다음 체인에서 이전에 해당 튜플에 인접했던 튜플이 서로 연결됩니다.

DBMS는 LRU 체인을 위한 별도의 데이터 구조를 유지하는 대신, 튜플의 헤더에 직접 포인터를 삽입합니다. 메모리 오버헤드를 줄이기 위해 각 튜플에 대한 포인터는 해당 파티션의 테이블 메모리에 있는 해당 레코드의 4바이트 오프셋(8바이트 주소 위치 대신)으로 설정됩니다.

각 테이블의 전체 주문을 추적하는 데 드는 CPU 오버헤드를 줄이기 위해 DBMS는 런타임에 모니터링할 트랜잭션의 일부를 선택합니다. 선택된 트랜잭션은 LRU 체인에서 데이터를 업데이트하는 데 사용됩니다. 핫 튜플은 정의상 더 자주 액세스되기 때문에 샘플링된 트랜잭션에서 액세스될 가능성이 더 높으며, 따라서 LRU 체인에서 업데이트될 가능성이 더 높습니다. 트랜잭션이 샘플링되는 속도는 매개변수 α에 의해 제어되며, 여기서 0 < α <= 1입니다. 샘플링의 영향과 다른 트레이드오프에 대해서는 5.4절에서 살펴보겠습니다.

또한 자주 액세스하는 테이블이 종종 있습니다. 디스크에서 퇴거되도록 허용해서는 안 됩니다(예: 소규모 조회 테이블). 이러한 테이블은 핫 테이블로 간주되므로, 이러한 테이블의 일부가 이러한 테이블의 일부가 디스크로 퇴거될 가능성은 거의 없습니다. 그래도 이러한 테이블에 대한 LRU 체인을 유지 관리하는 오버헤드가 추가됩니다. 이를 제거하려면 이를 제거하려면 스키마 생성 중에 테이블을 퇴거 가능한 것으로 스키마를 생성합니다. 퇴거 가능으로 레이블이 지정되지 않은 테이블은 LRU 체인을 유지하지 않고 주 메모리에만 남게 됩니다.

3.2 Block Eviction

이상적으로, 우리의 아키텍처는 시스템에서 튜플의 단일 글로벌 순서를 유지하여 핫 데이터와 콜드 데이터를 전체적으로 추적할 수 있습니다. 그러나 여러 파티션에 걸쳐 단일 체인을 유지하려면 파티션 간 통신 비용이 추가되기 때문에 비용이 엄청나게 비쌉니다. 대신, 저희 시스템은 파티션에 로컬인 테이블당 별도의 LRU 체인을 유지합니다. 따라서 데이터를 퇴출하기 위해 DBMS는 (1) 어떤 테이블에서 데이터를 퇴출할지, (2) 주어진 테이블에서 퇴출해야 하는 데이터의 양을 결정해야 합니다. 초기 구현에서 DBMS는 테이블에 대한 액세스의 상대적 왜곡을 통해 이러한 질문에 답합니다. 각 테이블에서 액세스한 데이터의 양을 모니터링하고 각 테이블에서 퇴거되는 데이터의 양은 마지막 퇴거 이후 테이블에서 액세스한 데이터의 양에 반비례하므로 테이블이 더 뜨거울수록 퇴거되는 데이터의 양이 줄어듭니다. 테스트한 벤치마크의 경우 이 접근 방식만으로도 충분하지만, 향후에는 더 정교한 방식을 고려할 예정입니다.

Figure 5: 트랜잭션 실행 상태 다이어그램 - 트랜잭션이 퇴출된 데이터에 액세스하는 경우 트랜잭션은 프리패스 실행에 들어가서 트랜잭션이 요청되기 전에 데이터를 가져와 병합합니다.

각 테이블에서 퇴출할 데이터의 양을 결정한 후, HStore는 퇴출할 튜플을 선택하고 디스크에 블록을 쓰는 특수 단일 파티션 트랜잭션을 실행합니다. 트랜잭션은 각 파티션에서 한 번에 하나씩 실행되므로, 이러한 퇴거 트랜잭션은 추가적인 잠금 메커니즘 없이도 대상 파티션의 다른 모든 트랜잭션을 자동으로 차단합니다.

퇴거 트랜잭션이 실행되면 대상 테이블의 LRU 체인 헤드에서 튜플을 popping 하여 새 블록을 생성합니다. 퇴거되는 각 튜플에 대해 H-Store는 해당 데이터를 퇴거 블록 버퍼에 복사합니다. 그런 다음 퇴거된 테이블에 항목을 추가하고 모든 인덱스가 원래의 튜플 위치 대신 이 항목을 가리키도록 업데이트합니다. 퇴거 테이블의 각 튜플에는 헤더에 특수 퇴거 플래그가 포함되어 있어 트랜잭션이 퇴거된 데이터에 액세스하는 시기를 DBMS가 인식할 수 있습니다. 이 퇴거 프로세스는 블록이 가득 찰 때까지 계속되며, 이 시점에서 트랜잭션은 다음 블록을 생성합니다. 트랜잭션이 각 테이블에서 필요한 양의 데이터를 퇴거하면 프로세스가 중지됩니다. 블록 그룹은 한 번의 순차적 쓰기로 기록됩니다. 예를 들어, 테이블에 n개의 블록 집합을 퇴거하라는 요청이 있는 경우, 테이블은 n개의 블록을 각각 독립적으로 생성하고, n개의 블록이 모두 생성된 경우에만 한 번의 순차 쓰기로 결과를 디스크에 기록합니다.

또한 퇴거 프로세스 중에 데이터베이스의 상태가 일관된다는 점도 중요합니다. 인덱스가 업데이트되고 블록이 디스크에 기록되기 전에 원래 테이블에서 튜플이 제거되지만, 실행 엔진의 단일 스레드 특성으로 인해 특수 트랜잭션이 완료될 때까지 다른 트랜잭션이 이러한 변경 사항에 액세스할 수 없습니다. 다른 트랜잭션은 퇴거 요청된 전체 블록 세트가 디스크에 기록될 때까지 실행되지 않으며, 또한 이 프로세스 중 어느 시점에서도 DBMS가 충돌하더라도 데이터를 복구할 수 없습니다(3.6항 참조).

3.3 Transaction Execution

H-Store와 같은 주 메모리 DBMS는 데이터가 주 메모리에 있다고 가정하는 처리 알고리즘을 통해 성능 이점을 누릴 수 있습니다. 그러나 트랜잭션 중간에 디스크 읽기를 처리해야 하는 경우 모든 시스템의 속도가 느려집니다. 즉, 트랜잭션이 퇴거된 튜플에 액세스할 때마다 파티션에서 트랜잭션 실행이 지연되는 것을 방지해야 합니다. 이제 안티캐싱을 통해 이를 수행하는 방법을 설명하겠습니다.

쿼리는 인덱스 또는 순차적 조회(즉, 전체 테이블 스캔)를 통해 퇴거된 데이터에 액세스할 수 있습니다. 후자의 경우, DBMS는 전체 테이블을 메모리에 저장해야 하므로 사용 가능한 물리적 메모리를 초과할 수 있습니다. 이 문제는 섹션 6.1에서 설명합니다.

인덱스 조회 쿼리의 경우, 시스템은 대상 인덱스를 검색하여 쿼리의 술어와 일치하는 키를 찾습니다. 인덱스의 각 키는 일반 테이블 저장소 또는 퇴거된 테이블에 있는 튜플을 가리킵니다. 액세스된 튜플 중 퇴거된 튜플이 없는 경우 DBMS는 트랜잭션을 계속 진행하도록 허용합니다. 퇴거된 데이터가 필요한 경우, 트랜잭션은 필요한 데이터와 해당 데이터가 디스크에 존재하는 위치를 정확히 결정하기 위한 특수 단계로 들어갑니다.

Pre-pass Phase: 트랜잭션은 실행을 계속하기 위해 퇴거된 데이터가 필요한 경우 Pre-pass 단계로 들어갑니다. Pre-pass 단계의 목표는 트랜잭션이 액세스해야 하는 모든 퇴거된 데이터를 확인하여 함께 검색할 수 있도록 하는 것입니다. 이를 위해 트랜잭션은 정상적으로 실행되지만, DBMS가 액세스하는 각 튜플에 대해 퇴거 플래그를 확인하여 해당 튜플이 퇴거되었는지 여부를 확인하는 것은 예외입니다. 퇴거된 경우, DBMS는 퇴거된 튜플의 블록 ID와 오프셋을 블록 테이블에 기록합니다(그림 3 참조). Pre-pass 실행이 완료되면, DBMS는 트랜잭션이 모든 파티션에서 수행한 모든 변경 사항을 롤백한 다음 프리패스 단계에서 액세스를 시도한 퇴거된 튜플 식별자 목록과 함께 트랜잭션을 다시 큐에 넣습니다. 또한 Pre-pass 단계에서는 트랜잭션이 다시 대기열에 추가되기 전에 인메모리 튜플이 LRU 체인에서 업데이트되어 이러한 튜플이 퇴거될 가능성을 줄입니다. 이렇게 하면 퇴거된 데이터로 인해 트랜잭션이 여러 번 재시작될 가능성을 최소화할 수 있습니다.

트랜잭션을 중단하고 다시 시작하는 데 드는 오버헤드는 작지만 0은 아닙니다. 따라서 Pre-pass 단계에서 DBMS는 트랜잭션이 퇴거된 튜플을 만난 후에도 해당 트랜잭션이 계속 실행되도록 허용하여 트랜잭션에 필요한 모든 데이터를 식별하려고 시도합니다[23]. 이를 통해 DBMS는 요청을 일괄 처리하고 트랜잭션을 여러 번 재시작할 가능성을 최소화할 수 있습니다. 이와 대조적으로, 가상 메모리에서 페이지 오류가 발생하면 퇴거된 개별 페이지 액세스마다 실행이 중단됩니다[28].

일부 트랜잭션의 경우, DBMS가 단일 Pre-pass에서 필요한 모든 데이터를 검색할 수 없는 경우가 있습니다. 이는 동일한 트랜잭션에서 추가 튜플을 검색하기 위해 퇴거된 튜플의 인덱싱되지 않은 값이 필요한 경우 발생할 수 있습니다. 이 경우, 초기 Pre-pass 단계에서는 현재 퇴거된 데이터에 종속되지 않는 모든 퇴거된 데이터를 결정합니다. 이 데이터가 성공적으로 병합되고 트랜잭션이 다시 시작되면, 이 퇴거되지 않은 데이터를 사용하여 데이터 종속성을 해결하고 추가로 퇴거해야 할 데이터가 있는지 결정합니다. 그러나 경험상 이러한 시나리오는 드물다고 생각합니다. 보다 일반적인 액세스 패턴은 트랜잭션이 보조 인덱스에서 레코드의 키를 검색하는 것인데, 이 경우 인덱스가 항상 메모리에 남아 있기 때문에 DBMS는 여전히 Pre-pass 단계에서 트랜잭션을 실행할 수 있습니다.

다음으로 DBMS가 프리패스 중에 식별된 퇴거된 튜플을 검색하여 시스템의 인메모리 스토리지에 다시 병합하는 방법을 설명합니다.

3.4 Block Retrieval

퇴거된 튜플에 액세스하려는 트랜잭션을 중단한 후, DBMS는 두 단계에 걸쳐 블록 테이블에서 트랜잭션에 필요한 블록을 검색하도록 예약합니다. 먼저 시스템은 디스크에서 블록을 검색하기 위해 non-blocking 읽기를 실행합니다. 이 작업은 일반 트랜잭션이 해당 파티션에서 계속 실행되는 동안 별도의 스레드에서 수행됩니다. DBMS는 이렇게 검색된 블록을 쿼리에서 액세스할 수 없는 별도의 버퍼에 저장합니다. 이러한 블록 중 하나에서 퇴거된 튜플에 액세스를 시도하는 모든 트랜잭션은 데이터가 여전히 디스크에 있는 것처럼 중단됩니다.

요청된 블록이 검색되면 중단된 트랜잭션의 일정이 다시 조정됩니다. 트랜잭션이 시작되기 전에 DBMS는 'stop and copy' 작업을 수행하여 모든 트랜잭션을 해당 파티션에서 차단하고 퇴거되지 않은 튜플을 스테이징 버퍼에서 일반 테이블 스토리지로 다시 병합합니다. 그런 다음 퇴거된 테이블에서 이러한 검색된 튜플에 대한 모든 항목을 제거한 다음 실제 튜플을 가리키도록 테이블의 인덱스를 업데이트합니다.

이 단계에서 고려해야 할 핵심 문제는 검색된 블록에서 다시 인메모리 스토리지로 병합할 데이터의 양입니다. 예를 들어, DBMS는 최근에 검색된 블록의 모든 튜플을 병합할지, 아니면 처음에 블록을 검색하게 만든 이전 트랜잭션이 액세스를 시도한 튜플만 병합할지 선택할 수 있습니다. 이제 이 문제에 대한 두 가지 해결책을 살펴보겠습니다. 5.1절에서 이러한 접근법의 효율성과 성능을 비교하겠습니다.

Block-Merging: 가장 간단한 방법은 DBMS가 검색된 전체 블록을 다시 일반 테이블 스토리지로 병합하는 것입니다. 블록의 모든 튜플이 인메모리 테이블에 다시 삽입됩니다. 요청된 튜플은 테이블의 LRU 체인 뒤쪽에 배치됩니다. 반대로 보류 중인 트랜잭션에 필요하지 않은 튜플은 LRU 체인의 앞쪽(즉, 콜드 엔드)에 추가되며, 이는 다음 라운드에서 퇴거 대상으로 선택될 가능성이 높아진다는 것을 의미합니다. 이렇게 하면 블록을 퇴거시키지 않은 트랜잭션에 필요했던 튜플만 핫 블록이 되고, 나머지 블록은 여전히 콜드 블록으로 간주됩니다. DBMS가 블록에서 튜플을 병합한 후에는 퇴거된 테이블에서 해당 블록을 삭제할 수 있습니다.

특히 블록에서 하나의 튜플만 필요하고 다른 모든 튜플이 곧바로 재퇴거되는 경우, 퇴거되지 않은 블록의 모든 튜플을 병합하는 오버헤드가 상당할 수 있습니다. 최악의 경우, 원치 않는 튜플이 시스템에 들어왔다가 즉시 다시 퇴거되는 퇴거/재퇴거 사이클이 계속될 수 있습니다.

Tuple-Merging: 이러한 진동을 방지하려면 디스크에서 블록을 읽게 한 원인이 된 튜플만 병합하는 것이 대안이 될 수 있습니다. 디스크에서 블록이 검색되면 DBMS는 해당 블록에서 필요한 튜플만 추출한 다음(퇴거된 테이블에 저장된 오프셋에 따라) 해당 튜플만 다시 인메모리 테이블에 병합합니다. 원하는 튜플이 병합되면 가져온 블록은 디스크의 블록을 업데이트하지 않고 삭제됩니다. 이렇게 하면 튜플을 테이블에 다시 병합하고 인덱스를 업데이트하는 시간이 단축됩니다. 이제 메모리에 있는 버전과 디스크의 안티 캐시에 있는 오래된 버전, 두 가지 버전의 튜플이 존재하게 됩니다. 그러나 DBMS는 퇴거된 테이블에서 병합된 튜플을 제거하므로, 이후 이러한 튜플에 대한 모든 조회는 메모리 내 버전을 사용합니다. 이 블록을 다시 가져오면 이미 퇴거되지 않은 튜플의 오래된 항목은 무시됩니다.

시간이 지남에 따라 블록의 이러한 "holes"이 누적됩니다. 이는 각 블록에서 검색되는 유효한 데이터의 양이 줄어든다는 것을 의미합니다. 저희는 병합 과정에서 지연 블록 압축 알고리즘을 사용합니다. 이 압축은 블록 테이블에서 각 블록의 구멍 수를 추적하여 작동합니다. DBMS는 디스크에서 블록을 검색할 때 블록의 구멍 수가 임계값을 초과하는지 여부를 확인합니다. 임계값을 초과하면 DBMS는 블록 병합 전략과 마찬가지로 전체 블록을 다시 메모리로 병합합니다. 보다 정교한 접근 방식은 섹션 6.2에서 설명합니다.

3.5 Distributed Transactions

캐싱 방지 모델은 분산 트랜잭션도 지원합니다. H-Store는 분산 트랜잭션이 파티션 중 하나에서 퇴거된 튜플에 액세스하려고 시도할 때 단일 파티션 트랜잭션과 마찬가지로 "pre-pass" 모드로 전환합니다. 트랜잭션은 클러스터의 노드에서 필요한 모든 블록이 검색되었다는 알림을 받을 때까지 중단되고 재요청되지 않습니다. 시스템은 각 노드가 디스크에서 블록을 검색하는 데 걸리는 시간 동안 트랜잭션이 어느 파티션에서도 액세스한 인메모리 튜플이 퇴거되지 않도록 보장합니다.

3.6 Snapshots & Recovery

디스크 기반 시스템의 지속성과 내구성은 일반적으로 온디스크 데이터와 로깅의 조합을 통해 달성됩니다. 그러나 주 메모리 DBMS에서는 스냅샷 및 명령 로깅[22, 29]과 같은 다른 기술이 사용됩니다. 안티캐싱 기능이 있는 DBMS의 경우 3.1절에서 설명한 추가 데이터 구조도 스냅샷해야 한다는 점을 제외하면 이 점은 변하지 않습니다.

이를 위해 DBMS는 일반 테이블과 인덱스 데이터의 모든 내용과 퇴거된 테이블의 내용을 직렬화하여 디스크에 씁니다. 동시에 DBMS는 스냅샷이 시작될 때 존재했던 블록 테이블의 복사본도 디스크에 만듭니다. 스냅샷 중간에 퇴거는 허용되지 않으며, 충돌이 발생한 후 복구하기 위해 DBMS는 디스크에서 마지막 스냅샷을 로드합니다. 이렇게 하면 테이블, 인덱스, 차단 테이블 및 퇴거된 테이블이 충돌 전에 존재했던 대로 설정됩니다. 그런 다음 DBMS는 이 스냅샷이 생성된 후 생성된 명령 로그의 트랜잭션을 재생합니다. 이 프로세스를 통해 모든 안티캐싱 데이터는 영구적으로 유지되며, 충돌이 발생하더라도 시스템의 정확한 상태를 복구할 수 있습니다.

데이터 크기가 큰 경우 블록 테이블의 스냅샷을 만드는 데 엄청난 비용이 들 수 있습니다. 각 체크포인트마다 복사본을 만드는 대신, DBMS는 델타 스냅샷을 만듭니다. 블록 테이블의 블록 내 데이터는 업데이트되지 않기 때문에 DBMS는 마지막 스냅샷 이후 블록 테이블에서 어떤 블록이 추가 또는 제거되었는지 확인하기만 합니다. 이 기술은 각 스냅샷을 호출할 때마다 복사되는 데이터의 양을 크게 줄여줍니다.