MonetDB Architecture

모네 데이터베이스 모델

아래 논문참고함.

MonetDB: Two Decades of Research in Column-oriented Database Architectures 

1. Physical Data Model

컬럼 저장방식. 각각의 컬럼을 BAT 이라는 테이블에 저장한다. 

MonetDB uses the operating system’s memory mapped files support to load data in main memory and 2

exploit extended virtual memory. Thus, all data structures are represented in the same binary format on disk and in memory. Furthermore, MonetDB uses late tuple reconstruction, i.e., during the entire query evaluation all intermediate results are in a column format. Only just before sending the final result to the client, N-ary tuples are constructed. This approach allows the query engine to exploit CPU- and cache-optimized vector-like operator implementations throughout the whole query evaluation relying on a bulk processing model as opposed to the typical Volcano approach, allowing to minimize function calls, type casting, various metadata handling costs, etc. Intermediate results need to be materialized, but those can be reused [12]. 

2. Execution Model

모네디비의 커널은 추상화 머신이다. Monetdb Assembly Language

3. System Architecture

MonetDB’s query processing scheme is centered around three software layers. 

Front-end

The top layer or front-end provides the user-level data model and query language. While relational tables with SQL and XML with XQuery [1] are readily available, arrays with SciQL [14] and RDF with SPARQL are on our research and development agenda. The front-end’s task is to map the user-space data model to MonetDB’s BATs and to translate the user-space query language to MAL. The query language is first parsed into an internal representation (e.g., SQL into relational algebra), which is then optimized using domain-specific rules. In general, these domain-specific strategic optimizations aim primarily at reducing the amount of data to be processed, i.e., the size of intermediate results. In the case of SQL & relational algebra, such optimizations include heuristics like pushing down selections and exploiting join indexes. The optimized logical plan is then translated into MAL and handed over to the back-end for general MAL-optimization and evaluation. 

Back-end

The middle layer or back-end consists of the MAL optimizers framework and the MAL interpreter as textual interface to the kernel. The MAL optimizers framework consists of a collection of optimizer modules that each transform a given MAL program into a more efficient one, possibly adding resource management directives. The modules provide facilities ranging from symbolic processing up to just-in-time data distribution and execution. This tactical optimization is more inspired by programming language optimization than by classical database query optimization. It breaks with the hitherto omnipresent cost-based optimizers, recognizing that not all decisions can be cast together in a single cost formula. Operating on the common binary-relational back-end algebra, these optimizer modules are shared by all front-end data models and query languages.

중간 계층 또는 백엔드는 커널에 대한 텍스트 인터페이스로서 MAL 최적화자 프레임워크와 MAL 해석기로 구성된다. MAL 최적화자 프레임워크는 각각 주어진 MAL 프로그램을 보다 효율적인 프로그램으로 변환하여 자원 관리 지침을 추가하는 최적화자 모듈의 모음으로 구성된다. 이 모듈들은 상징적 처리에서부터 적시적 데이터 배포와 실행에 이르는 다양한 설비를 제공한다. 이 전술적 최적화는 전통적인 데이터베이스 질의 최적화보다 프로그래밍 언어 최적화에 의해 더 영감을 받는다. 그것은 모든 결정이 단일 비용 공식으로 결합될 수 있는 것은 아니라는 것을 인식하면서, 지금까지의 모든 비용 기반 최적화와 결부된다. 공통 이항-관계 백엔드 대수에서 운용되는 이러한 최적화자 모듈은 모든 프런트엔드 데이터 모델과 쿼리 언어에 의해 공유된다.

 

Kernel

The bottom layer or kernel (aka. GDK) provides BATs as MonetDB’s bread-and-butter data structure, as well as the library of highly optimized implementations of the binary relational algebra operators. Due to the operator-at-a-time “bulk-processing” evaluation paradigm, each operator has access to its entire input including known properties. This allows the algebra operators to perform operational optimization, i.e., to choose at runtime the actual algorithm and implementation to be used, based on the input’s properties. For instance, a select operator can exploit sorted-ness of a BAT by deploying binary search, or (for point-selections) use an existing hash-index, and fall back to a scan otherwise. Likewise, a join can at runtime decide to, e.g., perform a merge-join if the join attributes happen to be sorted, and fall-back to hash-join otherwise.

하단 계층 또는 커널(ac. GDK)은 BAT를 모네DB의 빵-버터 데이터 및 이진 관계형 대수 연산자의 고도로 최적화된 구현의 라이브러리로 제공한다. 한 번에 운영자 "불크 처리" 평가 패러다임으로 인해, 각 운영자는 알려진 속성을 포함한 전체 입력에 접근할 수 있다. 이를 통해 대수 운영자는 운용 최적화를 수행할 수 있다. 즉, 입력 특성에 기초하여 런타임에 실제 알고리즘과 사용할 구현을 선택할 수 있다. 예를 들어, 선택 운영자는 바이너리 검색을 배치하여 BAT의 정렬된 강도를 이용하거나, (점 선택을 위해) 기존의 해시 색인을 사용하고, 그렇지 않으면 다시 검색으로 돌아갈 수 있다. 마찬가지로, 런타임에 조인 속성을 정렬할 경우 병합 결합을 수행하고, 그렇지 않으면 해시 결합으로 되돌아간다. 

=============================================================================================

아래 논문 참고함.

Breaking the Memory Wall in MonetDB

by Peter a. boncz, Martin l. Kersten, and stefan Manegold 

2.1. the memory hierarchy 

컴퓨터의 메인 메모리는 동적 RAM 칩으로 구성된다. CPU 클록 속도는 빠르게 증가하고 있지만 DRAM 액세스 지연 시간은 지난 20년 동안 거의 개선되지 않았다. 1980년대 초 D램 메모리를 1 대 2로 읽으면서 현재 300주기가 넘게 걸린다. 일반적으로 프로그램 지침 중 3개 중 1개는 메모리 로드/스토어이므로 최악의 경우 이 "메모리 벽"은 현대의 CPU의 효율성을 두 자릿수까지 줄일 수 있다. 일반적인 시스템 모니터링 도구(상단 또는 윈도우즈 작업 관리자)는 이러한 성능 측면에서 통찰력을 제공하지 않으며 100% 사용 중인 CPU는 95%의 메모리 정지 상태일 수 있다.

높은 DRAM 지연 시간을 숨기기 위해 메모리 계층은 일반적으로 CPU 칩 자체에 있는 캐시 메모리(cf, 그림 1)로 확장되었다. 모든 캐시 아키텍처의 기본 원칙은 참조 인접성, 즉 CPU가 항상 캐시에 적합한 제한된 양의 데이터만 반복적으로 액세스한다는 가정이다. 데이터가 주 메모리, 즉 필수 캐시 누락에서 로드되어야 하므로 첫 번째 액세스만 "느림"이다. 이후 액세스(동일한 데이터 또는 메모리 주소에 대한)는 데이터가 캐시에서 사용 가능하므로 "빠르게" 된다. 이것은 캐시 적중이라고 불린다. 캐시에서 이행할 수 있는 메모리 액세스의 분율은 캐시 적중률이라고 한다.

캐시 메모리는 메인 메모리와 CPU 사이에 여러 계단식 레벨로 구성된다. 그들은 더 빠르지만 더 작아질수록 CPU에 더 가까워진다. 나머지 부분에서는 캐시 레벨이 2개인 일반적인 시스템(L1과 L2)을 가정한다. 그러나 논의는 간단한 방법으로 임의의 수의 계단식 캐시 레벨로 쉽게 일반화할 수 있다.

실제로 캐시 메모리는 가장 최근에 액세스한 데이터뿐만 아니라 현재 실행 중인 지침도 보관한다. 따라서 오늘날 거의 모든 시스템은 두 개의 별도 L1 캐시를 구현하는데, 지시사항을 위한 읽기 전용 캐시와 데이터를 위한 읽기-쓰기 캐시를 구현한다. 그러나 L2 캐시는 일반적으로 지침과 데이터 모두에 사용되는 단일 "통합" 읽기-쓰기 캐시다.

캐시 메모리의 많은 기본 특성과 매개변수는 후속편과 관련이 있다.

capacity (C). A cache’s capacity de nes its total size in bytes. Typical cache sizes range from 32KB to 4MB. 

Line size (Z) 캐시는 캐시 라인으로 구성된다. 캐시는 인접한 캐시 레벨 간의 전송 단위 중 가장 작은 단위를 재적격한다. 캐시 누락이 발생할 때마다 다음 캐시 레벨 또는 메인 메모리에서 전체 캐시 라인(즉, 다수의 연속 단어)이 로드되어 넓은 버스를 통해 캐시 라인의 모든 비트를 병렬로 전송한다. 이는 공간적 인접성을 이용하여 캐시 누락을 야기한 참조에 "근접"되는 향후 데이터에 대한 캐시 적중 가능성을 증가시킨다. 일반적인 캐시 라인 크기는 64바이트 입니다.

associativity (A) A-way 집합 연관 캐시는 A-way의 다른 위치 중 하나에 라인을 로딩할 수 있다. A > 1이면 일부 캐시 교체 정책은 A 후보 중에서 하나를 선택한다. 가장 최근에 사용된 (LRU)는 가장 일반적인 대체 알고리즘이다. A = 1인 경우 캐시는 직접 매핑된 것으로 호출된다. 이 조직은 캐시라인 후보자를 결정할 때 (실제로) 최소의 오버헤드를 초래한다. 그러나, 그것은 또한 최소한의 융통성을 제공하며 많은 소위 갈등 실패를 야기할 수 있다. 다른 극단적인 경우는 완전히 연관성이 있는 캐시들이다. 여기서 각 메모리 주소는 캐시의 어떤 라인에도 로딩될 수 있다(A = #). 이렇게 하면 충돌 누락이 방지되며 캐시 용량이 초과될 때 소위 용량 누락만 발생한다. 그러나 이 전략에서 캐시 라인 후보를 결정하는 것은 캐시 크기에 따라 증가하는 상대적으로 높은 오버헤드를 야기한다. 따라서, 그것은 작은 캐시에서만 가능하다. 현재 PC와 워크스테이션은 일반적으로 2방향에서 8방향 연결 캐시를 구현한다.

대기 시간(l)은 CPU에서 결과가 나올 때까지 데이터 액세스의 실행 시간 범위를 의미한다. L1 캐시에서 이미 사용 가능한 데이터에 액세스하면 L1 액세스 지연 시간(LL1)이 발생하며, 이는 일반적으로 다소 작은(1 또는 2 CPU 주기)이다. 요청된 데이터를 L1에서 찾을 수 없는 경우, L1 누락이 발생하고, L2 캐시에 액세스하기 위해 L2 액세스 지연 시간(LLL2)까지 데이터 액세스를 추가로 지연시킨다. 이와 유사하게, 데이터를 아직 L2에서 사용할 수 없는 경우 L2 누락이 발생하고, 메모리 액세스 지연 시간(lMem)에 의한 액세스가 추가로 지연되어 메인 메모리에서 데이터를 마지막으로 로드한다. 따라서 두 캐시 모두 있는 데이터에 액세스하기 위한 총 대기 시간은 lMem + lL2 + lL1이다. 위에서 언급한 바와 같이, 모든 현재의 하드웨어는 실제로 이 기간 동안 다수의 연속된 단어, 즉 완전한 캐시라인을 전송한다.

대역폭(b)은 초당 CPU로 전송할 수 있는 데이터 볼륨(메가바이트)에 대한 메트릭이다. 서로 다른 대역폭을 각각 L2 액세스 대역폭(bL2)과 메모리 액세스 대역폭(bMem)이라고 한다. 메모리 대역폭은 단순히 캐시 라인 크기를 메모리 지연 시간으로 나눈 것이었다. 현대의 다중 프로세서 시스템은 초과 대역폭 용량 b′ b. 이것을 활용하기 위해서는 캐시가 비차폐화되어야 한다. 즉, 한 번에 둘 이상의 뛰어난 메모리 부하를 허용해야 한다. CPU는 캐시 누락에서 차단되지 않고 명령을 계속 실행(독립적)하기 때문에, 주문 외 명령 실행을 지원하는 CPU는 여러 개의 관련 전류 로드를 생성할 수 있다. 미결 메모리 요청 수는 일반적으로 CPU 내에서 제한된다. 접속 패턴이 순차적인 경우 현대 하드웨어에서 가장 높은 대역폭을 얻을 수 있으며, 이 경우 현대 CPU에 내장된 자동 메모리 프리페터가 활성화된다. 순차 액세스 대역 폭(b s = b ′)과 각(prefetched) 랜덤 액세스 대역폭(br = Z/lr)의 차이는 D램이 실제로 자기 디스크와 매우 유사한 블록 장치가 되었음을 의미한다.

Transition lookaside buffer (Tlb). 특별한 종류의 캐시인 TLB는 현대 CPU에 내장된 가상 메모리 지원의 일부분이다. 즉, 그것은 논리를 물리적 페이지 주소로 최근에 변환한 것을 기억한다(예: 64). 각 메모리 로드/스토어는 주소 변환이 필요하다. 페이지 주소가 TLB(TLB 히트)에 있으면 추가 비용은 없다. 그렇지 않다면, 매핑 테이블에서 좀 더 복잡한 조회가 필요하다. 따라서 TLB 누락은 패널티를 의미한다. 또한 (메모리 상주) TLB 매핑 테이블을 조회하면 추가적인 CPU 캐시 누락이 발생할 수 있다. TLB의 일반적인 페이지 크기 4KB와 64개 항목의 경우 많은 시스템에서 TLB 지연은 256KB보다 큰 데이터 구조(예: 해시 테이블)에 대한 랜덤 액세스에 이미 적용된다는 점에 유의하십시오.

unified hardware model. 위의 설명을 요약하면, 우리는 컴퓨터의 메모리 하드웨어를 (TLB 포함) 캐시의 N 수준의 계단식 계층으로 설명한다. 지수 i ∈ {1, . . ., N}은(는) 지정 C 수준의 각 값을 식별한다. 레벨 i + 1에 대한 접근은 레벨에서의 누락에 의해 야기된다는 이중주의를 이용하여 나는 표기법을 일부 단순화할 수 있다. 지연 시간 li = li + 1을 소개하고 각 누락 대역폭 bi = bi + 1 shows li = Zi /bi. 각 캐시 레벨은 표 1.b에 주어진 매개변수로 특징지어지며, 이러한 매개변수는 디스크 액세스의 비용 관련 특성도 포함한다고 지적했다. 따라서 I/O 작업을 위해 주 메모리(예: 데이터베이스 시스템의 버퍼 풀)를 캐시(레벨 N + 1)로 보는 것은 이 하드웨어 모델에 디스크 액세스를 포함하기가 쉽다.

우리는 모든 컴퓨터 하드웨어에서 이 매개변수를 자동으로 측정하기 위해 Calibrator c라는 시스템 독립적인 C 프로그램을 개발했다. 교정기는 신중하게 설계된 메모리 액세스 패턴을 사용하여 캐시 누락을 제어된 방식으로 생성한다. 캐시 누락이 있거나 없는 실행의 실행 시간을 비교하여 표 1에 열거된 캐시 파라미터와 대기 시간을 도출할 수 있다. Calibrator에 대한 자세한 설명은 PC용 Manegold.11,12 샘플 결과에 나와 있다.GHz Intel Core 2 Quad Q6600 CPU 모양: