개발

jackryu 2009. 6. 9. 19:14

 

 

 

 

FTL.pdf

 

nand(FTL).pdf

 

 

 

 

1. Wear-Leveling

Wear-Leveling 이란, 플래시 수명을 연장하기 위해 block 당 write 횟수를 모니터하여 한 block 에만 치우치지 않도록 균등하게 분배하는 기능을 말합니다. 즉, 특정 블록에만 데이터가 write 되는 것을 방지해 플래시 디스크가 깨지지 않도록 합니다. 

플래시메모리는 각 블록이 소거될 수 있는 한계 횟수를 가지고 있습니다. 따라서 , 특정 몇 블록에 기록 및 소거
작업이  집중되게 된다면, 일부 블록은 일찍 수명을 다하게 되어서 저장장치로서의 내구성에 문제가 있습니다.
따라서 위의 Wear-Leveling 기법은 플래시 메모리 시스템에서 상당히 중요한 기법이고, 어떻게 하는것이 가장
효율적이냐에 대해 여러가지 논의가 오가고 있는 주제입니다.


2. Wear-Leveling 기법들의 소개

효과적인 Wear-Leveling이 저장장치로서의 내구성에 큰 영향을 주기때문에, 이를 효과적으로 하기위한 많은 기법들이 연구되었는데요. 간단히 몇가지에 대한 소개와 장단점에 대해 써보겠습니다.

(1) 삭제색인(clealing index) 을 이용한 블록삭제 작업 - eNVy System

삭제색인을 블록삭제비용과 삭제 빈도의 곱으로 표시하여서, 이 색인을 이용하여 블록을 삭제하는 작업을
수행하는 기법입니다. 삭제색인이 큰 블록은 선택하는 방식이기 때문에, 당연히 저 수치가 높은 블록이
선택 되겠지요. 결국 삭제횟수가 많은 블록이 또 다시 선택되게 될텐데요 ( 삭제비용 * 삭제빈도 )
그럼 다시 거기에 기록이 되고.. 또 다시 선택되어 삭제가 되는 과정이 반복하게 됩니다.

이를 위한 해결책으로, 소거 횟수가  큰 블록과 소거 횟수가 작은 블록에서 유효한 데이터를 교환하는 방법이 있습니다. 하지만 삭제 작업 수행시마다 삭제색인을 계산하여 전체 블록과 계산하는 작업은  비용이 많이 듭니다.

(2) Greedy 정책 & Cost-benefit 정책

효과적인 지움정책을 연구하여 나타난 기법중에 하나인 Greedy정책에 대해 말씀드리겠습니다.  지움 과정에서
발생하는 유효 블록의 복사로 인한 작업을 최소화하기 위하여 유용한 데이터를 포함하고 있지 않은 무효 블록이
가장 많은 세그먼트를 선택하여 지우는 방법입니다. 

여기서 세그먼트는 블록의 모음입니다.
( 즉 페이지(YAFFS의 경우  CHUNK)의 모음 = 블록 ,  블록의 모음 = 세그먼트 )

플래시 메모리는 새로운 데이터를 쓰기 위해서 지움 과정을 반드시 거칩니다. 즉, 어느 블록에 새로운 데이터를
기록할때, 그전에 블록에 존재하던 데이터가 아직 유효한 데이터이면, 반드시 옮겨주고 써야한다는 것이죠.

하지만 만약 해당 세그먼트의 블록들이 무효화블록( 유효 데이터가 들어있지 않은 블록)이면 , 지움 작업을 선행할 필요가 없으므로, 그만큼의 비용이 절감 될것입니다. Greedy정책은 바로 그렇게 하도록 하는 정책입니다.

Cost-benefit정책은 다음공식으로 지울 세그먼트를 선택하는 기법입니다.

Benefit                       age x ( 1 - u )
----------          =  -----------------
Cost                               2u

각각 설명드리면, Cost(비용), Benefit(이익), u(이용률), (1 - u )은 이용될 빈 공간의 양, age는 가장 마지막으에 블록을 무효로 변화시킨후의 시간, 2u는 유효 블록을 읽고 그것들을 다른 빈 공간에 쓰는데 걸리는 시간을
의미합니다. Cost에 비해 Benefit이 큰 세그먼트를 채택하도록 하는 기법입니다. 역시 cost-benefit값을 계산하는데 드는 비용의 문제가 관건입니다.


(3) 로그 구조 파일시스템에 기반한 JFFS & YAFFS의 순차적 저장방식

데이터의 기록과 갱신을 말 그대로 플래시 메모리에 순서대로 수행하는 방식입니다. 모든 블록을 다 한번씩 사용하면 다시 처음 블록부터 다시 사용하는 방법을 반복하는 것이죠. 이 방식이 가장 균등하게 데이터를 저장 할 수 있는 방법입니다. 하지만 파일시스템에서는 파일의 접근 형태가 균일하지 않은 경우에는,  파일의 갱신빈도에 따라 해당 블록의 소거횟수의 편차가 커지는 문제가 생기게 됩니다.

일반적으로 파일을 사용함에 있어서 이러한 문제는 종종 발생할 수 없다고 생각됩니다. 부팅때마다 읽기/삭제/갱신등이 이루어지는 파일이 있을수도 있고, 한번 만들어지면 변화없이 계속되는 파일도 있을수 있기때문이죠. 즉 사용자가 어떻게 사용하느냐에 따라서 사용빈도는 달라지고, 소거횟수의 편차 또한 발생할 수 밖에 없습니다. YAFFS의 순차적 저장방식( 블럭할당 ) 은 이런 문제점이 내포되어 있는 것이죠.  추후에 블로그에 글을
통해 더 자세히 말씀드리겠지만, YAFFS의 블럭할당방식은 순차적일 뿐만아니라, 리부팅후에는 다시 처음부터 블럭을 검색하기 때문에, 소거횟수의 평준화가 이루어지기 상당히 힘들다고 생각합니다.


3. 프로젝트에서 목표로하는 Wear-Leveling

일단은, 현재 YAFFS에서 쓰고있는 순차적 저장방식보다 효율적으로 저장하는 방식을 중간발표 전까지 연구하고 검증하여 발표할 예정에 있습니다. 현재는 Hash를 이용한 Wear-Leveling을 생각하고 있습니다. 쓰기횟수에
따라 얻어지는 버켓내부에 연결리스트로 각 블록들을 연결할 생각입니다. 하지만, 좀 더 조원들과의 의견교류 및 효율성을 연구할 필요가 있을거 같네요~

본격적인 설계 및 코딩은 1월에 시작되는데, 그전까지 파이팅해서 효율적인 YAFFS 개선을 위해 노력해야겠습니다~!


참고논문:
1. 플래시 메모리 파일 시스템을 위한 효율적인 소거 횟수 평준화 기법(배영현,최종무,이동희,노삼혁,민상렬)
2. Greedy 방법을 개선한 플래시 메모리 지움 정책(김경윤,김영필,송인준,유혁)

 

 

 

Wear-Leveling

FLASH MEMORY WEAR LEVELING SYSTEM AND METHOD

  • 플래쉬 메모리 셀의 삭제하는데 걸리는 시간이 오래 걸릴 수록 셀의 수명이 줄어든다
  • wear leveling를 위해 주기적으로 논리 주소와 물리 주소 맵핑을 재배열 해준다.
    • real erasing time > reference erasing time 이면 다른 유닛 섹터를 할당
    • real erasing time <= reference erasing time 이면 현 섹터로 데이터를 옮긴다.
  • 결국, 삭제 블록의 사용 정도를 erase counter 없이 삭제 시간을 통해서 추측하여 사용
  • 문제점 : 정확도가 낮다


 

JFFS : The Journalling Flash File System

  • 100번째 재사용 블록을 선택할 때 마다, 유효한 데이터만 존재하는 블록을 랜덤하게 선택하여 옮김


 

WEAR LEVELING OF STATIC AREAS IN FLASH MEMORY

  • 기존 방법의 문제점
    • static area를 고려하지 않음
    • overhead : write/erase 카운터, 시스템 자원
  • 제안 방법
    • 많은 수(여기서는 1000번)의 write/erase operation이 일어날 때 wear-leveling 함
    • 타겟 유닛(블록) 선택 방법
      • selected from first to last in physical order (순차적)
      • gives equal probability for each unit to be selected (램덤)
  • 장점
    • static area의 wear-leveling 보장
    • 기존의 block 구조를 사용 가능
    • 시스템 overhead가 낮음
    • 다양한 FTL 알고리즘에 적용 가능


 

On Efficient Wear-Leveling for Large-Scale Flash-Memory Storage Systems

  • 플래쉬 사용을 분석하면 특정 블록만이 빈번이 사용된다
    • hot 블록, cold 블록 발생
  • 제안 알고리즘 : The Dual-Pool Algorithm
    • Cold-data migration
      • 삭제 횟수가 많은 블록에 업데이트가 자주 일어나지 않는 데이터를 옮긴다
    • Hot-cold regulation
      • hot pool에 있는 블록 중 가장 많이 사용한 블록과 cool pool에 있는 블록 중 가장 적게 사용한 블록을 교환
      • hot pool : 업데이트가 자주 일어나는 데이터를 저장하기 위한 블럭 모음, cool pool은 반대
    • 자세한 알고리즘 : Dirty Swap(DS)
      1. Write가 발생
      • hot pool에 있는 블록 중 가장 많이 사용한 블록(F)과 cool pool에 있는 블록 중 가장 적게 사용한 블록(C)의 삭제 횟수 비교
      • 임계값을 넘었다면 F블록의 valid data를 다른 free page에 옮기고 F블록을 지운다.
      • C블록의 valid data를 F블록으로 옮기고 C블록을 지운다.
      • pool에서 F블록과 C블록을 swap 한다.
    • 문제점
      • 위 알고리즘은 임계값을 넘지 못하고 중단되어 있는 경우, 비교되는 블록 외의 블록을 놓친다.
      • hot pool에 cold data가 cold pool에 hot data가 있어도 처리 못한다
    • Hot Pool resize (HPR)
      • hot pool에서 가장 많이 사용한 블록과 hot pool에서 가장 적게 사용한 블록의 삭제 횟수 차가 임계값의 두배보다 크다면 가장 적게 사용한 블록을 cold pool로 옮긴다
    • Cold Pool resize (CPR)
      • Effective erasure cycle (EEC) : Dirty Swap에서 pool에서 블록이 swap 된 후로 삭제된 횟수
      • cold pool에서 가장 큰 EEC를 가진 블록과 hot pool에서 가장 적은 EEC를 가진 블록의 EEC 차가 임계값보다 크다면 cold pool 중 가장 큰 EEC를 가진 블록을 hot pool로 옮긴다.
      • 막 DS에서 옮겨진 블록과 hot data를 가지고 있어 많이 지워진 블록과 구분을 하기 위해서 EEC를 쓴다.
  • 성능
    • 뛰어난 wear-leveling
    • wear-leveling 시 필요한 ram과 CPU cycles도 적은 편

 

 

- 첨부파일

FTL.pdf  
nand(FTL).pdf