SSD 쓰기 감소를 위한 2WPR 캐시 페이지 교체 알고리즘 평가 및 개선

2-1 SSD 연구 배경

SSD의 쓰기 감소를 위한 기본적인 전략은 캐시 운영 전략에서 쓰기를 최대한 억제하는 방안을 모색하는 것이다[8]. 일반적인 캐시 전략의 최대 목표는 읽기와 쓰기를 포함하여 전체적인 적중률을 높이는 데 있지만, SSD의 경우에는 적중률 하락에 대한 보상으로 쓰기 횟수를 줄이는 데 있다. SSD의 쓰기 감소를 위해서 쓰기 적중률은 유지하거나 높이되 읽기 적중률의 하락을 감수하자는 의도이다. 좀 더 구체적으로 접근하면 쓰기 1회를 줄이는 대신 읽기 몇 회를 더 허용한다는 의미로 풀이된다. 연구[9]에서 사용된 표 1의 SSD 사양 예에 따르면 접근 시간 관점에서는 쓰기 1회가 읽기 10회와 동등하고, 에너지 소모관점에 에서는 쓰기 1회가 읽기 15회와 맞먹는다. 여기에 쓰기 팽창 결과를 고려한다면 쓰기 대비 읽기의 대등 횟수는 더 많아질 것인데, 이에 대한 보다 정확한 산출을 시도하는 연구들이 있다[6], [10].

Table 1.

An Example of Access Time and Energy Consumption of SSDs

2-2 SSD 쓰기 감소 관련 연구

SSD의 쓰기 감소를 위한 캐시 알고리즘 연구는 SSD가 본격적으로 보급되기 시작한 2000년대 중반에 시작되었다, 이 시기의 대표적인 연구로 CF-LRU(clear first LRU)[11]를 들 수 있다. CF-LRU는 희생 페이지가 필요할 때 그림 1과 같이 LRU 리스트의 상위 몇 개(윈도우 w)를 대상으로 클린(clean)과 더티(dirty) 그룹으로 분류한 뒤 클린 그룹이 없을 때만 더티 그룹에서 희생 페이지를 선택한다. 더티 페이지를 방출할 때 발생하는 쓰기 연산을 최대한 미루자는 의미인데, 사용되지 않을 더티 페이지가 캐시를 오래 차지하여 캐시 전체의 용량을 감소시킴으로써 결국 다른 쓰기 연산을 유발할 가능성이 높다. 이러한 CF-LRU의 단점은 더티 그룹을 좀 더 세분화함으로써 완화시킬 수 있다. LRU-WSR(LRU and write sequence reordering) [12]는 첫 참조 페이지를 콜드(cold), 두 번 이상의 참조 페이지를 핫(hot)으로 정의하고, 클린과 콜드-더티 페이지를 동일 순위로 방출한다. 다만, 핫-더티 페이지에 대한 영원한 우대를 예방하기 위해 윈도우 내 핫-더티 페이지는 콜드-더티 상태로 변환하여 MRU로 이동시킨다. 이렇게 이동된 콜드-더티 페이지가 참조 없이 LRU 윈도우 범위에 진입하면 방출 대상이 된다.

Fig. 1.

LRU List of CF-LRU and LRU-WSR

AD-LRU(adaptive double LRU)[13]은 그림 2와 같이 리스트를 아예 콜드 페이지와 핫 페이지 등 두 개로 분리하고, 첫 참조 시 콜드 페이지에 삽입한 다음, 재 참조 이후에는 핫 리스트로 이동시킨다. 희생 페이지의 선택은 콜드 리스트가 일정 크기 이상이면 콜드 리스트에서, 그렇지 않으면 핫 리스트에서 LRU-WSR 방식으로 이루어지는데, 다만 콜드-클린과 핫-클린 등 클린 그룹의 세분화가 더해진다.

Fig. 2.

LRU List of AD-LRU

그림 2의 LRU 리스트 분리 개념은 클린/더티, 핫/콜드 등 단순한 두 가지 이분법적 조합 외에 더 유연하고 다양한 지표의 적용을 가능케 하는 틀로 자리 잡고 있다. 이러한 LRU 리스트 분리 개념이 쓰기 감소 알고리즘을 한 단계 업그레이드할 수 있는 계기가 되었고, 그 연장선 상에서 가장 최근에 발표된 연구 결과 중의 하나가 2WPR 알고리즘이다.

3-1 2WPR 알고리즘의 LRU 리스트

2WPR 알고리즘은 그림 3과 같이 LRU 리스트를 2WPR_List와 Victim_List로 분리하여 아래와 같이 운영한다.

• ① 첫 참조 페이지는 2WPR_List의 MRU에 삽입한다.
• ② 2WPR_List의 크기가 주어진 한계를 초과하면 윈도우(w) 내에서 희생 페이지를 선택하여 Victim_List의 MRU로 이동‧삽입한다.
• ③ 과정 ②에서 Victim_List의 크기가 주어진 한계를 초과하면 CF-LRU 방식으로 희생 페이지를 선택하여 방출한다.
• ④ 2WPR_List에서 재 참조된 페이지는 해당 리스트의 MRU로 이동시킨다.
• ⑤ Victim_List에서 재 참조된 페이지는 2WPR_List의 MRU로 이동‧삽입한다.

Fig. 3.

LRU List of 2WPR

3-2 2WPR_list의 희생 페이지 선택

2WPR 알고리즘의 핵심은 그림 3의 과정 ②에서 쓰기를 최대한 줄일 수 있는 방출 후보 페이지 선정 방법에 있는데, 쓰기로 재 참조될 가능성을 의미한 쓰기 비중 혹은 쓰기 가중치(WW: write weight)를 측정하여 그 비중이 가장 가벼운 페이지를 선택하도록 한다. 쓰기 비중을 산출하기 위해 아래의 3가지 지표를 도입한다.

￭ 시간적 지역성(TL: temporal locality)

총 참조 횟수가 낮은 페이지는 시간적 지역성이 낮을 것이므로 높은 방출 우선순위를 부여한다. 이를 위해 식 1과 같이 윈도우 내 모든 페이지의 평균 참조 횟수 대비 각 페이지의 참조 횟수를 시간적 지역성 지표로 정의한다.

￭ 공간적 지역성(SL: spatial locality)

파일 시스템을 구성하는 LBA(logical block address) 순서 상 특정 페이지의 참조 시간과 바로 전 페이지 참조 시간의 차가 길면 공간적 지역성이 낮으므로 높은 방출 우선순위를 부여한다. 이를 위해 식 2와 같이 각 페이지들 사이의 참조 시간의 차를 공간적 지역성 지표로 정의한다. 이 식에서 page_prev(i)는 LBA 순서 상 page_i의 바로 전 페이지를 의미한다.

￭ 쓰기 비율(WR: write ratio)

참조 횟수 중, 쓰기 참조 횟수가 적은 페이지는 쓰기 부담이 낮으므로 높은 방출 우선순위를 부여한다. 이를 위해 식 3과 같이 윈도우 내 모든 페이지의 평균 참조 횟수 대비 각 페이지의 쓰기 참조 횟수를 쓰기 비중 지표로 정의한다.

위에서 식 1과 식 2는 쓰기 비중과 반비례 관계에 있으므로 일차적인 쓰기 비중 WW는 아래의 식 4와 같이 구할 수 있다.

그런데, 식 4는 어느 한 항목이 전체 결과 값을 지배할 수 있으므로, 각 항을 0 ~ 1 범위로 변환하기 위해 각 지표 및 최종 쓰기 비중을 식 5 ~ 식 8과 같이 재정의한다.

위의 기초 지표 식 5 ~ 식 7을 기반으로 시뮬레이션을 통해 2WPR 알고리즘의 성능을 분석하고 개선한다.

3-3 실험 환경

￭ 실험 플랫폼

분석 및 평가가 이루어진 하드웨어 플랫폼 환경은 표 2와 같다.

Table 2.

Experimental Environment (Hardware Platform)

￭ FTL 시뮬레이터

FTL 시뮬레이션을 위해 DiskSim을 그림 4의 모형으로 축약하여 연구[8]에서 소개한 리눅스 FUSE 기반 시뮬레이터를 사용한다.

Fig. 4.

Architecture of the FTL Simulator

￭ 캐시 구성

페이지 사이즈 8K, RAM 사이즈 256MB인 SSD를 모델로 하여 이중 128MB는 매핑 테이블로, 나머지 128MB는 캐시로 사용한다. 캐시는 총 16K개인데 이를 128개 그룹으로 구성하고, "LSN(logical sector number) mod 128"의 해시 함수로 캐시 할당 그룹을 결정한다. 페이지 교체는 각 그룹별 128개의 캐시에서 이루어진다. 각 그룹별 128개의 캐시 중 2WPR_List에 90개(약 70%)를, Victim_List에 나머지 38개를 배분한다. 그리고 2WPR_List에서 쓰기 가중치를 적용할 윈도우는 6(약 7%)으로 설정한다.

￭ 워크로드 데이터

실험용 데이터로는 실제 현장 트레이스 데이터로 알려진 표 3의 금융 데이터[14]를 활용한다. 이들 금융 데이터는 512 바이트 블록 기반 파일 시스템에서 약 12시간 동안 운영체제 입‧출력 요청을 모니터링한 결과로 <LBA, size, R/W, time_ stamp> 형태로 구성되어 있다.

Table 3.

Experimental Data for Workload

3-4 평가 및 분석

￭ 각 지표들의 유효성 분석

식 5 ~ 식 7에서 도출된 TL’, SL’, WR’ 각 지표의 유효성을 분석하기 위해 이들 지표들의 조합이 아닌 개별적 적용에 따른 쓰기 횟수 추이를 관찰한다. 이를 위해 각 지표에 대하여 서로 상반되는 반대 부호 (+, -)의 지표 값을 두 데이터에 적용한 결과를 비교한다. 그림 5와 그림 6이 그 결과인데, 예상과 다르게 반대 부호로 적용했을 때 오히려 더 우수한 결과를 낳는 경우가 많다. 이 결과로부터, 각 지표들에 대한 전제 내용에 내부적인 변수가 있으며, 이들 지표들을 모두 합산하여 최종 쓰기 비중으로 활용하는 방안이 최선이 아닐 수도 있음을 예상할 수 있다. 이들 지표들의 합산 외에 다른 조합들에 대한 실험 필요성이 제기된다.

Fig. 5.

Write Count Trend of Financial1 with Respective Metric

Fig. 6.

Write Count Trend of Financial2 with Respective Metric

4-1 쓰기 비중 지표들의 재조합

종합 지표인 쓰기 비중을 구성하는 세 가지 지표들의 다양한 조합을 시행착오를 거쳐 실험한 결과, 원래 제안된 식 8 외에 식 9 ~ 식 11이 비교해볼 가치가 있는 것으로 판단된다. 식 9는, 그림 5와 그림 6에서 각 지표가 쓰기 횟수 감소에 부정적 영향을 미친 것으로 나타나 각 지표의 부호를 반대로 설정한 것이고, 식 10은 식 8의 각 지표 간 가중치 불균형에 의한 영향을 줄이기 위해 합산 대신 비례식(곱셈)으로 변환한 것이며, 식 11은 그림 5의 쓰기 우위 데이터에서 SL의 부정적 영향이 크게 나타나 식 10을 변형하여 이를 반비례 지표로 반영한 것이다.

그림 7과 그림 8에 새로 조합된 쓰기 비중들의 비교를 위한 식 8(WW8) ~ 식 11(WW11)에 대한 쓰기 감소 효과를 보였다. 이 두 그림에서 보는 바와 같이 공간 지역성 SL'을 반비례 지표로 적용한 식 11이 가장 우수함을 알 수 있다.

Fig. 7.

Write Count Trend with Recombined Write Weight(Financial1)

Fig. 8.

Write Count Trend with Recombined Write Weight(Financial2)

4-2 새로운 쓰기 비중 도출

식 11의 특징 중의 하나는 쓰기 비중이 지표들의 합산이 아닌 비례식으로 구성되었다는 점이다. 지표들을 비례식으로 구성할 경우 어느 한 지표가 전체를 지배하는 지표 간 가중치 불균형의 위험성을 완화시킬 수 있다. 이 추론의 범위를 좀 더 확장하면 가중치 균등화를 위해 지수 함수로 변환하기 이전의 원천 지표인 식 1 ~ 식 3을 비례식에 곧바로 적용하는 방안을 검토해볼 필요가 있다. 식11의 쓰기 비중을 변환 이전의 지표들인 식 1 ~ 식 3으로 대체하여 재구성하면 식 12와 같다.

4-3 제안 지표의 평가

표 4와 그림 9, 그리고 그림 10은 원래의 쓰기 비중인 식 8(WW8) 대비 지표들을 재조합한 쓰기 비중인 식 11(WW11)과 새로운 쓰기 비중인 식 12(WW12)의 쓰기 감소 효과를 비교해 보이고 있다. 새로 도출된 쓰기 비중인 식 12가 쓰기 비율이 높은 Financial1 워크로드에서 원래의 식 8 대비 쓰기 및 읽기 감소 비율이 약 2%로 나타나 그 효과가 높다. 읽기 비율이 높은 Financial2에서는 쓰기 감소 개선이 약 0.1%로 나타나 효과가 높지 않다. 개선된 쓰기 비중은 쓰기 비율이 높은 워크로드에서 높은 효과를 보인다.

Table 4.

Write Reduction Effects of WW11 and WW12

Fig. 9.

Write Reduction Comparison of Improved Write Weight(Financial1)

Fig. 10.

Write Reduction Comparison of Improved Write Weight(Financial2)

새로운 쓰기 비중 WW12에 대한 개선 효과의 안정성을 검증하기 위해 표 3의 워크 로드 데이터를 표 5와 같이 1,000,000 여건 단위로 분리‧재구성하여 실험한 결과를 표 6에 보였다. 이 표로부터 새롭게 제안된 쓰기 비중 WW12가 기존의 쓰기 비중인 WW8보다 낮은 경우는 발견되지 않음을 확인할 수 있다.

Table 5.

Reconfiguration of Experimental Data

Table 6.

Write Count of WW8 and WW12 in Reconfigured Data