일단 써보기

LSM-Tree와 B-Tree는 현대 Key-value 저장소의 스토리지 엔진으로 주로 사용되는 자료구조입니다. LSM-Tree의 경우 updata 쿼리에서, B-Tree는 좁은 범위의 lookups에서 좋은 성능을 보입니다.

B-Trees

B-tree는 디스크에서 사용하기위해 설계된 인덱스 구조로 R. Bayer 와 E. McCreight가 1970년 7월 발표한 논문 "Organization and Maintenance of Large Ordered Indexes"에서 처음 발표되었습니다.

인덱스구조
데이터베이스에서 탐색속도를 높이는데 사용되는 자료구조입니다.
인덱스 구조를 생성하고 유지하기 위해서는 추가적인 스토리지 공간과 쓰기작업과 관련된 비용이 발생합니다. 하지만 인덱스를 사용하여 쿼리하는것이 데이터베이스의 모든 행을 탐색하는것보다 훨씬 빠르기 때문에 이러한 비용은 큰문제가 되지 않습니다.

B-tree를 사용하는 가장 큰 이유는 디스크 접근시간을 줄일 수 있기 때문입니다. B-tree는 2개 이상의 차수를 가진 트리구조로 비교적 적은 읽기 횟수로 데이터의 저장 위치를 알아낼 수 있습니다.

LSM-Trees

Log-Structured Merge Tree는 Patrick O’Neil이 1996년 발표한 논문 The Log-Structured Merge-Tree (LSM-Tree)에서 처음 발표되었습니다. LSM-tree는 우수한 업데이트 성능과 space amplification특성때문에 많은 key-value store 데이터베이스에서 차용되었습니다.

Space amplification

LSM-tree의 update는 디스크 I/O를 최소화하기위해 메모리의 버퍼에 log를 남깁니다. 그리고 버퍼는 주기적으로 정렬되어 디스크에 쓰여지는데 이를 flush라고 하며, 정렬된 일련의 배열을 run이라고 합니다.

LRU

LRU는 Least Recently Used의 약자로 페이지 폴트가 발생하게 되면 가장 오래전에 접근했던 페이지를 퇴출시켜 공간을 확보합니다.

버퍼에 존재하는 페이지에 접근하는 경우 리스트의 head로 페이지를 이동시킵니다. 이러한 방식으로 최근에 접근한 페이지 일수록 head에 가깝게, 오래전에 접근한 페이지일수록 tail에 가까이 위치하게 됩니다. 새로운 페이지를 위한 공간이 필요할 경우 tail에 존재하는 페이지를 퇴출시킵니다.

LRU는 주로 이중 연결리스트와 해시테이블을 통해 구현합니다. 구현이 간단하고, 알고리즘의 효율성 때문에 80년대 초반까지 대부분의 시스템에서 차용되었던 알고리즘입니다. 하지만, 이러한 장점들에도 불구하고 특정 상황에서 최악의 성능을 보입니다.

Sub-Optimality during DB scans

데이터베이스 테이블이 LRU 캐시보다 큰 경우, 테이블을 스캔할 때 DB 프로세스는 전체 LRU 캐시를 삭제하고 스캔한 테이블의 페이지들로 채우게 됩니다. 이러한 페이지들이 다시 참조되지 않는다면 데이터 베이스의 성능을 크게 저하시킬 수 있습니다.

2Q

LRU의 이러한 단점을 보완하기 위해 2Q는 추가적인 대기열을 통해 실제로 Hot한 페이지가 LRU캐시에 위치할 수 있도록 합니다. 즉, 2Q는 접근 빈도 뿐만 아니라, 페이지의 Hot여부도 판단합니다.

Simplified 2Q

2Q 알고리즘은 기본 LRU버퍼 Am과 보조 FIFO버퍼 A1으로 구성됩니다. Page Fault가 발생하면 먼저 A1버퍼에 페이지를 push합니다. 이후 페이지가 다시 참조되면 LRU버퍼 Am으로 페이지를 push합니다. 이를통해 Am버퍼에 있는 페이지의 hot함을 보장할 수 있습니다.

만약 A1버퍼의 page가 다시 참조되지 않으면 A1버퍼의 fifo정책에 따라 퇴출됩니다.
이는 해당 페이지가 cold하며, 캐시될 필요가 없음을 암시합니다.

def access_page(X: page):
    # if the page already exists in the LRU cache
    # in buffer Am
    if X in Am:
         Am.move_front(X)

    # if the page exists in secondary storage
    # and not it gets access.
    # since the page is accessed again, indicating interest
    # and long-term need, move it to Am.
    elif X in A1:
         A1.remove(X)
         Am.add_front(X)

    # page X is accessed for the first time
    else:
         # if A1 is full then free a slot.
         if A1.is_full():
             A1.pop()

         # add X to the front of the FIFO A1 queue
         A1.add_front(X)

A1버퍼의 크기가 너무 작다면, hot의 기준이 너무 높아지게 되며, A1버퍼의 크기가 너무 커지게 되면 메모리의 한계로 인해 Am버퍼의 크기를 줄이게 되고 이는 데이터 베이스의 성능을 저하시킬 수 있습니다.

2Q Full Version

일반적인 데이터베이스 접근 패턴에서 페이지는 짧은 시간동안 많은 참조를 받은 다음, 오랜시간 동안 참조되지 않습니다. 만약 캐시를 해야한다면, 짧은 시간의 많은 참조 이후에도 정기적으로 참조되는 페이지가 캐시되야 할 것입니다.

이러한 데이터 베이스 접근패턴에서 2Q를 활용하기 위해, 2Q Full Version은 보조 버퍼 A1을 A1-in, A1-out으로 나눕니다.

새로운 페이지는 항상 A1-in에 저장이 되고 페이지가 다시 참조될때까지 A1에 머무릅니다.
만약 페이지가 오래되어 퇴출되는 경우 메모리에서는 페이지가 삭제되지만, A1-out에 디스크 참조를 저장합니다. A1-out의 페이지가 다시 액세스 되는 경우 Am버퍼로 이동합니다.

References

• 2Q Cache Management Algorithm - Arpit's Newsletter
• LRU - Wikipedia
• The Saga of the ARC Algorithm and Patent
• 2Q: A low overhead high-performance buffer management replacement algorithm

Pre-processor(전처리기)

전처리기는 소스코드를 컴파일 할때 가장 먼저 실행되는 프로그램으로 소스파일의 지시자를 처리한다.

지시자는 #으로 시작해서 줄바꿈으로 끝나는 코드이다. ex) #inlcude<stdio.h>, #define MAX 10

소스코드 파일의 전처리가 끝나면 전처리기는 .i 확장자로 끝나는 전처리가 완료된 파일을 생성한다. 

Compiler(컴파일러)

컴파일러는 전처리가 완료된 .i파일을 어셈블리 프로그램으로 변환한다. 

컴파일러는 C, java, python 과 같은 고급언어에서 저급언어 assembly어 변환하는데 언어 문법에 맞지않거나 표준과 달라 발생하는 오류들을 발견하여 컴파일 에러를 발생시킨다. 컴파일이 완료되면 .s 확장자로 끝나는 어셈블리 프로그램을 생성한다. 

Assembler(어셈블러)

어셈블러는 어셈블리 프로그램을 기계어로 바꿔 .o 확장자로 끝나는 재배치가능한 객체 프로그램(relocatable object program)을 생성한다. 

Linker(링커)

링커는 재배치 가능한 프로그램들을 하나로 합쳐 실행가능한 프로그램을 만든다. 

hello.c 소스코드의 printf 와 같은 함수는 외부 라이브러리(stdio.h)의 printf.o 프로그램에 구현되어 있기 때문에 링크과정을 거쳐야 한다.

Loader(로더)

컴파일러를 통해 생성된 프로그램은 하드디스크와 같은 보조기억장치에 저장된다. 프로그램을 실행하기 위해서는 프로그램을 주기억장치인 메인 메모리에 적재해야 하는데 이때 사용되는 시스템 프로그램이 로더이다.

로더는 프로그램의 주기억장치 할당(Allocation) > 연결(Linking) >재배치(Relocation) >적재(Load) 순으로 실행되며 앞서 언급한 링커는 로더의 한 종류이다.

 추상화(abstraction)는 복잡한 자료, 모듈, 시스템 등으로부터 핵심적인 개념 또는 기능을 간추려 내는 것을 말한다.

ISA(Instruction Set Architecture)

ISA는 프로세서가 인식해서 기능을 이해하고 실행할 수 있는 명령어집합을 말한다. 하드웨어의 추상화로 하드웨어와 소프트웨어 사이의 인터페이스를 정의하며 프로세서의 제조회사마다 ISA가 다르다. 주로 다루게 될 ISA는 Intel사의 x86-64 아키텍쳐의 ISA이다.

추상화에 대한 이해가 필요한 이유

1. 수학의 일반적인 공리들이 맞지 않는 경우가 있다. 

 자료형의 범위를 넘어가는 값에서 overflow가 발생하여 잘못된 값이 저장된다.

예를 들어 int x,. x = 50000 * 50000 일때 overflow 가 발생한다.

2. 어셈블리에 대해 알아야 한다

- C, C++와 같은 고급언어들이 저수준에서 버그를 발생시킬수 있기때문

- 컴파일러에서 해결하지 못하는 프로그램의 최적화를 위해

- 시스템 소프트웨어를 실행시키기 위해

- 멀웨어를 방지하기위해

3. 메모리 referencing bug

 C, C++은 Memory Protection을 제공하지 않기 때문에 범위를 정확히 지정해 주지 않으면 Segmentation fault와 같은 버그가 발생할수 있다. 

4. 메모리 시스템에 대한 이해를 통해 성능을 향상시킬수 있다.

• rax is the 64-bit, "long" size register.  It was added in 2003 during the transition to 64-bit processors.
• eax is the 32-bit, "int" size register.  It was added in 1985 during the transition to 32-bit processors with the 80386 CPU.  I'm in the habit of using this register size, since they also work in 32 bit mode, although I'm trying to use the longer rax registers for everything.
• ax is the 16-bit, "short" size register.  It was added in 1979 with the 8086 CPU, but is used in DOS or BIOS code to this day.
• al and ah are the 8-bit, "char" size registers.  al is the low 8 bits, ah is the high 8 bits.  They're pretty similar to the old 8-bit registers of the 8008 back in 1972.

레지스터의 종류

Conditioion Code Register(상태 레지스터)

상태 레지스터, 플래그 레지스터 라고도 불리며 1비트 레지스터로 구성되어 있다. (t = a+b)

레지스터 인자 전달

-리눅스 ELF 환경에서는 다음과 같은 순서로 함수의 인자를 전달받는다

Parameter 1 - rdi

Parameter 2 - rsi

Parameter 3 - rdx

Parameter 4 - rcx

Parameter 5 - r8(범용레지스터)

Parameter 6 - r9(범용레지스터)

-인자가 7개 이상일경우 스택을 사용한다.

Parameter 7 - (%rsp)

Parameter 8 - 0x8(%rsp)

system call - %rax