카운팅 블룸필터를 활용한 FAST FTL 로그영역 탐색성능 개선 (On Fast Searching of Log Area in FAST FTL using Counting Bloom Filters)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회논문지 : 데이타베이스 / 38권 / 3호 / 149 ~ 164페이지
· 저자명 : 강운학, 이상원

초록

낸드 플래시 메모리(NAND flash memory)를 사용한 저장장치는 빠른 읽기/쓰기 성능, 저 전력, 충격에 강한 장점들로 인해 사용영역을 넓혀가고 있다. 지금까지 제안된 많은 FTL 기법 중에서, FAST는 논리적 페이지와 물리적 페이지 사이의 완전연관성을 사용하여 로그영역을 관리함으로써, 임의쓰기 성능이 아주 우수한 것으로 알려져 있다. 그러나 모든 읽기/쓰기/병합 연산마다 해당 페이지의 최신 버전이 로그영역에 존재하는지 먼저 확인해야 하는 부담이 있다. Flash SSD(Solid State Disk)를 포함해서, 낸드플래시 메모리 기반의 저장장치가 대용량화함에 따라, 쓰기버퍼 역할을 하는 FAST의 로그영역도 증가하게 될 것이며, 사상테이블에 대한 스캔 방식의 로그 영역 검색은 확장성에 문제가 있다.
본 논문에서는, FAST 로그영역에 대한 탐색비용을 획기적으로 개선하는 확장성 있는 검색기법으로, 카운팅 블룸필터를 응용하는 방식을 제시한다. 제안한 기법은 플래시메모리 컨트롤러와 같이 메모리 사용량이 제한된 환경에서, 주어진 데이터페이지의 최신 버전이 FAST 로그영역에 존재하는지를 아주 빨리 결정할 수 있다. 성능평가 결과, 제안한 기법이 비트맵 대비 30% 메모리만을 사용하고도 평균 80% 탐색을 회피할 수 있었다. 카운팅 블룸필터가 높은 회피율과 낮은 긍정오류를 보이기 때문에, FAST의 로그영역 탐색에 아주 효과적임을 알 수 있다.

영어초록

NAND flash memory storage devices has been widely adopted in many applications, due to its good characteristics. Unlike hard disk drive, however, flash memory does not allow in-place update so that a block should be erased before a page of the block is overwritten. Several FTL algorithms have been proposed during the past decade, among them, FAST scheme is popular for its random write performance because of its full associativity between logical data pages and physical flash pages in log blocks (called log area). However, on every read/write/merge operations, FAST should check whether the most recent version of a page exists in log blocks. But, even though the mapping table resides in SRAM, this full scan of the mapping table for checking the existence of the up-to-date page in the log block is not any more trivial as the size of flash-based storage grows exponentially and thus the number of log blocks should accordingly increase for reasonable random write performance.As a scalable search scheme for log area, this paper applies the counting bloom filters to efficiently check whether the recent copy of a page exist in the log area of FAST scheme. To be specific, with a very small footprint of memory, which is very common in resource-limited flash memory controllers, the counting bloom filter can quickly determine a recent version of the given data page does not reside in log area when it does not have its recent copy in log area. The performance evaluation shows that our scheme can improve the search cost of log area by more than 80% with only exploit 30% of memory compare to bitmap scheme.

참고자료

· 없음