Metadata Management Algorithms for Improving Performance of Memory-limited Flash Storage

Abstract

일반적인 플래시 스토리지는 원활한 동작에 필요한 메타데이터 전체를 스토리지 내부 메모리에서 관리한다. 메타데이터 중 가장 큰 부분을 차지하는 것은 호스트 시스템의 논리 주소를 플래시 메모리의 물리 주소로 변환하는데 사용되는 주소 매핑 테이블이다. 그러나 메모리가 제한된 플래시 스토리지에선 주소 매핑 테이블을 메모리에 로드해둘 수 없기 때문에 테이블에서 일부의 매핑 정보만 메모리에 캐싱하고 전체 정보는 플래시에서 관리된다. 메모리에서 매핑 정보가 캐싱 되는 공간을 맵 캐시라 한다. 맵 캐시가 관리되는 과정에서 플래시 입출력이 추가되므로 성능 저하가 발생한다. 기존에는 유저 데이터로의 플래시 입출력만 존재했기에 매핑 정보로의 플래시 입출력은 데이터 입출력의 처리를 방해하는 문제를 가져온다. 게다가 맵 캐시가 어떻게 관리되느냐에 따라 맵 입출력의 발생량이 달라진다. 맵 입출력은 스토리지의 전체적인 성능 및 수명에 악영향을 미칠 뿐만 아니라 호스트 입출력 요청의 지연 시간을 늘린다. 스토리지 접근 패턴의 공간 지역성에 맞춰 매핑 정보를 플래시에서 가져올 수 있다면 캐시 공간이 효율적으로 관리되어 맵 입출력의 발생량이 줄어든다. 이를 실현하기 위해 여러 맵 캐시 관리 기법들이 연구되었지만, 개선의 여지가 남아있는 상황이다. 맵 캐시에 의한 성능 저하를 완화하기 위해서 이 논문은 두 가지 기술을 제안한다. 첫 번째는 맵 캐시로 인해 발생하는 플래시 스토리지 내부 작업을 고려한 명령 스케줄링이다. 많은 낸드 플래시 스토리지 시스템은 호스트 시스템의 입출력 요청을 처리하기 위해 플래시 명령을 생성하여 플래시 메모리에 접근한다. 플래시 명령이 처리되는 순서는 입출력 성능에 영향을 미치기 때문에 이전 연구에서는 읽기 성능 향상을 위해 플래시 읽기 명령을 우선하는 명령 스케줄링을 수행했다. 그러나 맵 캐시 관리에 의한 플래시 명령은 입출력 요청의 지연 시간에 큰 영향을 미친다. 입출력 요청의 처리 시간은 매핑 정보용 플래시 명령과 사용자 데이터용 플래시 명령의 실행 시간에 따라 달라진다. 따라서 맵 플래시 명령의 발생에 대응하여 읽기 성능을 향상시키기 위한 명령 스케줄링을 제안한다. 읽기 요청으로부터 온 플래시 읽기 및 프로그램 명령에 우선권을 부여하고, 이 명령 중에서 처리 시간이 더 짧은 읽기 요청에서 발생한 플래시 명령이 먼저 수행된다. 실제 워크로드로 실험한 결과 제안된 스케줄링 방식은 기존 스케줄링 방식보다 평균 읽기 지연 시간을 최대 51%까지 줄이는 것으로 나타난다. 두 번째는 다양한 캐싱 세분성을 지원하는 맵 캐시 관리 기법이다. 맵 캐시 미스가 발생했을 때 스토리지 접근 패턴의 시간적 및 공간적 지역성을 활용하기 위해 다수의 매핑 정보를 플래시에서 가져온다. 정확히 어느 정도의 매핑 정보를 가져오는 것이 효율적인지 관해 여러 기법이 연구되었다. 그중에는 고정된 수의 매핑 정보를 가져오는 기법과 적응형으로 매핑 정보의 수를 결정하는 기법이 있다. 하지만 기존 연구들은 어떤 주소가 접근되는지와 관계없이 전역 캐싱 세분성을 갖는 방식에 머물러있다. 워크로드의 공간적 지역성은 접근되는 주소에 따라 다르기 때문에 주소마다 다른 캐싱 세분성을 가질 때 캐시 공간이 효율적으로 사용된다. 공간적 지역성과 캐싱 세분성이 크게 어긋나면 낮은 캐시 적중률을 보이거나 캐시 오염이 심각할 수 있다. 따라서 일정 단위의 주소별로 서로 독립적인 캐싱 세분성을 갖는 맵 캐시 관리 기법을 제안한다. 각 캐싱 세분성의 적정값은 미리 알 수 있는 것이 아니기 때문에 맵 캐시가 동작하는 내내 조정된다. 모바일 및 엔터프라이즈 환경의 워크로드로 실험한 결과 제안된 캐시 관리 기법은 기존 기법보다 매핑 정보로의 플래시 입출력 시간을 최대 84%까지 개선한다.|In typical flash storage, all metadata necessary for smooth operation is managed in internal memory. The largest part of the metadata is the address mapping table used to translate the logical address of the host system into the physical address of the flash memory. However, in memory-limited flash storage, because the address mapping table cannot be fully loaded into memory, only some mapping information from the table is cached, and all information is maintained in the flash. A space in memory where the mapping information is cached is called a map cache. As flash I/O is added during the process of managing the map cache, the storage performance is degraded. In typical flash storage, only flash I/O for user data takes place; therefore, adding flash I/O needed for mapping information in the map cache storage causes a problem, because it blocks user data I/O processing. Moreover, the amount of map I/O generated depends on how the map cache is managed. Map I/O not only adversely affects the overall storage performance and lifetime, it also increases the latency of host I/O requests. If the mapping information is fetched from the flash according to the spatial locality of the storage access pattern, the cache space is efficiently managed, and the amount of map I/O generated is reduced. To realize this, several map cache management schemes have been studied, but room for improvement remains. To alleviate the performance degradation caused by the map cache, this dissertation proposes two techniques. The first is command scheduling, which considers the internal tasks of the flash storage induced by the map cache. Many NAND flash storage systems access flash memories by generating flash commands to process input/output (I/O) requests from a host system. Because the order in which flash commands are processed affects the I/O performance, command scheduling has been performed in previous studies to prioritize flash read commands for improving the read performance. However, the flash commands by the map cache management have a significant influence on the latency of I/O requests. The processing time of the I/O request depends on the execution time of the flash commands for mapping information and the flash commands for user data. Therefore, a command scheduling to improve read performance to address the occurrence of map flash commands is proposed. Priority is given to the flash read and program command from the read request, and among these commands, the flash command originating from the read request, which has a shorter processing time, is executed first. Experiments conducted with real workloads show that the proposed scheduling scheme reduces the average read latency by up to 51% compared with the existing scheduling scheme. The second is a map cache management scheme that supports caching granularity variations. When a map cache miss occurs, a certain amount of mapping information is fetched from the flash to exploit the temporal and spatial locality of the storage access pattern. Several schemes have been studied to determine how efficient it is to fetch the exact amount of mapping information needed. Among them, there are schemes to fetch a fixed amount of mapping information, and schemes to adaptively determine the amount of mapping information to be fetched. However, existing studies are limited in the sense that they only incorporate global caching granularity, regardless of which addresses are accessed. Because the spatial locality of workloads depends on the addresses being accessed, cache space is efficiently used when the caching granularities differ by addresses. Large discrepancies between spatial locality and caching granularity can result in low cache hit ratios or severe cache pollution. Therefore, a map cache management scheme that adopts independent caching granularity for each address of a certain unit is proposed. Because the appropriate value of each caching granularity is not known in advance, it is adjusted throughout the map cache management process. As a result of experimenting with workloads in mobile and enterprise environments, the proposed cache management scheme improves the flash I/O time to access mapping information by up to 84% compared to existing schemes.