선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 본 논문에서는 SSD 저장 시스템의 인덱스 연산 성능을 높이기 위하여 CHC-Tree 기반의 새로운 인덱스 관리 기법을 제안하였다. 기존의 하드 디스크 및 메모리를 위한 B-Tree 기반 인덱스 기법을 개선하여, 제안 기법은 트리의 인덱스 노드를 핫-콜드 클러스터로 분리하여 다른 클러스터로 저장하였고, 키와 포인터를 재배열하여 오프셋 압축함으로써 플래시 메모리의 저장 연산 수를 대폭 줄여서, 전반적인 저장성능을 높일 수 있었다.
- 본 논문에서는 디스크 기반 및 메인 메모리 기반 색인 중에서 가장 보편적인 B-Tree 색인을 근간으로 하여 플래시 메모리 저장 시스템에 적합한 색인 저장 기법을 연구하였다. 메인 메모리 데이터베이스에서 많이 사용되는 T-Tree도 가능하지만, 동시성 제어를 고려할 경우 B-Tree보다 성능이 낮은데, 그 이유는 메모리 보다 CPU의 발전 속도가 더 빠르므로, 상대적으로 접근수가 적은 B-Tree가 유리하기 때문이다[11].
- 본 연구에서는 이러한 데이터의 접근 패턴을 분석한 후, 정적인 속성의 데이터는 정적인 콜드 세그먼트에 클러스터링하고, 빈번히 수정되는 동적인 속성의 데이터는 동적인 핫 세그먼트에 저장하여, 전체적으로 세그먼트 업데이트 횟수를 줄이고자 한다. 보통 데이터가 수정된 블록을 오염된(dirty) 블록이라고 하는데, 세그먼트 내에 더티 블록이 모이면 클리닝을 수행하게 된다.
제안 방법
- 디스크 기반 색인은 깊이가 얕고 넓게 퍼진 트리를 써서 삽입/검색 시에 I/O 비용을 최소화 하였다. 반면에, 메모리 기반 색인의 접근 비용은 포인터로 노드의 메모리 주소를 획득하는 비용이므로 크지 않다.
- -Tree기법(BTR_N)이며, 전술한 바와 같이 최적성능이 나오는 트리 노드의 평균 점유율(69%)을 기본으로 하였다. 또한 트리가 거의 차 있는 최고밀도 저장의 경우(97%)의 B+-Tree기법(BTR_F)도 포함하여, 총 세 가지 색인을 비교 시험하였다. 실험 도구는 CSIM discrete- event simulation software [13] 시뮬레이션 언어와 Microsoft Visual C++를 사용하였다.
- 또한, T-Tree도 B-Tree에서 파생되어 B-Tree의 속성을 가지고 있으며, 실제 메모리 데이터베이스에서 B-Tree도 많이 사용된다. 또한, 기존의 디스크 기반 데이터베이스에서도 B-Tree가 대부분 활용된다는 관점에서 본 논문에서는 B-Tree에 기초하였고, B-Tree 중에서도 더 진보되어 보편적인 B+-Tree를 대상으로 하였다. 그 이유는 B+-Tree는 B-Tree와는 달리 중간 노드에 데이터 관련 정보를 넣지 않고 리프 노드에서 저장하므로, 상대적으로 색인 자체의 저장 효율이 높아지기 때문이다.
- 기존의 하드 디스크 및 메모리를 위한 B-Tree 기반 인덱스 기법을 개선하여, 제안 기법은 트리의 인덱스 노드를 핫-콜드 클러스터로 분리하여 다른 클러스터로 저장하였고, 키와 포인터를 재배열하여 오프셋 압축함으로써 플래시 메모리의 저장 연산 수를 대폭 줄여서, 전반적인 저장성능을 높일 수 있었다. 또한, 성능 확인을 위하여 큐잉방식의 시뮬레이션 모델을 제시하였다. 특히, 부하가 심한 저장 환경에서 실험한 결과, 전체적인 인덱스 처리 성능이 기존 기법에 비하여 23% 이상 개선됨을 확인하였다.
- 각 인덱스 노드는 이러한 핫-콜드 분류를 위하여 수정빈도시간을 저장하고 있다. 또한, 인덱스 영역을 핫 클러스터와 콜드 클러스터로 분류한다. 핫-클러스터는 핫-노드만을 포함하는 핫-세그먼트들로 구성되어 있다.
- 본 연구의 시뮬레이션에서는 제안한 CHCTR 색인을 기존의 BTR_N 및 BTR_F 색인과 비교 분석하였으며, 검색 및 갱신 부하에 따른 각 기법의 처리 성능과 응답 시간을 분석하였다. 또한, 전체 인덱스 연산 중 검색 연산은 50%, 삽입 및 삭제 연산은 각각 25%로 기본 구성하여 실험하였다.
- 7%로 나타났다. 물론 이 보다 더 압축률이 좋은 알고리즘이 많이 있으므로, 추후에 더 성능을 개선할 수 있으나, 본 연구의 편의상 프로그램 코드가 공개되어 있는 LZO1X 압축 기법을 사용하였으며, 압축레벨을 조절함으로써 압축률과 압축속도를 제어 가능하다. 여기에 키와 포인터를 분리하여, 각각 재 정렬하고, 오프셋을 압축함으로써 압축 성능을 LZW대비 약 8% 더 개선할 수 있었는데, 결과적으로 인덱스 접근성능이 향상되게 된다.
- 보다 세부적으로 CHCTR 기법의 효과를 분석하기 위하여, 혼합된 인덱스 연산을 검색 연산과 업데이트 연산(insert and delete)으로 다시 분리하여 실험해 보았다. 인덱스 검색 연산에 대한 처리 성능은 그림 7에 그려져 있고, 그 평균 응답 시간은 그림 9에 나타나 있다.
- 본 시뮬레이션 수행시 CHC-Tree 색인 기법(CHCTR)과 비교된 대상 색인은 가장 보편적으로 사용하는 B+-Tree기법(BTR_N)이며, 전술한 바와 같이 최적성능이 나오는 트리 노드의 평균 점유율(69%)을 기본으로 하였다. 또한 트리가 거의 차 있는 최고밀도 저장의 경우(97%)의 B+-Tree기법(BTR_F)도 포함하여, 총 세 가지 색인을 비교 시험하였다.
- 본 연구에서 제안된 기법의 성능을 검증하기 위하여 시뮬레이션을 수행한 후 그 결과를 분석해 보았다. 본 시뮬레이션 수행시 CHC-Tree색인 기법과 비교된 대상 색인은 가장 보편적으로 사용하는 B+-Tree(BTR)기법이다.
- 본 연구에서 핫 클러스터와 콜드 클러스터의 설정 비율은 전술한 데로 1:2이므로, 상대적인 hot-ratio 값은 33%로, hot-ratio값은 67%로 설정하였다. 또한, 전체 인덱스 접근 연산에서 검색 연산이 50%를 차지하고, 삽입 연산이 25%, 삭제연산이 25%로 하여 구성된다.
- 본 연구에서는 인덱스 노드를 접근 패턴에 따라서 자주 수정되는 “핫-노드”와 드물게 수정되는 “콜드 노드”로 두 가지로 분류한다.
- 본 연구의 시뮬레이션에서는 제안한 CHCTR 색인을 기존의 BTR_N 및 BTR_F 색인과 비교 분석하였으며, 검색 및 갱신 부하에 따른 각 기법의 처리 성능과 응답 시간을 분석하였다. 또한, 전체 인덱스 연산 중 검색 연산은 50%, 삽입 및 삭제 연산은 각각 25%로 기본 구성하여 실험하였다.
- 이러한 관점에서 본 연구에서는 메모리 기반 및 디스크 기반 데이터베이스에서 근간이 되는 B+-Tree를 본 플래시 메모리 저장 시스템에 적합하게 개선하여, RAM 메모리에 비하여 매우 느린 쓰기 연산과 지우기 연산의 부담을 줄이고, 성능을 개선할 수 있는 효율적인 색인 저장 기법인 CHC-Tree (Compressed Hot-cold Cluster Tree)를 제안한다. CHC-Tree 기법의 핵심은 핫-콜드 분리 기술과 콜드 세그먼트의 비활용 영역의 압축 기술로 구성된 압축된 핫-콜드 클러스터링 기법이다.
- 주요 시뮬레이션 파라미터는 초당 생성된 인덱스 연산의 수, 읽기 연산 수행시간, 쓰기 연산 수행 시간, 소거 연산 수행시간 등이다. 초당 생성된 인덱스 연산의 수는 검색연산의 경우는 1500개에서부터 500개 단위로 5,000개까지 변화시켜 보았으며, 갱신 연산의 경우는 300개에서부터 300개 단위로 2,400개까지 변화시켜 보았다. 이는 모두 시뮬레이션 시스템에 가해지는 작업 부하를 의미한다.
대상 데이터
- 플래시 메모리의 읽기 연산 수행 시간은 16㎲로 설정하였고, 쓰기 연산 수행 시간은 250㎲로 설정하였으며, 소거 시간은 세그먼트당 2㎳로 설정하였다. 각 연산 수행 시간은 기존의 연구[1]와 제품 홈페이지[14]에서 제시한 자료이다.
- 실험 도구는 CSIM discrete- event simulation software [13] 시뮬레이션 언어와 Microsoft Visual C++를 사용하였다. 실험이 수행된 하드웨어 환경은 펜티엄 쿼드CPU와 메인 메모리 2G, 하드디스크 500G이며, 운영체제는 윈도우 2003 서버를 사용하였다.
- 주요 시뮬레이션 파라미터는 초당 생성된 인덱스 연산의 수, 읽기 연산 수행시간, 쓰기 연산 수행 시간, 소거 연산 수행시간 등이다. 초당 생성된 인덱스 연산의 수는 검색연산의 경우는 1500개에서부터 500개 단위로 5,000개까지 변화시켜 보았으며, 갱신 연산의 경우는 300개에서부터 300개 단위로 2,400개까지 변화시켜 보았다.
이론/모형
- 다음으로 플래시 메모리 데이터베이스를 위한 시뮬레이션 모듈이 필요한데, 사용된 모델은 CSIM에서 제공되는 폐쇄형 큐잉 모델(Closed Queuing Model)이다. 이 모델을 통하여 초당 일정한 수의 읽기 쓰기의 인덱스 연산을 생성하고, 이와 연관된 인덱스 트리가 검색 또는 수정되면서 발생한 시스템의 처리 시간과 성능을 측정하면 된다.
- 본 연구에서 제안된 기법의 성능을 검증하기 위하여 시뮬레이션을 수행한 후 그 결과를 분석해 보았다. 본 시뮬레이션 수행시 CHC-Tree색인 기법과 비교된 대상 색인은 가장 보편적으로 사용하는 B+-Tree(BTR)기법이다. 실제 실험을 대신하여 컴퓨터 시뮬레이션 방식을 통한 모의실험을 선택한 이유는 다음과 같다.
- 본 실험에 사용된 압축 알고리즘은 명료하고 공개적으로 쉽게 구할 수 있는 LZO1X 압축 기법이다. 이 알고리즘의 성능은 웹에 공개되어 있다.
- 또한 트리가 거의 차 있는 최고밀도 저장의 경우(97%)의 B+-Tree기법(BTR_F)도 포함하여, 총 세 가지 색인을 비교 시험하였다. 실험 도구는 CSIM discrete- event simulation software [13] 시뮬레이션 언어와 Microsoft Visual C++를 사용하였다. 실험이 수행된 하드웨어 환경은 펜티엄 쿼드CPU와 메인 메모리 2G, 하드디스크 500G이며, 운영체제는 윈도우 2003 서버를 사용하였다.
- 따라서 쓰기와 지우기 연산의 횟수를 최대한 줄이는 것이 매우 중요하다. 이러한 최소 쓰기 목적을 위하여, 본 연구에서는 핫-콜드 분류 클러스터링 및 콜드 세그먼트 압축 기법을 사용한다.
성능/효과
- 즉, BTR_F는 최고의 저장효율을 가지고 있는데, 이는 결과적으로 인덱스 트리의 깊이를 짧게 만들어서 노드 접근 횟수가 줄었기 때문으로 분석된다. BTR_F는 5000개의 인덱스 검색 부하 시에 본 CHCTR 기법의 보다 6% 더 우수한 성능을 보였다.
- 전체구간에서 CHCTR 의 커브가 기존 기법에 비하여 완만하면서도 더 늦게 증가하면서 상대적으로 빠른 응답속도를 보였다. CHCTR은 인덱스 노드의 부하가 초당 2,400일 때, 기존 기법대비 23%의 개선된 처리 결과를 보였는데, 이러한 성능차이로 압축 핫-콜드 클러스터링의 효과를 확인할 수 있었다.
- 그리고 B+-Tree에서 수많은 임의의 값들을 삽입하고 삭제하는 시뮬레이션을 수행하여 분석한 결과 69%정도 차 있을 때가 가장 효율적이다. 한 노드에 최대한 많이 저장하면 검색 노드수도 줄어들고 저장 효율은 향상되지만, 삽입, 삭제시 노드의 변동이 너무 빈번하여 많은 수의 쓰기 연산을 유도하여 결과적으로 더 손실이 크다.
- 그림 5의 그래프에서 보면 본 CHCTR 기법이 느린 저장 연산을 최소화하여 기존 기법보다 처리 성능이 우세하다고는 하지만, 인덱스 연산 부하가1,500을 넘으면, 과도한 부하로 인하여, 서서히 성능이 저하됨을 알 수 있었다. 그림 6에서 인덱스 접근 부하가 증가하여도, 900이하의 구간에서는 별로 응답지연이 발생하지 않으나, 이 구간을 넘게 되면 적체현상이 발생하여 평균응답시간이 빠르게 증가함을 알 수 있었다.
- 본 논문에서는 SSD 저장 시스템의 인덱스 연산 성능을 높이기 위하여 CHC-Tree 기반의 새로운 인덱스 관리 기법을 제안하였다. 기존의 하드 디스크 및 메모리를 위한 B-Tree 기반 인덱스 기법을 개선하여, 제안 기법은 트리의 인덱스 노드를 핫-콜드 클러스터로 분리하여 다른 클러스터로 저장하였고, 키와 포인터를 재배열하여 오프셋 압축함으로써 플래시 메모리의 저장 연산 수를 대폭 줄여서, 전반적인 저장성능을 높일 수 있었다. 또한, 성능 확인을 위하여 큐잉방식의 시뮬레이션 모델을 제시하였다.
- 둘째, 하드 디스크나 메인 메모리는 쓰기 횟수가 거의 제한이 없는 반영구적 수명을 가지고 있는 반면에, 플래시 메모리는 쓰기 횟수가 최대 1,000,000번 정도로 수명이 제한된다.
- 그 이유는 B+-Tree는 B-Tree와는 달리 중간 노드에 데이터 관련 정보를 넣지 않고 리프 노드에서 저장하므로, 상대적으로 색인 자체의 저장 효율이 높아지기 때문이다. 또한, 우선적으로는 B+-Tree에 적용하였지만, 제안 기법을 B-Tree를 포함한 일반적인 트리 구조의 색인에도 적용이 가능하다.
- 이는 주로 작업 부하 증가에 따라서, 인덱스 연산의 집중에 의한 것이다. 또한, 전반적인 인덱스 연산의 처리 성능을 측정한 결과, CHCTR이 BTR_N 과 BTR_F 보다 더 높게 나타났다.
- 이 알고리즘의 성능은 웹에 공개되어 있다. 본 실험에서 트리 샘플로서 압축률을 측정해보니 중간 노드는 55.6%이고, 리프노드는 54.7%로 나타났다. 물론 이 보다 더 압축률이 좋은 알고리즘이 많이 있으므로, 추후에 더 성능을 개선할 수 있으나, 본 연구의 편의상 프로그램 코드가 공개되어 있는 LZO1X 압축 기법을 사용하였으며, 압축레벨을 조절함으로써 압축률과 압축속도를 제어 가능하다.
- 이 사실은 그림 10에서 압축 핫-콜드 클러스터링으로 인하여 역시 응답시간도 더 개선되었음을 확인할 수 있었다. 실제로, CHCTR의 평균응답시간은 기존 기법에 비하여 최대 38%가 개선되었다.
- 이러한 인텐시브 저장 연산이 수행되는 실험 환경에서는 당연히 본 CHCTR이 전체 구간에서 더 높은 성능을 보인다. 실험결과 특히, 900개 이상의 초당 인덱스 부하 상태에서 기존 기법에 비하여 26%정도의 훨씬 더 높은 성능을 보였다. 이러한 성능의 우위는 압축된 콜드 클러스터에서 지우기 및 쓰기 연산이 줄어들어서, 결과적으로 전체적인 인덱스 노드 업데이트 연산수가 감소하였기 때문으로 분석된다.
- 물론 이 보다 더 압축률이 좋은 알고리즘이 많이 있으므로, 추후에 더 성능을 개선할 수 있으나, 본 연구의 편의상 프로그램 코드가 공개되어 있는 LZO1X 압축 기법을 사용하였으며, 압축레벨을 조절함으로써 압축률과 압축속도를 제어 가능하다. 여기에 키와 포인터를 분리하여, 각각 재 정렬하고, 오프셋을 압축함으로써 압축 성능을 LZW대비 약 8% 더 개선할 수 있었는데, 결과적으로 인덱스 접근성능이 향상되게 된다.
- 그림 6에서 인덱스 접근 부하가 증가하여도, 900이하의 구간에서는 별로 응답지연이 발생하지 않으나, 이 구간을 넘게 되면 적체현상이 발생하여 평균응답시간이 빠르게 증가함을 알 수 있었다. 전체구간에서 CHCTR 의 커브가 기존 기법에 비하여 완만하면서도 더 늦게 증가하면서 상대적으로 빠른 응답속도를 보였다. CHCTR은 인덱스 노드의 부하가 초당 2,400일 때, 기존 기법대비 23%의 개선된 처리 결과를 보였는데, 이러한 성능차이로 압축 핫-콜드 클러스터링의 효과를 확인할 수 있었다.
- 즉, 평균점유율(average fill factor)이 69%일 때 가장 안정되어 인덱스 리벨런싱과 재구성을 하지 않고도 인덱스 연산을 수행할 수 있다. 따라서 인덱스 구성시 이 평균점유율에 맞추어 B+-Tree를 조직하게 된다.
- 첫째, 읽기 연산의 경우에는 플래시 메모리의 연산처리 속도가 하드 디스크에 비하여 800배 정도로 매우 빠르며, 일반 RAM 메모리에 비해서는 좀 느리지만 10㎲ 정도로 빠르므로 접근 시에 별 문제가 없다[3, 4]. 하지만, 플래시 메모리의 쓰기 연산의 경우에는 속도가 읽기 연산 대비 20배 정도의 많은 시간이 소모되어 매우 느리며, 메인 메모리처럼 Update-In-Place(제자리 덮어 쓰기)가 불가능한 Update-Out-Place 구조이다.
- 콜드 세그먼트내의 각 인덱스 노드에 대하여 각 키와 포인터 필드의 배열을 오프셋 압축하여, 52%의 압축이 가능하였다. 압축률과 압축속도는 레벨에 따라 효율적으로 조절이 가능하며, CHC-Tree의 인덱스 구조는 다음과 같다.
- 또한, 성능 확인을 위하여 큐잉방식의 시뮬레이션 모델을 제시하였다. 특히, 부하가 심한 저장 환경에서 실험한 결과, 전체적인 인덱스 처리 성능이 기존 기법에 비하여 23% 이상 개선됨을 확인하였다. 본 CHC-트리 기반 인덱스 관리 기법은 플래시 메모리나 SSD가 장착된 최신 데스크톱 컴퓨터 및 중대형 데이터 서버 등에서 폭넓게 활용 가능하다.
- -Tree에서 수많은 임의의 값들을 삽입하고 삭제하는 시뮬레이션을 수행하여 분석한 결과 69%정도 차 있을 때가 가장 효율적이다. 한 노드에 최대한 많이 저장하면 검색 노드수도 줄어들고 저장 효율은 향상되지만, 삽입, 삭제시 노드의 변동이 너무 빈번하여 많은 수의 쓰기 연산을 유도하여 결과적으로 더 손실이 크다.
후속연구
- 따라서 범용 정보기기에서의 기존의 하드 디스크나 메모리 저장 장치와 더불어, 플래시 메모리 기반 데이터 저장 시스템은 향후 상당히 유망하며, 이와 관련된 데이터 관리 기술의 개발이 매우 시급하다고 할 수 있다. 이러한 저장 미디어에 대한 성능상의 차이는 다음 표1.
- 이러한 단점들로 인하여, 기존의 인덱스 관리 기법들은 플래시 메모리에 쉽게 적용이 되지 못하였다. 따라서 플래시 메모리의 제약점을 효과적으로 극복할 뿐 아니라, 그 고유의 장점을 효과적으로 활용하는 새로운 인덱스 관리 구조와 저장 시스템의 연구가 필요하다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.