[go: up one dir, main page]

KR101457270B1 - Ｌｂａ 비트맵 사용 - Google Patents

Ｌｂａ 비트맵 사용 Download PDF

Info

Publication number
KR101457270B1
KR101457270B1 KR1020120143392A KR20120143392A KR101457270B1 KR 101457270 B1 KR101457270 B1 KR 101457270B1 KR 1020120143392 A KR1020120143392 A KR 1020120143392A KR 20120143392 A KR20120143392 A KR 20120143392A KR 101457270 B1 KR101457270 B1 KR 101457270B1
Authority
KR
South Korea
Prior art keywords
nvm
lba
bitmap
nvm interface
tree
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
KR1020120143392A
Other languages
English (en)
Other versions
KR20130066524A (ko
Inventor
다니엘 제이. 포스트
니르 제이콥 워크랫
바딤 크멜니츠키
Original Assignee
애플 인크.
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 애플 인크. filed Critical 애플 인크.
Publication of KR20130066524A publication Critical patent/KR20130066524A/ko
Application granted granted Critical
Publication of KR101457270B1 publication Critical patent/KR101457270B1/ko
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
    • G06F12/023—Free address space management
    • G06F12/0253—Garbage collection, i.e. reclamation of unreferenced memory
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
    • G06F12/023—Free address space management
    • G06F12/0238—Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
    • G06F12/0246—Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory in block erasable memory, e.g. flash memory
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
    • G06F12/023—Free address space management
    • G06F12/0238—Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/10—Providing a specific technical effect
    • G06F2212/1016—Performance improvement
    • G06F2212/1024—Latency reduction
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/10—Providing a specific technical effect
    • G06F2212/1041—Resource optimization
    • G06F2212/1044—Space efficiency improvement
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/72—Details relating to flash memory management
    • G06F2212/7201—Logical to physical mapping or translation of blocks or pages
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/72—Details relating to flash memory management
    • G06F2212/7205—Cleaning, compaction, garbage collection, erase control
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
    • G06F2212/72—Details relating to flash memory management
    • G06F2212/7209—Validity control, e.g. using flags, time stamps or sequence numbers

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Human Computer Interaction (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Memory System (AREA)
  • Techniques For Improving Reliability Of Storages (AREA)

Abstract

비휘발성 메모리("NVM")를 갖는 시스템용의 논리 블록 주소("LBA") 비트맵 사용을 위한 시스템 및 방법이 개시된다. 비트맵은 시스템의 휘발성 메모리에 저장될 수 있으며, 비트맵은 하나 이상의 논리 주소의 맵핑 상태를 저장할 수 있다. 비트맵을 이용함으로써, 시스템은 NVM에 액세스하지 않고도 LBA의 맵핑 상태를 판정할 수 있다. 또한, 시스템은 최소한의 NVM 액세스를 동반하며 LBA의 맵핑 상태를 업데이트할 수 있다. NVM 액세스 횟수를 줄임으로써, 시스템은 폐영역 회수 프로세스의 트리거링을 피할 수 있어서, 전체 시스템 성능을 개선할 수 있다.

Description

ＬＢＡ 비트맵 사용{LBA BITMAP USAGE}
NAND 플래시 메모리 뿐만 아니라 기타 유형의 비휘발성 메모리("NVM")는 대용량 저장을 위해 흔히 사용된다. 예를 들어, 휴대용 미디어 플레이어와 같은 가전 제품들은, 음악, 비디오 및 기타 미디어를 저장하는 플래시 메모리를 종종 포함한다.
NVM을 갖는 시스템은, 논리 블록 주소("LBA"; logical block address)의 맵핑 상태를 나타내는 NVM에 저장된 인덱스 페이지(index page)를 포함할 수 있다. 예를 들어, LBA의 맵핑 상태가 "맵핑됨(mapped)"이라면, 이것은 LBA가 현재 NVM에 저장된 데이터와 연관되어 있다는 것을 나타낼 수 있다. 대안으로서, 만일 LBA의 맵핑 상태가 "언맵핑됨(unmapped)"이라면, 이것은 이전에 LBA에 맵핑된 데이터가 삭제되었거나 LBA가 임의의 데이터에 결코 맵핑된 적이 없다는 것을 나타낼 수 있다.
LBA의 맵핑 상태는 인덱스 페이지에 저장되기 때문에, LBA가 맵핑되거나 언맵핑될 때마다 시스템은 인덱스 페이지를 업데이트할 필요가 있으므로, NVM에 관해 프로그래밍 동작이 수행되게끔 한다. 추가적인 프로그래밍 동작 때문에, 시스템은 결국 공간을 자유롭게 하기 위해 NVM에 관한 폐영역 회수(garbage collection)를 수행할 필요가 있다. 이것은 차례로 시스템 성능을 저하시킨다.
비휘발성 메모리("NVM")를 갖는 시스템용의 논리 블록 주소("LBA") 비트맵 사용을 위한 시스템 및 방법이 개시된다. 시스템의 휘발성 메모리에 저장될 수 있는 비트맵은, 하나 이상의 논리 주소(예를 들어, LBA)의 맵핑 상태를 저장할 수 있다. 비트맵을 이용하여, 시스템은 NVM에 액세스하지 않고도 LBA의 맵핑 상태를 판정할 수 있다. 또한, 시스템은 최소한의 NVM 액세스를 동반하며 LBA의 맵핑 상태를 업데이트할 수 있다. NVM 액세스 횟수를 줄임으로써, 시스템은 폐영역 회수 프로세스의 트리거링을 피할 수 있어서, 전체 시스템 성능을 개선할 수 있다.
본 발명의 상기 및 기타의 양태들 및 이점들은, 도면 전체를 통해 유사한 참조 번호가 유사한 부분들을 나타내고 있는 첨부된 도면들과 함께 이하의 상세한 설명의 고려시에 더욱 명백해질 것이다.
도 1은 본 발명의 다양한 실시예에 따라 구성된 전자 장치의 블록도이다;
도 2는 본 발명의 다양한 실시예에 따른 메모리 맵핑 아키텍쳐의 예시적 블록도이다;
도 3은 본 발명의 다양한 실시예에 따라 구성된 전자 장치의 또 다른 블록도이다;
도 4a 내지 도 4c는 본 발명의 다양한 실시예에 따른 예시적 비트맵이다;
도 5는 본 발명의 다양한 실시예에 따른 비트맵을 이용한 언맵핑 요청을 처리하기 위한 예시적 프로세스의 플로차트이다;
도 6은 본 발명의 다양한 실시예에 따른 비트맵을 이용한 판독 요청을 처리하기 위한 예시적 프로세스의 플로차트이다;
도 7은 본 발명의 다양한 실시예에 따른 트리(tree)를 업데이트하기 위한 예시적 프로세스의 플로차트이다;
도 8은 본 발명의 다양한 실시예에 따른 유효성 카운터(validity counter)를 업데이트하기 위한 예시적 프로세스의 플로차트이다;
도 9는 본 발명의 다양한 실시예에 따른 더 빠른 폐영역 회수(garbage collection)를 위한 예시적 프로세스의 플로차트이다;
비휘발성 메모리("NVM")를 갖는 시스템용의 논리 블록 주소("LBA") 비트맵 사용을 위한 시스템 및 방법이 제공된다. 시스템의 휘발성 메모리에 저장될 수 있는 비트맵은, 하나 이상의 논리 주소(예를 들어, LBA)의 맵핑 상태를 저장할 수 있다. 비트맵의 각 엔트리는 하나 이상의 LBA에 대응한다.
비트맵을 이용하여, 시스템의 NVM 인터페이스는 NVM에 액세스하지 않고도 LBA의 맵핑 상태를 판정할 수 있다. 또한, NVM 인터페이스는 최소한의 NVM 액세스를 동반하며 LBA의 맵핑 상태를 업데이트할 수 있다. 예를 들어, 특정 LBA를 언맵핑하라는 파일 시스템으로부터의 요청의 수신에 응답하여, NVM 인터페이스는 비트 맵의 대응하는 엔트리의 맵핑 상태를 "맵핑됨"으로부터 "언맵핑됨"으로 변경할 수 있다. NVM 액세스 횟수를 줄임으로써, 시스템은 폐영역 회수 프로세스의 트리거링을 피할 수 있어서, 전체 시스템 성능을 개선할 수 있다.
비트맵을 업데이트함으로써 LBA의 맵핑 상태를 변경한 후에, NVM 인터페이스는, 역시 휘발성 메모리에 저장된 적어도 하나의 유효성 카운터를 업데이트하기 위하여 휘발성 메모리에 저장된 트리를 참조할 수 있다. 그러나, LBA와 NVM의 물리적 주소 사이의 맵핑을 포함할 수 있는 트리는 LBA의 언맵핑을 반영하기 위해 반드시 업데이트될 필요는 없다. 대신에, NVM 인터페이스는 트리 메모리 사용이 유익하게도 감소될 때에만 트리 업데이트를 수행할 것을 결정할 수 있다.
NVM 인터페이스가 트리를 참조함으로써 적어도 하나의 유효성 카운터를 업데이트할 수 없는 상황에서는, NVM 인터페이스는 LBA와 연관된 인덱스 페이지를 NVM으로부터 로딩할 필요성이 있을 수도 있다. NVM 인터페이스는 인덱스 페이지를 휘발성 메모리 내에 읽어들일 필요가 있지만, NVM 인터페이스는 반드시 인덱스 페이지를 업데이트하고 NVM 내에 다시 프로그램할 필요는 없다. 순 결과(net result)는, 수행될 필요가 있는 인덱스 페이지 동작의 총 수가 줄어들고, 폐영역 회수를 피할 수 있다는 것이다.
일부 실시예들에서, 비트맵은 폐영역 회수 프로세스를 개선할 수 있다. 특히, 비트맵을 이용하여, NVM 인터페이스는 NVM에 저장된 사용자 데이터에 관한 폐영역 회수를 수행하면서 이루어져야 할 필요성이 있는 인덱스 페이지 액세스 수를 줄일 수 있다.
도 1은 전자 장치(100)의 블록도를 나타낸다. 일부 실시예들에서, 전자 장치(100)는, 휴대형 미디어 재생기, 셀룰러 전화, 포켓 사이즈 개인용 컴퓨터, PDA(personal digital assistance), 데스크톱 컴퓨터, 랩탑 컴퓨터, 및 기타의 임의의 적절한 유형의 전자 장치이거나 이들을 포함할 수 있다.
전자 장치(100)는 시스템-온-칩("SoC")(110) 및 비휘발성 메모리("NVM")(120)를 포함할 수 있다. 비휘발성 메모리(120)는 부동 게이트 또는 전하 포획 기술에 기초한 NAND 플래시 메모리, NOR 플래시 메모리, 소거가능한 프로그래머블 판독 전용 메모리("EPROM"), 전기적으로 소거가능한 프로그래머블 판독 전용 메모리("EEPROM"), 강유전성 RAM("FRAM"), 자기저항 RAM("MRAM"), 또는 이들의 임의의 조합을 포함할 수 있다.
NVM(120)은 가장 작은 소거가능한 단위인 "블록"으로 조직화될 수 있으며, 또한, 프로그램 또는 판독될 수 있는 가장 작은 단위인 "페이지"로 조직화될 수 있다. 일부 실시예에서, NVM(120)은 복수의 집적 회로를 포함할 수 있으며, 각각의 집적 회로는 복수의 블록을 가질 수 있다. 대응하는 집적 회로로부터의 메모리 위치(예를 들어, 블록이나 블록의 페이지)는 "수퍼 블록"을 형성할 수 있다. NVM(120)의 각 메모리 위치(예를 들어, 페이지나 블록)는 물리 주소(예를 들어, 물리 페이지 주소나 물리 블록 주소)를 이용하여 참조될 수 있다.
이제 도 2를 참조하면, 논리 주소를 물리 페이지에 맵핑하기 위한 예시적 메모리 맵핑 아키텍쳐(200)가 도시되어 있다. 아키텍쳐(200)는 휘발성 메모리(점선의 좌측에 도시)와 비휘발성 메모리(점선의 우측에 도시)로 분할된다. 즉, 룩업 테이블(202), 인덱스 테이블 캐시(204), 트리(210), 및 비트맵(212)은 휘발성 메모리(예를 들어, 도 1의 메모리(114))에 저장되는 반면, 인덱스 테이블(206) 및 데이터 페이지(208)는 비휘발성 메모리(예를 들어, 도 1의 NVM(120))에 저장된다.
NVM의 하나 이상의 페이지는, SoC(예를 들어, 도 1의 SoC(110)) 또는 장치(예를 들어, 도 1의 장치(100))의 컴포넌트들의 일반 동작과 연관된 데이터를 저장하는데 이용될 수 있는 데이터 페이지(208)일 수 있다. 일부 실시예들에서, 블록 콘텐츠 테이블("TOC", block table-of-contents)은 각 데이터 블록과 연관될 수 있다. 예를 들어, 도 2에 도시된 예에서, 블록 TOC(1)는 데이터 블록(1)과 연관되고, 블록 TOC(N)는 데이터 블록(N)과 연관될 수 있는 등등이다. 각 블록 TOC는 대응하는 데이터 블록에 저장될 수 있고, 데이터 블록의 데이터 페이지를 대응하는 논리 주소로 맵핑하는 정보를 포함할 수 있다.
또한, 인덱스 테이블(206)을 저장하기 위해 NVM의 하나 이상의 페이지가 이용될 수 있다. 논리 섹터가 물리 페이지에 직접 맵핑되는 실시예에서, 논리-대-물리 맵핑은 인덱스 테이블(206)에 저장될 수 있다. 본 명세서에서 사용될 때, "논리-대-물리 맵핑"은, 데이터 페이지의 하나 이상의 논리 주소(예를 들어, 논리 섹터)와 물리 주소(예를 들어, 물리 페이지 주소나 가상 블록 주소) 사이의 맵핑일 수 있다. 예를 들어, 인덱스 테이블(206)은 NVM의 데이터 페이지(208)의 물리 주소를 유지할 수 있다.
일부 경우에, 인덱스 테이블(206)은 복수의 인덱스 페이지(1-N)를 포함할 수 있고, 각각의 인덱스 페이지는 논리 주소를 데이터 페이지(208)의 하나 이상의 물리 주소에 맵핑할 수 있다(예를 들어, 하나 이상의 논리-대-물리 맵핑을 저장). 예를 들어, 도 2에 도시된 바와 같이, 인덱스 테이블(206)의 인덱스 페이지(1)는 논리 주소를 데이터 블록(1) 및 데이터 블록(N)의 하나 이상의 페이지에 맵핑할 수 있다.
다시 도 1을 참조하면, 시스템 온 칩(110)은, SoC 제어 회로(112), 메모리(114), 및 NVM 인터페이스(118)를 포함할 수 있다. SoC 제어 회로(112)는, SoC(110) 및 SoC(110)나 장치(100)의 다른 컴포넌트들의 일반 동작 및 기능을 제어할 수 있다. 예를 들어, 사용자 입력 및/또는 애플리케이션이나 운영 체제의 명령에 응답하여, SoC 제어 회로(112)는 NVM(120)으로부터 데이터를 얻거나 이에 데이터를 저장하기 위해 NVM 인터페이스(118)에 판독이나 기록 요청을 내릴 수 있다. 명료성을 위해, SoC 제어 회로(112)가 저장이나 검색을 요청하는 데이터는, 그 데이터가 사용자나 사용자 애플리케이션과 직접 연관되지 않더라도, "사용자 데이터"라고 말할 수 있다. 오히려, 사용자 데이터는, (예를 들어, 애플리케이션이나 운영 체제를 통해) SoC 제어 회로(112)에 의해 발생되거나 얻어진 임의의 적절한 시퀀스의 디지털 정보일 수 있다.
SoC 제어 회로(112)는, 하드웨어, 소프트웨어, 및 펌웨어의 임의 조합, 및 전자 장치(100)의 기능을 구동하도록 동작하는 임의의 컴포넌트, 회로 또는 로직을 포함할 수 있다. 예를 들어, SoC 제어 회로(112)는, NVM(120)이나 메모리(114)에 저장된 소프트웨어/펌웨어의 제어하에 동작하는 하나 이상의 프로세서를 포함할 수 있다.
메모리(114)는, (예를 들어, 정적 RAM("SRAM"), 동적 랜덤 액세스 메모리("DRAM"), 동기 동적 랜덤 액세스 메모리("SDRAM"), 더블 데이터 레이트("DDR") RAM)과 같은 랜덤 액세스 메모리("RAM"), 캐시 메모리, 판독 전용 메모리("ROM"), 또는 그 임의 조합과 같은 임의의 적절한 유형의 휘발성 메모리를 포함할 수 있다. 메모리(114)는, 비휘발성 메모리(120)로의 프로그래밍 또는 이로부터의 판독을 위한 사용자 데이터를 일시적으로 저장할 수 있는 데이터 소스를 포함할 수 있다. 일부 실시예들에서, 메모리(114)는 SoC 제어 회로(112)의 일부로서 구현된 임의의 프로세서에 대한 메인 메모리로서 동작할 수 있다.
일부 실시예들에서, 메모리(114)는 NVM 인터페이스(118)에 의해 그 연관된 동작을 수행하기 위해 이용될 수 있는 하나 이상의 데이터 구조를 저장할 수 있다. 예를 들어, 메모리(114)는 비트맵을 포함할 수 있다. 이것은, 휘발성 메모리가 비트맵(212)을 포함하고 있는 도 2에도 도시되어 있다.
비트맵은 하나 이상의 논리 주소(예를 들어, LBA)의 맵핑 상태(예를 들어, "맵핑됨" 또는 "언맵핑됨")를 저장할 수 있다. 예를 들어, LBA의 맵핑 상태가 "맵핑됨"이라면, NVM 인터페이스(118)는 그 LBA가 NVM(120)에 저장된 사용자 데이터와 현재 연관되어 있다고 판정할 수 있다. 대안으로서, 만일 LBA의 맵핑 상태가 "언맵핑됨"이라면, NVM 인터페이스(118)는 LBA가 이전에 사용자 데이터에 맵핑(그렇지만, 그 이후에 사용자 데이터가 삭제)되었거나, LBA가 임의의 사용자 데이터와 결코 연관된 적이 없었다고 판정할 수 있다.
비트맵은 임의의 적절한 시간에서 채워질 수 있다. 예를 들어, 일부 시스템에서는, 파일 시스템은, 시스템 부트업 동안에 어느 LBA가 언맵핑될지에 관한 정보를 제공할 수 있다. 예를 들어, 일단 파일 시스템이 마운트되고 나면, NVM 인터페이스(118)는 LBA의 맵핑 상태와 연관된 정보를 파일 시스템으로부터 수신할 수 있다. 이 정보의 수신 후에, NVM 인터페이스(118)는 이 정보를 이용하여 비트맵을 채울 수 있다. 맵핑 상태는 파일 시스템으로부터 자동으로 얻어질 수 있기 때문에, 전체 시스템 마운트 시간이 줄어들 수 있다. 그러나, 만일 파일 시스템이 부트업 동안에 어느 LBA가 언맵핑될지에 관한 정보를 제공하지 않는다면, NVM 인터페이스(118)는 NVM(120)을 스캐닝함으로써 맵핑 상태를 얻을 수 있다. 시스템 동작 동안에, 비트맵은 NVM 인터페이스(118)에 의해 동적으로 유지되고 이용될 수 있다.
비트맵은 예를 들어, 2MB와 같은 임의의 적절한 크기를 가질 수 있다. 비트맵에 할당되는 메모리의 양은 하나 이상의 인자에 의존할 수 있다. 예를 들어, 더 작은 비트맵은 다른 정보를 저장하기 위해 더 많은 공간이 메모리(114)에서 이용가능하게 하는 것을 허용할 수 있다. 대조적으로, 더 큰 비트맵은 비트맵의 각 엔트리가 하나의 LBA에 대응하도록 허용할 수 있고, 이것은 각 LBA의 맵핑 상태에 관한 최종 정보를 NVM 인터페이스(118)에 제공할 수 있다. 어느 경우든, 비트맵은 맵핑 상태 외에도 물리 및/또는 논리 주소를 저장할 것을 필요로 하는 상이한 데이터 구조(예를 들어, 테이블)에 비해 더 작은 크기를 가질 수 있다. 도 4a 내지 도 4c와 관련하여 다양한 유형의 비트맵이 더 상세히 설명될 것이다.
또 다른 예로서, 메모리(114)는, 복수의 트리 엔트리를 포함할 수 있는 트리를 포함할 수 있다. 예를 들어, 도 2에 도시된 바와 같이, 트리(210)는 논리 주소(예를 들어, LBA)와 NVM(예를 들어, 도 1의 NVM(120))의 대응하는 물리 주소 사이의 맵핑을 제공할 수 있다. 트리(210)는, 예를 들어 b-트리 또는 b*-트리와 같은, 트리의 특정 엔트리에 대한 검색 시간을 개선하는 트리 구조를 가질 수 있다. 일부 경우에는, 트리(210)는 휘발성 메모리에서 미리결정된 양의 트리 메모리를 할당받을 수 있다.
역시 또 다른 예로서, 메모리(114)는 룩업 테이블 및/또는 인덱스 테이블 캐시를 포함할 수 있다. 예를 들어, 도 2에 도시된 바와 같이, 룩업 테이블(202)은 인덱스 테이블(206)의 위치(예를 들어, 물리 주소)를 유지할 수 있다. 특히, 룩업 테이블(202)은 인덱스 테이블(206)의 일부를 형성하는 인덱스 페이지들(1 내지 N)의 논리-대-물리 맵핑을 유지할 수 있다. 또한, 룩업 테이블(202)은 또한 인덱스 테이블 캐시(204)의 메모리 위치(들)을 저장할 수 있다.
인덱스 테이블 캐시(204)는 더 빠른 판독을 제공하기 위하여 최근에 기입되거나 액세스된 논리 주소(예를 들어, 논리 섹터)의 물리 주소를 유지할 수 있다. 즉, 캐시(204)는, 현재 프로그램중이거나 최근에 프로그램된 데이터 페이지(208)에 대한 논리-대-물리 맵핑을 유지할 수 있다. 주기적 기반으로, 인덱스 테이블 캐시(204)에 저장된 정보는 NVM의 인덱스 페이지들(1-N)로 흘러갈(flush out) 수 있다.
다시 도 1을 참조하면, NVM 인터페이스(118)는, SoC 제어 회로(112)와 NVM(120) 사이에서 인터페이스 또는 구동기로서 동작하도록 구성된 하드웨어, 소프트웨어, 및/또는 펌웨어의 임의의 적절한 조합을 포함할 수도 있다. NVM 인터페이스(118)에 포함된 임의의 소프트웨어 모듈의 경우, 대응하는 프로그램 코드가 NVM(120) 또는 메모리(114)에 저장될 수 있다.
NVM 인터페이스(118)는, SoC 제어 회로(112)가 NVM(120)에 액세스하고 NVM(120)의 메모리 위치들(예를 들어, 페이지, 블록, 수퍼 블록, 집적 회로)과 그 내부에 저장된 데이터(예를 들어, 사용자 데이터)를 관리하는 것을 허용하는 다양한 기능을 수행할 수 있다. 예를 들어, NVM 인터페이스(118)는, SoC 제어 회로(112)로부터의 판독이나 기록 요청을 해석하고, 웨어-레벨링(wear leveling)을 수행하며, NVM(120)의 버스 프로토콜과 호환되는 판독 및 프로그램 명령어를 생성할 수 있다.
NVM 인터페이스(118) 및 SoC 제어 회로(112)가 별개의 모듈로서 도시되어 있지만, 이것은 본 발명의 실시예들의 설명을 간소화하기 위한 의도일 뿐이다. 이들 모듈들은 하드웨어 컴포넌트, 소프트웨어 컴포넌트, 또는 양쪽 모두를 공유할 수 있다는 것을 이해하여야 한다. 예를 들어, SoC 제어 회로(112)는 NVM 인터페이스(118)를 위한 소프트웨어-기반의 메모리 구동기를 실행할 수 있다.
일부 실시예들에서, 전자 장치(100)는, NVM(120)과 NVM 인터페이스(118)의 일 부분 또는 모든 부분을 포함하는, 플래시 메모리 드라이브 또는 SD 카드와 같은 타겟 장치를 포함할 수 있다. 이들 실시예에서, SoC(110) 또는 SoC 제어 회로(112)는 타겟 장치에 대해 호스트 제어기로서 동작할 수 있다. 예를 들어, 호스트 제어기로서, SoC(110)는 타겟 장치에 판독 및 기록 요청을 내릴 수 있다.
도 3은 전자 장치(300)의 블록도로서, 다양한 실시예에 따른 전자 장치(100)(도 1)의 펌웨어, 소프트웨어, 및/또는 하드웨어 컴포넌트들의 일부를 더 상세히 나타내고 있다. 전자 장치(300)는 도 1과 관련하여 전술된 특징들 및 기능들 중 임의의 것을 가질 수 있으며, 그 반대도 마찬가지다. 도시된 바와 같이, 점선은 층들의 경계를 표시한다. 경계선 내에 해당하는 컴포넌트들의 도시는 단지 예시일 뿐이고, 하나 이상의 컴포넌트들이 상이한 층과 연계될 수 있음을 알 수 있다.
전자 장치(300)는, 파일 시스템(310), NVM 구동기(312), NVM 버스 제어기(316), 및 NVM(320)을 포함할 수 있다. 일부 실시예들에서, 파일 시스템(310) 및 NVM 구동기(312)는 소프트웨어 또는 펌웨어 모듈이고, NVM 버스 제어기(316) 및 NVM(320)은 하드웨어 모듈일 수 있다. 따라서, 이들 실시예들에서, NVM 구동기(312)는 NVM 인터페이스(318)의 소프트웨어 또는 펌웨어 양태를 나타내고, NVM 버스 제어기(316)는 NVM 인터페이스(318)의 하드웨어 양태를 나타낼 수 있다.
파일 시스템(310)은, 파일 할당 테이블("FAT") 파일 시스템 또는 계층적 파일 시스템 플러스("HFS+")와 같은 임의의 적절한 유형의 파일 시스템을 포함할 수 있으며, 전자 장치(300)의 운영 체제의 일부(예를 들어, 도 1의 SoC 제어 회로(112)의 일부)일 수 있다. 일부 실시예들에서, 파일 시스템(310)은, 페이지의 논리-대-물리 맵핑을 제공하는 플래시 파일 시스템을 포함할 수 있다. 이들 실시예들에서, 파일 시스템(310)은 이하에서 논의되는 NVM 구동기(312)의 기능들 중 일부 또는 전부를 수행할 수 있으므로, 파일 시스템(310) 및 NVM 구동기(312)는 별개의 모듈일 수도 있고 아닐 수도 있다.
파일 시스템(310)은 애플리케이션 및 운영 체제를 위한 파일 및 폴더 구조를 관리할 수 있다. 파일 시스템(310)은, 전자 장치(300)에서 실행 중인 애플리케이션이나 운영 체제의 제어하에서 동작할 수 있으며, 애플리케이션이나 운영 체제가 NVM(320)에 정보가 저장되거나 이로부터 정보를 판독할 것을 요청할 때 NVM 구동기(312)에 기록 및 판독 요청을 제공할 수 있다. 각각의 판독 또는 기록 요청과 함께, 파일 시스템(310)은, 논리 페이지 주소 또는 페이지 오프셋을 갖는 논리 블록 주소와 같은, 사용자 데이터가 판독되거나 기록되어져야 하는 장소를 나타내는 논리 주소를 제공할 수 있다.
파일 시스템(310)은 NVM(320)과 직접 호환되지 않는 NVM 구동기(312)에 판독 및 기록 요청을 제공할 수 있다. 예를 들어, 논리 주소는 하드-드라이브-기반의 시스템에서 전형적인 규약이나 프로토콜을 이용할 수 있다. 하드-드라이브-기반의 시스템은, 플래시 메모리와는 달리, 먼저 블록 소거를 수행하지 않고도 메모리 위치를 덮어쓰기할 수 있다. 게다가, 하드 드라이브는 장치의 수명을 증가시키는 웨어 레벨링을 필요로 하지 않을 수 있다. 따라서, NVM 인터페이스(318)는, 파일 시스템 요청을 처리하고 NVM(320)에 적합한 방식으로 기타의 관리 기능을 수행하기 위해 메모리-특유의, 벤더-특유의, 또는 양쪽 모두에 해당하는 임의의 기능을 수행할 수 있다.
NVM 구동기(312)는 변환 계층(314)을 포함할 수 있다. 일부 실시예들에서, 변환 계층(translation layer, 314)은 플래시 변환 계층("FTL")이거나 이를 포함할 수 있다. 기록 요청시에, 변환 계층(314)은 제공된 논리 주소를 NVM(320) 상의 자유로운 소거된 물리 위치에 맵핑할 수 있다. 판독 요청시에, 변환 계층(314)은 요청된 데이터가 저장되어 있는 물리 주소를 결정하기 위해, 제공된 논리 주소를 이용할 수 있다. 각각의 NVM은 NVM의 크기 또는 벤더에 따라 상이한 레이아웃을 가질 수 있기 때문에, 이 맵핑 동작은 메모리 및/또는 벤더마다 특유할 수 있다.
논리-대-물리 주소 맵핑 외에도, 변환 계층(314)은 폐영역 회수("GC") 및 웨어 레벨링과 같은, 플래시 변환 계층에 전형적일 수 있는 기타 임의의 적절한 기능을 수행할 수 있다.
일부 실시예들에서, NVM 구동기(312)는 NVM 액세스 요청(예를 들어, 프로그램, 판독, 및 소거 요청)을 완료하기 위해 NVM 버스 제어기(316)와 인터페이싱할 수 있다. 버스 제어기(316)는, NVM(320)에 대한 하드웨어 인터페이스로서 동작할 수 있으며, NVM(320)의 버스 프로토콜, 데이터 레이트, 및 기타의 사양을 이용하여 NVM(320)과 통신할 수 있다.
NVM 인터페이스(318)는, 때때로 여기서는 "메타데이터"라고 불리는, 메모리 관리 데이터에 기초하여 NVM(320)을 관리할 수 있다. 메타데이터는 NVM 구동기(312)에 의해 생성되거나, NVM 구동기(312)의 제어하에 동작하는 모듈에 의해 생성될 수 있다. 예를 들어, 메타데이터는, 논리 주소와 물리 주소간의 맵핑 관리, 불량 블록 관리, 웨어 레벨링, 데이터 오류를 검출하고 보정하는데 이용되는 ECC 데이터, 또는 그 임의의 조합에 이용되는 임의의 정보를 포함할 수 있다. 메타데이터는, 논리 주소와 같은, 사용자 데이터와 함께 파일 시스템(310)에 의해 제공된 데이터를 포함할 수 있다. 따라서, 일반적으로, "메타데이터"란, 사용자 데이터에 대한 또는 그에 관한 임의의 정보로서 일반적으로 비휘발성 메모리의 동작 및 메모리 위치를 관리하는데 이용되는 정보를 말한다.
NVM 인터페이스(318)는 NVM(320)에 메타데이터를 저장하도록 구성될 수 있다. 일부 실시예들에서, NVM 인터페이스(318)는, 사용자 데이터가 저장되는 메모리 위치(예를 들어, 페이지)와 동일한 메모리 위치에 사용자 데이터와 연관된 메타데이터를 저장할 수 있다. 예를 들어, NVM 인터페이스(318)는, 사용자 데이터, 연관된 논리 주소, 및 사용자 데이터에 대한 ECC 데이터를 NVM(320)의 하나 이상의 메모리 위치에 저장할 수 있다. NVM 인터페이스(318)는 또한, 사용자 데이터에 대한 기타 유형들의 메타데이터를 동일한 메모리 위치에 저장할 수 있다.
NVM 인터페이스(318)는 논리 주소를 저장하여, NVM(320)의 파워-업시에 또는 NVM(320)의 동작 동안에, 전자 장치(300)가 그 위치에 어떤 데이터가 존재하는지를 판정할 수 있도록 할 수 있다. 특히, 파일 시스템(310)은 그 물리 주소가 아니라 그 논리 주소에 따라 사용자 데이터를 참조할 수 있기 때문에, NVM 인터페이스(318)는 사용자 데이터와 논리 주소를 함께 저장하여 그들의 연관을 유지할 수 있다. 이런 방식으로, NVM(320) 내의 물리-대-논리 맵핑을 유지하는 별개의 테이블이 오래 되더라도(outdated), NVM 인터페이스(318)는, 예를 들어, 전자 장치(300)의 파워-업 또는 리부트시에 적절한 맵핑을 여전히 결정할 수 있다.
전술된 바와 같이, 휘발성 메모리에 저장될 수 있는 비트맵은 하나 이상의 LBA의 맵핑 상태를 저장할 수 있다. 또한, 비트맵의 각 엔트리는 하나 이상의 LBA에 대응할 수 있다. 예를 들어, 이제 도 4a 내지 도 4c를 참조하면, 다양한 예시적 비트맵이 도시되어 있다. 당업자라면, 비트맵은 임의의 적절한 개수의 엔트리를 포함할 수 있다는 것을 이해할 것이다. 그러나, 간소화를 위해, 도 4a 내지 도 4c의 각각의 비트맵은 단 8개의 엔트리만을 포함하는 것으로 도시되어 있다.
먼저 도 4a를 참조하면, 비트맵(400)은 엔트리(400A 내지 400H)를 포함할 수 있다. 비트맵(400)의 각 엔트리는 단일의 LBA에 대응할 수 있다. 따라서, 예를 들어, 엔트리들(400A 내지 400H) 각각은, 각각 LBA(0-7)에 대응할 수 있다. 또한, 각 엔트리는 한 개 비트에 대응할 수 있다. 즉, 비트맵(400)의 각 엔트리는 2진 값(예를 들어, 0 또는 1)을 저장할 수 있으며, 각각의 2진 값은 "언맵핑됨" 또는 "맵핑됨"의 맵핑 상태에 대응할 수 있다. 데이터가 LBA에 프로그램되고 대응하는 비트맵 엔트리가 "언맵핑됨"의 맵핑 상태를 가질 때, 비트맵 엔트리는 "맵핑됨"의 맵핑 상태를 반영하도록 업데이트될 수 있다. 그러나, 대응하는 비트맵 엔트리가 이미 "맵핑됨"의 맵핑 상태를 가진다면, LBA가 이전에 저장되었던 블록의 유효성 카운터가 감소될 수 있다.
비트맵(400)의 각 엔트리는 단일 LBA에 대응하기 때문에, 비트맵(400)은 특정 LBA가 맵핑되어 있는지 또는 언맵핑되어 있는지에 관한 최종 정보를 NVM 인터페이스(예를 들어, 도 1의 NVM 인터페이스(118) 또는 도 3의 NVM 인터페이스(318))에 제공할 수 있다. 대안적 구성에서, LBA로의 엔트리의 입도(granularity)는, 비트맵의 각 엔트리가 복수의 LBA(예를 들어, 8, 16, 또는 32 LBA들)에 대응할 수 있도록 감소될 수 있다. 이러한 구성은 시스템의 각 LBA에 대한 최종 맵핑 상태를 제공하지 못할 수도 있지만, 이들 비트맵들은 더 작을 수 있어서(예를 들어, 2 MB와는 대조적으로 256 kB), 메모리(예를 들어, 도 1의 메모리(114))에서 추가 공간을 절약한다. 예를 들어, 더 큰 트리(예를 들어, 도 2의 트리(210))를 저장하는 것과 같은 다른 목적을 위해 추가의 메모리 공간이 이용될 수 있다.
다른 실시예들에서, 비트맵의 각 엔트리는 복수의 LBA에 대응할 수 있다. 예를 들어, 이제 도 4b를 참조하면, 비트맵(402)은 엔트리들(402A 내지 402H)을 포함할 수 있으며, 각 엔트리는 8개의 LBA와 연관될 수 있다. 또한, 각 엔트리는 여전히 한 개 비트에 대응할 수 있다. 즉, 각 엔트리는 2진 값을 저장할 수 있으며, 각각의 2진 값은 "모두 맵핑됨"/"모두 언맵핑됨" 또는 "알려지지 않음"의 맵핑 상태에 대응할 수 있다. 예를 들어, 도 4b에 도시된 바와 같이, 엔트리가 "예" 라벨을 가진다면, 그 엔트리에 대응하는 모든 LBA들은, 비트맵(402)이 구성된 방식에 따라, 모두 맵핑됨 또는 모두 언맵핑됨 중 어느 하나인 것으로 간주될 수 있다. 대조적으로, 엔트리가 "혼합(Mix)" 라벨을 가진다면, 그 엔트리에 대응하는 LBA들의 맵핑 상태는 "알려지지 않음"인 것으로 간주될 수 있다. 따라서, 그 엔트리에 대응하는 하나 이상의 LBA들은 언맵핑될 수 있는 반면, 나머지 LBA들은 맵핑될 수 있다.
이제 도 4c를 참조하면, 비트맵(404)은 엔트리들(404A 내지 404H)을 포함할 수 있으며, 각 엔트리는 또한 8개의 LBA에 대응할 수 있다. 이 경우, 그러나, 각 엔트리는 복수개의 비트(예를 들어, 2비트)를 저장할 수 있다. 결과적으로, 비트맵(404)의 각 엔트리는 3개 값들 중 하나에 대응할 수 있으며, 각 값은 적절한 맵핑 상태에 대응할 수 있다(예를 들어, "맵핑됨", "언맵핑됨", 또는 "혼합"). 예를 들어, 도 4c에 도시된 바와 같이, 엔트리가 "맵핑됨" 라벨을 가진다면, 그 엔트리에 대응하는 모든 LBA들은 맵핑될 수 있다. 마찬가지로, 엔트리가 "언맵핑됨" 라벨을 가진다면, 그 엔트리에 대응하는 모든 LBA들은 언맵핑될 수 있다. 대조적으로, 엔트리가 "혼합" 라벨을 가진다면, 그 엔트리에 대응하는 하나 이상의 LBA들은 언맵핑될 수 있는 반면, 나머지 LBA들은 맵핑될 수 있다.
비트맵(402 및 404)의 경우, 엔트리의 맵핑 상태가 알려지지 않음 상태라고 NVM 인터페이스가 판정하면(예를 들어, NVM 인터페이스가 엔트리에 대해 "알려지지 않음", 또는 "혼합" 값을 만나면), NVM 인터페이스는 그 엔트리와 연관된 각 LBA의 맵핑 상태를 별도로 판정 및/또는 업데이트할 필요가 있다. 예를 들어, NVM 인터페이스는, 예를 들어, 트리(도 2의 트리(210)) 및/또는 하나 이상의 인덱스 페이지(예를 들어, 도 2의 인덱스 페이지들(1-N))과 같은, 시스템의 하나 이상의 데이터 구조를 참조 및 업데이트할 수 있다. 그 결과, 비트맵에서 "알려지지 않음" 또는 "혼합" 값들의 개수가 증가함에 따라 LBA의 맵핑 상태를 판정하는데 대해 비트맵이 덜 유용해질 수 있다.
또한, "맵핑됨" 엔트리와 연관된 LBA가 이제 언맵핑되면, 그 엔트리는 "알려지지 않음" 또는 "혼합"의 맵핑 상태를 가지도록 업데이트될 필요가 있을 것이다. 그 결과, LBA의 맵핑 상태를 계속 모니터링하기 위하여, NVM 인터페이스는 LBA의 변경된 맵핑 상태를 반영하기 위해 트리 및/또는 하나 이상의 인덱스 페이지를 업데이트할 필요가 있을 것이다.
따라서, 비트맵의 입도는, 예를 들어, 현재의 메모리 가용성, 소정의 입도에 대해 각 LBA의 맵핑 상태를 최종적으로 판정하는데 요구되는 듀티 사이클, 시스템 사용 모델, 및/또는 그 임의 조합과 같은, 하나 이상의 요인에 기초하여 결정될 수 있다. 시스템 사용 모델은, 기입 및/또는 삭제되고 있는 파일의 크기를 포함할 수 있다. 예를 들어, 만일 시스템이 큰 파일들을 순차적으로 기입 및 삭제하고 있다면, 비트맵에 대해 LBA로의 엔트리의 더 거친 입도가 선택될 수 있다. 대조적으로, 시스템이 작은 파일들 기록 및 삭제하고 있다면, 각 LBA에 대해 충분한 정보를 제공하기 위하여 LBA로의 엔트리의 더 미세한 입도가 선택될 수 있다.
일부 실시예들에서, NVM 인터페이스는 시스템이 동작하고 있는 동안 비트맵의 입도를 동적으로 조정할 수 있다(예를 들어, 소정 레벨에서 알려지지 않음 상태의 빈도에 기초하여 각 비트맵 엔트리의 범위를 증가 또는 감소). 예를 들어, NVM 인터페이스는, 각 엔트리가 하나의 LBA에 대응하도록 비트맵을 먼저 초기화할 수 있다. 그 다음, 시스템이 계속 동작함에 따라, NVM 인터페이스는, 알려지지 않음 상태를 갖는 엔트리의 수가 미리결정된 임계치보다 작다면(예를 들어, 비트맵 엔트리들의 50% 미만이 알려지지 않음 상태를 가짐) 각 엔트리에 대응하는 LBA의 수를 증가시킬 수 있다. 다른 실시예들에서, NVM 인터페이스는 비트맵의 각 엔트리가 고정된 미리결정된 개수의 LBA에 대응하도록(예를 들어, 각 엔트리는 하나의 LBA에 대응하거나, 각 엔트리가 32개의 LBA에 대응하도록) 비트맵을 초기화할 수 있다.
시스템은 다양한 시나리오에서 LBA들의 맵핑 상태를 모니터링하기 위해 비트맵을 이용할 수 있다. 종래에는, 시스템이 LBA의 맵핑 상태를 판정하기 위하여, 특히 시스템이 트리를 유지하지 않거나 LBA의 맵핑 상태가 트리에 의해 부분적으로만 포착되는 경우에는, 시스템은 NVM(예를 들어, 도 1의 NVM(120) 또는 도 3의 NVM(320))을 참조할 필요가 있다. 예를 들어, 하나 이상의 LBA를 언맵핑하기 위하여, 시스템은 먼저, NVM에 저장된 하나 이상의 인덱스 페이지(예를 들어, 도 2의 인덱스 페이지들(1-N))를 메모리(예를 들어, 도 1의 메모리(114))에 저장된 인덱스 테이블 캐시 내(예를 들어, 도 2의 인덱스 테이블 캐시(204))에 읽어들일 필요가 있다. 그 다음, 인덱스 페이지들은 하나 이상의 LBA의 언맵핑을 반영하기 위해 인덱스 테이블 캐시에서 업데이트될 수 있다(예를 들어, 연관된 물리 주소를 디폴트 값으로 대체함으로써). 나중에, 업데이트된 인덱스 페이지들은 NVM에 다시 프로그램될 수 있다. 그러나, 이들 추가의 프로그래밍 동작은, NVM의 폐영역 회수를 너무 일찍 트리거링하여, 시스템 성능에 부정적 영향을 줄 수 있다.
LBA의 맵핑 상태가 트리에 의해 완전히 포착되는 다른 시스템에서, 시스템은 LBA를 언맵핑하기 위해 트리를 업데이트할 필요가 있을 수 있다. 후속해서, 트리의 하나 이상의 부분(예를 들어, 엔트리)은, 일단 트리 메모리 사용이 미리결정된 임계치를 초과한다고 판정되면, 플래트닝(flattened)될 필요가 있다. 그러나, 플래트닝 동작은 또한, NVM에 관한 추가의 동작을 포함할 수 있는데, 이것은 플래트닝된 엔트리들에 대응하는 데이터는 NVM에서 재-프로그램될 필요가 있을 수 있기 때문이다. 이들 동작들은 나중에 폐영역 회수를 트리거링할 수 있다.
또 다른 예로서, 종래의 시스템에서 LBA를 판독하기 위하여, NVM에 저장된 인덱스 페이지가 참조될 필요가 있을 수 있다(예를 들어, 특히 인덱스 페이지가 도 2의 인덱스 테이블 캐시(204)와 같은 인덱스 테이블 캐시에 저장되지 않은 경우). 따라서, 시스템은, LBA가 맵핑되어 있는지 또는 언맵핑되어 있는지를 판정할 수 있기 이전에 메모리(예를 들어, 도 1의 메모리(114)) 내에 전체 인덱스 페이지를 읽어들일 필요가 있을 수 있다.
따라서, 메모리(예를 들어, 도 1의 메모리(114))에 저장되어 있는 비트맵(예를 들어, 각각 도 4a 내지 도 4c의 비트맵(400, 402, 또는 404)에 의존함으로써, NVM 인터페이스(예를 들어, 도 1의 NVM 인터페이스(118) 또는 도 3의 NVM 인터페이스(318))는 NVM에 액세스할 필요가 없이 LBA의 맵핑 상태를 판정할 수 있다. 또한, NVM 인터페이스는 최소한의 NVM 액세스를 동반하며 LBA의 맵핑 상태를 업데이트할 수 있다. NVM 액세스 횟수를 줄임으로써, 시스템은 폐영역 회수 프로세스의 트리거링을 피할 수 있어서, 전체 시스템 성능을 개선할 수 있다. 예를 들어, 이제 5 및 도 6을 참조하면, 예시적 프로세스의 플로차트들이 본 발명의 다양한 실시예에 따라 도시되어 있다.
먼저 도 5를 참조하면, 비트맵을 이용하여 언맵핑 요청을 처리하기 위한 프로세스(500)가 도시되어 있다. 프로세스(500)는 단계(502)에서 시작하여, 단계(504)에서, NVM 인터페이스는 복수의 LBA의 맵핑 상태를 휘발성 메모리(예를 들어, 도 1의 메모리(114))에 저장된 비트맵(예를 들어, 각각 도 4a 내지 도 4c의 비트맵(400, 402, 또는 404))에 저장할 수 있다. 예를 들어, 앞서 논의된 바와 같이, NVM 인터페이스는 시스템 부트업 동안에 또는 NVM(예를 들어, 도 1의 NVM(120) 또는 도 3의 NVM(320))의 스캐닝을 통해 파일 시스템(예를 들어, 도 3의 파일 시스템(310))으로부터 맵핑 상태를 얻을 수 있다.
단계(506)에서, NVM 인터페이스는 LBA를 언맵핑하라는 요청을 파일 시스템으로부터 수신할 수 있다. 계속해서 단계(508)에서, NVM 인터페이스는, 단지 비트맵을 업데이트함으로써 LBA의 맵핑 상태를 언맵핑됨으로 변경할 수 있다. 예를 들어, 다시 도 4a를 참조하면, LBA 0를 언맵핑하라는 요청을 NVM 인터페이스가 수신하면, NVM 인터페이스는 엔트리(400A)의 맵핑 상태를 "맵핑됨"으로부터 "언맵핑됨"으로 변경할 수 있다. 비트맵을 업데이트함으로써 LBA의 맵핑 상태를 변경한 후에, NVM 인터페이스는 메모리(예를 들어, 도 1의 메모리(114))에 저장된 적어도 하나의 유효성 카운터를 업데이트할 수 있다. 이 적어도 하나의 유효성 카운터는 LBA와 연관된 수퍼 블록에 대응할 수 있다. 맵핑 상태의 변경 후에, 프로세스(500)는 단계(510)에서 종료할 수 있다.
이제 도 6을 참조하면, 비트맵을 이용하여 판독 요청을 처리하기 위한 프로세스(600)가 도시되어 있다. 프로세스(600)는 단계(602)에서 시작하여, 단계(604)에서, NVM 인터페이스(예를 들어, 도 1의 NVM 인터페이스(118) 또는 도 3의 NVM 인터페이스(318))는 LBA를 판독하라는 판독 요청을 파일 시스템(예를 들어, 도 3의 파일 시스템(310))으로부터 수신할 수 있다.
그 다음, 단계(606)에서, NVM 인터페이스는 LBA와 연관된 비트맵(예를 들어, 각각 도 4a 내지 도 4c의 비트맵(400, 402, 또는 404))의 엔트리를 참조할 수 있다. 계속하여 단계(608)에서, NVM 인터페이스는, LBA가 언맵핑되어 있음을 엔트리가 나타내고 있는지를 판정할 수 있다.
단계(608)에서, LBA가 언맵핑되어 있음을 엔트리가 나타내고 있다고 NVM 인터페이스가 판정하면, 프로세스(600)는 단계(610)로 이동할 수 있다. 예를 들어, 다시 도 4a를 참조하면, LBA 2를 판독하라는 요청을 NVM 인터페이스가 수신하면, NVM 인터페이스는 비트맵(400)의 엔트리(400C)를 참조함으로써 LBA 2가 언맵핑되어 있다고 판정할 수 있다.
단계(610)에서, NVM 인터페이스는 LBA가 연관된 사용자 데이터를 갖고 있지 않다는 것을 나타내는 정보를 파일 시스템에 전송할 수 있다. 따라서, NVM 인터페이스는 NVM에 저장된 인덱스 페이지를 참조할 필요없이 LBA의 맵핑 상태를 직접 판정할 수 있다. 프로세스(600)는 단계(612)에서 종료할 수 있다.
다시 단계(608)를 참조하면, 대신에 LBA가 언맵핑되어 있지 않음을 엔트리가 나타내고 있다고 NVM 인터페이스가 판정하면, 프로세스(600)는 단계(614)로 이동할 수 있다. 단계(614)에서, NVM 인터페이스는, LBA와 연관된 사용자 데이터의 위치를 파악하기 위하여 NVM(예를 들어, 도 1의 NVM(120) 또는 도 3의 NVM(320))의 인덱스 페이지를 참조할 수 있다. 따라서, 종래 시스템과는 대조적으로, NVM 인터페이스는 LBA가 맵핑되어 있음을 비트맵 엔트리가 나타내고 있다면 인덱스 페이지만을 참조할 필요가 있다.
사용자 데이터의 위치 파악 후, 단계(616)에서 NVM 인터페이스는 사용자 데이터를 파일 시스템에 전송할 수 있다. 프로세스(600)는 단계(612)에서 종료할 수 있다.
일부 실시예들에서, 비트맵을 업데이트함으로써 LBA의 맵핑 상태를 변경한 후에, NVM 인터페이스는 메모리(예를 들어, 도 1의 메모리(114))에 저장된 유효성 카운터를 업데이트하기 위해 트리를 참조할 수 있다. 유효성 카운터는 NVM의 각 수퍼 블록에 대해 유지될 수 있다. 일부 실시예에서, 유효성 카운터는 메모리에 테이블로서 저장될 수 있다.
NVM 인터페이스가 유효성 카운터의 업데이트시에 트리를 참조할 수 있지만, LBA 언맵핑을 반영하기 위해 트리가 반드시 업데이트될 필요는 없다. 이것은 파일 시스템에 의해 사용되는 LBA들의 맵핑 상태를 비트맵이 이미 저장하고 있기 때문이다. 대신에, NVM 인터페이스는 트리 메모리 사용이 유익하게도 감소될 때에만 트리 업데이트를 수행할 수 있다. 그렇지 않은 경우, NVM 인터페이스는 트리를 현재 상태로 둘 수 있다.
예를 들어, 이제 도 7을 참조하면, 트리(예를 들어, 도 2의 트리(210))를 업데이트하기 위한 예시적 프로세스(700)의 플로차트가 도시되어 있다. 프로세스(700)는 단계(702)에서 시작하여, 단계(704)에서, NVM 인터페이스(예를 들어, 도 1의 NVM 인터페이스(118) 또는 도 3의 NVM 인터페이스(318))는 LBA를 언맵핑하라는 요청을 수신할 수 있다.
그 다음, 단계(706)에서, NVM 인터페이스는 LBA가 언맵핑되어 있는지를 판정하기 위해 비트맵(예를 들어, 각각 도 4a 내지 도 4c의 비트맵(400, 402, 또는 404))을 참조할 수 있다. 단계(708)에서, LBA가 언맵핑되어 있다고 NVM 인터페이스가 판정하면, 프로세스(700)는 단계(710)로 이동할 수 있다.
일부 실시예들에서는, 단계(710)에서, NVM 인터페이스는 LBA가 이미 언맵핑되어 있음을 나타내는 정보를 파일 시스템(예를 들어, 도 3의 파일 시스템(310))에 전송할 수 있다. 따라서, 프로세스(600)(도 6)의 단계(610)에서, LBA가 언맵핑되어 있다고 판정하기 위해 어떠한 NVM 액세스도 필요하지 않다. 프로세스(700)는 단계(712)에서 종료할 수 있다.
다시 단계(708)를 참조하면, 그 대신 LBA가 언맵핑되어 있지 않다고 NVM 인터페이스가 판정하면, 프로세스(700)는 단계(714)로 이동할 수 있다. 단계(714)에서, NVM 인터페이스는 비트맵에서 LBA를 언맵핑할 수 있다.
계속해서 단계(716)에서, NVM 인터페이스는 트리를 참조함으로써 하나 이상의 유효성 카운터를 업데이트할 수 있다. 특히, NVM 인터페이스는 LBA에 대응하는 논리-대-물리 맵핑을 얻기 위하여 트리를 참조할 수 있다. 따라서, 예를 들어, NVM 인터페이스는 LBA에 대응하는 트리의 엔트리의 위치를 파악할 수 있으며, 그 엔트리를 이용하여, NVM 인터페이스는 LBA와 연관된 데이터를 어떤 수퍼 블록(들)이 저장하고 있는지를 판정할 수 있다. 이 판정을 행한 후에, NVM 인터페이스는 그 수퍼 블록(들)과 연관된 하나 이상의 유효성 카운터를 디크리멘트할 수 있다. 결과적으로, 트리도 역시 메모리에 저장되기 때문에, 언맵핑 프로세스는 메모리 액세스만을 포함한다.
그 다음, 단계(718)에서, NVM 인터페이스는, 업데이트에 의해 트리 메모리 사용이 감소할 때에만 언맵핑된 LBA를 반영하기 위해 트리를 업데이트할 수 있다. 즉, NVM 인터페이스는, 업데이트가 트리의 총 엔트리 수의 순 감소를 생성할 수 있는 경우에만 트리를 업데이트할 것을 결정할 수 있다. 예를 들어, 복수의 논리적으로 연속된 데이터 세그먼트들이 언맵핑되고 있다면(예를 들어, 복수의 작은 데이터베이스 엔트리들이 삭제되고 있다면), 트리 업데이트가 유익할 수 있다. 결과적으로, 이들 데이터 세그먼트들에 대응하는 엔트리들은 플래트닝(예를 들어, 병합)될 수 있고, 더 작은 트리가 생성될 수 있어서, 전체 트리 메모리 사용을 감소시킨다. 더 작은 트리는 또한, 트리 검색이 수행될 수 있는 속도를 개선시킬 수 있다.
대조적으로, 단지 작은 데이터 세그먼트만이 언맵핑되고 있다면, 트리 업데이트가 트리 맵핑을 찢어지게 할 경우에는(예를 들어, 더 큰 트리 엔트리의 중간부나 앞쪽이 언맵핑되고 있다면), 트리 업데이트가 수행되지 않을 수도 있다. 따라서, 이 트리 업데이트는 바람직하게 못하게 많은 수의 엔트리들을 생성할 수 있다.
일부 실시예들에서, NVM 인터페이스는, LBA에 대응하는 트리의 엔트리의 위치를 파악함으로써 언맵핑된 LBA를 반영하기 위해 트리를 업데이트할 수 있다. 엔트리의 위치를 파악한 후에, NVM 인터페이스는, LBA와 연관된 엔트리의 물리 주소(예를 들어, 물리 페이지 주소 또는 가상 블록 주소)를 미리결정된 토큰 값으로 업데이트할 수 있다.
NVM 인터페이스가 트리를 참조함으로써 LBA에 대한 논리-대-물리 맵핑을 결정할 수 없는 실시예들(예를 들어, 트리 메모리가 거의 소진되거나 시스템이 트리를 갖지 않아서, 논리-대-물리 맵핑이 트리에 저장되지 않는 경우)에서는, NVM 인터페이스는 NVM으로부터 휘발성 메모리로 인덱스 페이지를 로딩함으로써 논리-대-물리 맵핑을 결정할 필요가 있을 수도 있다. 이 시나리오는 NVM으로의 액세스를 포함하지만, NVM 액세스는 판독 동작으로 한정되지 않는다. 프로그램 동작과는 대조적으로, 판독 동작은 일반적으로 폐영역 회수를 트리거링하지 않는다.
예를 들어, 이제 도 8을 참조하면, 유효성 카운터를 업데이트하기 위한 예시적 프로세스(800)의 플로차트가 도시되어 있다. 프로세스(800)는 단계(802)에서 시작하여, 단계(804)에서, NVM 인터페이스(예를 들어, 도 1의 NVM 인터페이스(118) 또는 도 3의 NVM 인터페이스(318))는 LBA를 언맵핑하라는 요청을 수신할 수 있다.
계속해서 단계(806)에서, NVM 인터페이스는 휘발성 메모리(예를 들어, 도 1의 메모리(114))에 저장된 비트맵(예를 들어, 각각 도 4a 내지 도 4c의 비트맵(400, 402, 또는 404))에서 LBA를 언맵핑할 수 있다. 단계(806)는, 프로세스(700)(도 7)의 단계들(704 내지 714)과 같은, 추가 단계들을 포함할 수 있지만, 이들 추가 단계들은 간소화를 위해 프로세스(800)로부터 생략되었다.
단계(808)에서, NVM 인터페이스는, 휘발성 메모리(예를 들어, 도 1의 메모리(114))에 저장된 트리(예를 들어, 도 2의 트리(210))가 LBA에 대응하는 논리-대-물리 맵핑을 포함하는지를 판정할 수 있다. 단계(808)에서, 트리가 LBA에 대응하는 논리-대-물리 맵핑을 포함한다고 NVM 인터페이스가 판정하면, 프로세스(800)는 단계(810)로 이동할 수 있다.
단계(810)에서, NVM 인터페이스는 트리를 이용하여 LBA와 연관된 NVM의 하나 이상의 수퍼 블록을 판정할 수 있다.
그 다음, 단계(812)에서, NVM 인터페이스는 그 수퍼 블록과 연관된 적어도 하나의 유효성 카운터를 디크리멘트할 수 있으며, 여기서, 적어도 하나의 유효성 카운터는 휘발성 메모리에 저장된다. 트리를 이용하여 하나 이상의 수퍼 블록들이 판정되었기 때문에, NVM 인터페이스는 NVM에 저장된 인덱스 페이지의 판독이나 기입을 반드시 수행할 필요는 없다. 이것은 폐영역 회수가 트리거링될 확률을 줄이는데 도움이 될 수 있다. 프로세스(800)는 단계(814)에서 종료할 수 있다.
다시 단계(808)를 참조하면, 그 대신 트리가 LBA에 대응하는 논리-대-물리 맵핑을 포함하지 않는다고 NVM 인터페이스가 판정하면, 프로세스(800)는 단계(816)로 이동할 수 있다. 단계(816)에서, NVM 인터페이스는 LBA와 연관된 인덱스 페이지(예를 들어, 도 2의 인덱스 페이지들(1-N))를 NVM(예를 들어, 도 1의 NVM(120) 또는 도 3의 NVM(320))으로부터 로딩할 수 있다. 예를 들어, NVM 인터페이스는 인덱스 페이지를 인덱스 테이블 캐시(예를 들어, 도 2의 인덱스 테이블 캐시(204)) 내에 로딩할 수 있다.
계속해서 단계(818)에서, NVM 인터페이스는 로딩된 인덱스 페이지를 참조함으로써 LBA와 연관된 NVM의 하나 이상의 수퍼 블록을 판정할 수 있다. 그 다음, 단계(812)에서, NVM 인터페이스는 하나 이상의 수퍼 블록과 연관된 적어도 하나의 유효성 카운터를 디크리멘트할 수 있다. 따라서, 이 시나리오에서 NVM 인터페이스는 인덱스 페이지를 판독할 필요가 있지만, NVM 인터페이스는 인덱스 페이지를 업데이트하고 NVM 내에 다시 프로그램할 필요는 없다. 순 결과는, 인덱스 페이지 액세스의 총 수가 여전히 줄어들 수 있고, 폐영역 회수를 피할 수 있다는 것이다. 프로세스(800)는 단계(814)에서 종료할 수 있다.
논리-대-물리 맵핑이 트리에 유지되지는 않지만(또는 완전히 유지되지는 않지만), NVM에 저장된 인덱스 페이지(예를 들어, 도 2의 인덱스 페이지(1-N))에 유지되는 실시예들에서, 비트맵을 유지하는 것은 폐영역 회수 프로세스를 개선시킬 수 있다. 특히, 비트맵을 이용하여, NVM 인터페이스는 폐영역 회수 동안에 이루어져야 할 필요가 있는 인덱스 페이지 액세스 수를 줄일 수 있다.
예를 들어, 이제 도 9를 참조하면, 더 빠른 폐영역 회수를 위한 예시적 프로세스(900)의 플로차트가 도시되어 있다. 프로세스(900)는 단계(902)에서 시작하여, 단계(904)에서, NVM 인터페이스(예를 들어, 도 1의 NVM 인터페이스(118) 또는 도 3의 NVM 인터페이스(318))는 NVM의 데이터 블록(예를 들어, 도 2의 데이터 블록(1-N) 중 하나)에 관해 폐영역 회수를 수행할 것을 결정할 수 있다.
계속해서 단계(906)에서, NVM 인터페이스는 데이터 블록에 저장된 블록 TOC(예를 들어, 도 2의 블록 TOC(1-N) 중 하나)을 로딩할 수 있다. 그 다음, 단계(908)에서, NVM 인터페이스는 휘발성 메모리에 저장된 비트맵(예를 들어, 각각 도 4a 내지 도 4c의 비트맵(400, 402, 또는 404))을 그 블록 TOC와 비교할 수 있다.
단계(910)에서, NVM 인터페이스는, 그 비교에 기초하여 맵핑되는 데이터 블록의 논리 주소(예를 들어, LBA)의 서브셋을 결정할 수 있다. 예를 들어, 비트맵을 이용하여, NVM 인터페이스는 어느 LBA가 언맵핑되는지를 결정할 수 있다. 따라서, 이들 언맵핑되는 LBA들은 폐영역 회수 프로세스로부터 배제될 수 있다.
계속해서 단계(912)에서, NVM 인터페이스는 논리 주소의 서브셋과 연관된 데이터 블록에 저장된 사용자 데이터에 대해서만 폐영역 회수를 수행할 수 있다. 폐영역 회수는 시스템에 따라 다양한 방식으로 수행될 수 있다. 예를 들어, 시스템이 트리를 유지하지 않는 실시예들에서, NVM 인터페이스는 논리 주소의 서브셋에 대응하는 NVM에 저장된 인덱스 페이지만을 액세스함으로써 사용자 데이터의 위치를 파악할 수 있다. 따라서, 논리 주소의 서브셋의 각 논리 주소에 대해, NVM 인터페이스는 그 논리 주소와 연관된 인덱스 페이지(예를 들어, 도 2의 인덱스 페이지들(1-N) 중 하나)에 액세스할 수 있다. 그 다음, 인덱스 페이지에 기초하여, NVM 인터페이스는 논리 주소에 대응하는 데이터 블록의 물리 주소를 결정할 수 있다. 물리 주소의 결정 후에, NVM 인터페이스는 그 물리 주소로부터의 사용자 데이터를 NVM의 상이한 데이터 블록에 복사할 수 있다.
휘발성 메모리에 트리(예를 들어, 도 2의 트리(210))가 저장되는 실시예들에서, NVM 인터페이스는, 트리가 논리 주소들의 서브셋에 대한 논리-대-물리 맵핑을 포함하는지를 판정할 수 있다. 예를 들어, 논리 주소들의 서브셋의 각 논리 주소에 대해, NVM 인터페이스는 그 논리 주소에 대해 논리-대-물리 맵핑이 존재하는지를 판정하기 위해 트리를 참조할 수 있다. NVM 인터페이스가 그 논리 주소에 대해 논리-대-물리 맵핑이 존재하지 않는다고 판정하면, NVM 인터페이스는 그 논리 주소와 연관된 인덱스 페이지에 액세스할 수 있다. 그 다음, 전술된 바와 같이, 인덱스 페이지에 기초하여, NVM 인터페이스는 그 논리 주소에 대응하는 데이터 블록의 물리 주소를 결정할 수 있다. 물리 주소의 결정 후에, NVM 인터페이스는 그 물리 주소로부터의 사용자 데이터를 NVM의 상이한 데이터 블록에 복사할 수 있다.
그러나, NVM 인터페이스가 그 논리 주소에 대해 논리-대-물리 맵핑이 존재한다고 판정하면, NVM 인터페이스는 트리를 이용하여 그 논리 주소에 대응하는 데이터 블록의 물리 주소를 결정할 수 있다. 그 다음, NVM 인터페이스는 그 물리 주소로부터의 사용자 데이터를 NVM의 상이한 데이터 블록에 복사할 수 있다. 폐영역 회수를 수행한 후에, 프로세스(900)는 단계(914)에서 종료할 수 있다.
따라서, NVM에서 검사될 필요가 있는 논리 주소들의 개수를 줄이기 위해 비트맵을 이용함으로써, 폐영역 회수 동안에 수행될 필요가 있는 NVM 동작의 수가 대응적으로 줄어들 수 있다. 그 결과, 폐영역 회수 프로세스가 더욱 효율적으로 수행될 수 있다.
또한, 논리-대-물리 맵핑이 휘발성 메모리에 저장된 트리에 완전히 유지되는 실시예들에서, 비트맵을 유지하는 것은 또한, 폐영역 회수 프로세스를 미미하게 개선시킬 수 있다. 논리 주소의 서브셋에 대해서만 트리를 참조함으로써, 메모리 액세스의 양이 줄어들 수 있다.
도 5 내지 도 9의 프로세스(500, 600, 700, 800, 및 900)은 시스템(예를 들어, 도 1의 전자 장치(100) 또는 도 3의 전자 장치(300)) 내의 하나 이상의 컴포넌트들에 의해 실행될 수 있다는 점을 이해하여야 한다. 예를 들어, 프로세스 내의 단계들 중 적어도 일부는 NVM 인터페이스(예를 들어, 도 1의 NVM 인터페이스(118) 또는 도 3의 NVM 인터페이스(318))에 의해 수행될 수 있다. 당업자라면 이들 단계들 중 하나 이상이 제어 회로(예를 들어, 도 1의 SoC 제어 회로(112))에 의해 수행될 수 있다는 것을 이해할 것이다.
또한, 도 5 내지 도 9의 프로세스(500, 600, 700, 800, 및 900)는 단지 예일 뿐이라는 점을 이해하여야 한다. 본 발명의 범위로부터 벗어나지 않고, 임의의 단계가 제거되거나, 수정되거나, 또는 결합될 수 있으며, 임의의 추가 단계들이 더해질 수 있다.
본 발명의 설명된 실시예들은, 제한이 아니라 예시의 목적을 위해 제공된 것이다.

Claims (19)

  1. 비휘발성 메모리("NVM")를 포함하는 시스템을 위한 논리 블록 주소("LBA")들을 언맵핑하기 위한 방법으로서,
    복수의 LBA의 맵핑 상태들을 휘발성 메모리에 저장된 비트맵에 저장하는 단계;
    제1 LBA를 언맵핑하라는 요청을 파일 시스템으로부터 수신하는 단계;
    상기 비트맵을 업데이트하는 것만으로 상기 제1 LBA의 맵핑 상태를 언맵핑으로 변경하는 단계; 및
    상기 제1 LBA에 대응하는 수퍼 블록(super block)에 대한 유효성 카운터(validity counter)를 감소시키는 단계
    를 포함하는 방법.
  2. 제1항에 있어서, 상기 비트맵의 각 엔트리는 하나의 LBA와 다수의 LBA 중 하나에 대응하는 방법.
  3. 제1항 또는 제2항에 있어서, 시스템 부트-업 동안에 상기 복수의 LBA의 맵핑 상태들과 연관된 정보를 상기 파일 시스템으로부터 수신하는 단계를 더 포함하는 방법.
  4. 제1항 또는 제2항에 있어서, 상기 NVM을 스캐닝함으로써 상기 복수의 LBA의 맵핑 상태들을 얻는 단계를 더 포함하는 방법.
  5. 제1항 또는 제2항에 있어서,
    제2 LBA를 판독하라는 판독 요청을 상기 파일 시스템으로부터 수신하는 단계;
    상기 제2 LBA와 연관된 상기 비트맵의 엔트리를 참조하는 단계;
    상기 제2 LBA가 언맵핑되어 있다고 상기 엔트리가 나타내는지를 판정하는 단계; 및
    상기 제2 LBA가 언맵핑되어 있다고 상기 엔트리가 나타낸다는 판정에 응답하여, 상기 제2 LBA는 사용자 데이터와 연관되어 있지 않다고 나타내는 정보를 상기 파일 시스템에 송신하는 단계
    를 더 포함하는 방법.
  6. 제5항에 있어서,
    상기 제2 LBA가 언맵핑되어 있지 않다고 상기 엔트리가 나타낸다는 판정에 응답하여, 상기 제2 LBA와 연관된 사용자 데이터의 위치를 파악하기 위해 상기 NVM의 인덱스 페이지를 참조하는 단계; 및
    상기 사용자 데이터를 상기 파일 시스템에 송신하는 단계
    를 더 포함하는 방법.
  7. 삭제
  8. 삭제
  9. 삭제
  10. 삭제
  11. 삭제
  12. 삭제
  13. 삭제
  14. 삭제
  15. 삭제
  16. 삭제
  17. 삭제
  18. 삭제
  19. 삭제
KR1020120143392A 2011-12-12 2012-12-11 Ｌｂａ 비트맵 사용 Expired - Fee Related KR101457270B1 (ko)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US13/323,311 US9069657B2 (en) 2011-12-12 2011-12-12 LBA bitmap usage
US13/323,311 2011-12-12

Related Child Applications (1)

Application Number Title Priority Date Filing Date
KR1020130007928A Division KR101966693B1 (ko) 2011-12-12 2013-01-24 Ｌｂａ 비트맵 사용

Publications (2)

Publication Number Publication Date
KR20130066524A KR20130066524A (ko) 2013-06-20
KR101457270B1 true KR101457270B1 (ko) 2014-10-31

Family

ID=47681510

Family Applications (2)

Application Number Title Priority Date Filing Date
KR1020120143392A Expired - Fee Related KR101457270B1 (ko) 2011-12-12 2012-12-11 Ｌｂａ 비트맵 사용
KR1020130007928A Active KR101966693B1 (ko) 2011-12-12 2013-01-24 Ｌｂａ 비트맵 사용

Family Applications After (1)

Application Number Title Priority Date Filing Date
KR1020130007928A Active KR101966693B1 (ko) 2011-12-12 2013-01-24 Ｌｂａ 비트맵 사용

Country Status (7)

Country Link
US (2) US9069657B2 (ko)
EP (1) EP2605142B1 (ko)
JP (1) JP2013137770A (ko)
KR (2) KR101457270B1 (ko)
CN (1) CN103164346B (ko)
TW (2) TWI516924B (ko)
WO (1) WO2013090133A1 (ko)

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR20180011365A (ko) * 2014-12-12 2018-01-31 인텔 코포레이션 저장 시스템에서의 가속된 데이터 복구
US11016881B2 (en) 2018-12-17 2021-05-25 SK Hynix Inc. Memory system and operating method thereof
US11281590B2 (en) 2019-08-05 2022-03-22 SK Hynix Inc. Controller, operating method thereof and storage device including the same

Families Citing this family (52)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8327185B1 (en) 2012-03-23 2012-12-04 DSSD, Inc. Method and system for multi-dimensional raid
US9323667B2 (en) * 2012-04-12 2016-04-26 Violin Memory Inc. System and method for managing trim operations in a flash memory system using mapping tables and block status tables
US10282286B2 (en) * 2012-09-14 2019-05-07 Micron Technology, Inc. Address mapping using a data unit type that is variable
KR102015053B1 (ko) * 2013-02-20 2019-08-27 삼성전자주식회사 불휘발성 메모리 장치 및 그것의 데이터 처리 방법
US9612773B2 (en) * 2013-11-21 2017-04-04 Samsung Electronics Co., Ltd. User device having a host flash translation layer (FTL), a method for transferring an erase count thereof, a method for transferring reprogram information thereof, and a method for transferring a page offset of an open block thereof
US9329792B2 (en) 2014-01-14 2016-05-03 International Business Machines Corporation Storage thin provisioning and space reclamation
CN103927132B (zh) * 2014-03-31 2017-08-25 华为技术有限公司 数据处理方法及装置
KR102254392B1 (ko) * 2014-05-12 2021-05-25 삼성전자주식회사 메모리 컨트롤러의 동작 방법 및 불휘발성 메모리 장치 및 메모리 컨트롤러를 포함하는 불휘발성 메모리 시스템
US9792069B2 (en) * 2014-09-29 2017-10-17 Western Digital Technologies, Inc. Offline deduplication for solid-state storage devices
US10474569B2 (en) 2014-12-29 2019-11-12 Toshiba Memory Corporation Information processing device including nonvolatile cache memory and processor
US10331552B2 (en) 2015-03-10 2019-06-25 Toshiba Memory Corporation Storage device and memory system
US10372676B2 (en) 2015-07-30 2019-08-06 Netapp Inc. Stale data detection
WO2017066601A1 (en) * 2015-10-16 2017-04-20 Huang Yiren Ronnie Method and apparatus for providing hybrid mode to access ssd drive
US10268385B2 (en) * 2016-05-03 2019-04-23 SK Hynix Inc. Grouped trim bitmap
US10061708B2 (en) 2016-05-12 2018-08-28 SK Hynix Inc. Mapped region table
JP2017219913A (ja) * 2016-06-03 2017-12-14 富士通株式会社 ストレージ制御装置、ストレージシステムおよびストレージ制御プログラム
US10353813B2 (en) 2016-06-29 2019-07-16 Western Digital Technologies, Inc. Checkpoint based technique for bootstrapping forward map under constrained memory for flash devices
US11216361B2 (en) 2016-06-29 2022-01-04 Western Digital Technologies, Inc. Translation lookup and garbage collection optimizations on storage system with paged translation table
US10229048B2 (en) 2016-06-29 2019-03-12 Western Digital Technologies, Inc. Unified paging scheme for dense and sparse translation tables on flash storage systems
US10175896B2 (en) 2016-06-29 2019-01-08 Western Digital Technologies, Inc. Incremental snapshot based technique on paged translation systems
US10235287B2 (en) 2016-06-29 2019-03-19 Western Digital Technologies, Inc. Efficient management of paged translation maps in memory and flash
KR102653401B1 (ko) * 2016-07-18 2024-04-03 에스케이하이닉스 주식회사 메모리 시스템 및 그의 동작방법
US20180089088A1 (en) * 2016-09-27 2018-03-29 Intel Corporation Apparatus and method for persisting blocks of data and metadata in a non-volatile memory (nvm) cache
KR102395538B1 (ko) * 2017-04-28 2022-05-10 에스케이하이닉스 주식회사 데이터 저장 장치 및 그것의 동작 방법
US10339062B2 (en) 2017-04-28 2019-07-02 EMC IP Holding Company LLC Method and system for writing data to and read data from persistent storage
US10466930B2 (en) 2017-04-28 2019-11-05 EMC IP Holding Company LLC Method and system for fast ordered writes with atomic multicast
US10289491B1 (en) 2017-04-28 2019-05-14 EMC IP Holding Company LLC Method and system for implementing multi-dimensional raid in an extensible storage array to optimize performance
US10614019B2 (en) 2017-04-28 2020-04-07 EMC IP Holding Company LLC Method and system for fast ordered writes with target collaboration
KR20190044968A (ko) * 2017-10-23 2019-05-02 에스케이하이닉스 주식회사 메모리 시스템 및 그것의 동작 방법
JP6982468B2 (ja) * 2017-10-27 2021-12-17 キオクシア株式会社 メモリシステムおよび制御方法
US10725904B2 (en) 2017-12-13 2020-07-28 Micron Technology, Inc. Synchronizing NAND logical-to-physical table region tracking
KR20200020464A (ko) * 2018-08-17 2020-02-26 에스케이하이닉스 주식회사 데이터 저장 장치 및 그 동작 방법
KR102679967B1 (ko) 2018-09-12 2024-07-02 에스케이하이닉스 주식회사 메모리 시스템에서의 유효 데이터 관리 방법 및 장치
KR102711044B1 (ko) 2018-09-20 2024-09-27 에스케이하이닉스 주식회사 메모리 시스템에서의 유효 데이터 체크 방법 및 장치
KR102695719B1 (ko) 2018-12-19 2024-08-16 삼성전자주식회사 데이터 스토리지 장치를 포함하는 시스템 및 데이터 스토리지 장치의 디스카드 동작 제어 방법
KR102839223B1 (ko) * 2019-01-07 2025-07-29 에스케이하이닉스 주식회사 데이터 저장 장치 및 그 동작 방법
US11301369B2 (en) * 2019-01-24 2022-04-12 Western Digital Technologies, Inc. Logical to physical mapping management using low-latency non-volatile memory
KR102732880B1 (ko) * 2019-03-27 2024-11-22 에스케이하이닉스 주식회사 메모리 컨트롤러 및 그 동작 방법
KR102818164B1 (ko) * 2019-04-01 2025-06-10 에스케이하이닉스 주식회사 메모리 시스템, 메모리 컨트롤러 및 그 동작 방법
CN110262980B (zh) * 2019-06-17 2023-05-02 吉林大学 基于有限寿命存储介质的高速存储系统
US11216218B2 (en) 2019-07-15 2022-01-04 Micron Technology, Inc. Unmap data pattern for coarse mapping memory sub-system
US11157404B2 (en) * 2019-08-27 2021-10-26 Micron Technology, Inc. Remapping techniques for a range of logical block addresses in a logical to physical table of NAND storage
US10957381B1 (en) * 2019-08-28 2021-03-23 Micron Technology, Inc. Metadata grouping for un-map techniques
US10990537B1 (en) * 2020-01-07 2021-04-27 International Business Machines Corporation Logical to virtual and virtual to physical translation in storage class memory
CN111737161B (zh) * 2020-05-22 2024-03-26 深圳市战音科技有限公司 Flash存储器的文件传输方法、终端及存储介质
CN111813471B (zh) * 2020-06-16 2024-06-18 北京明略软件系统有限公司 一种换肤的方法、终端和存储介质
US11500769B2 (en) * 2020-12-21 2022-11-15 Micron Technology, Inc. Valid data identification for garbage collection
TWI771926B (zh) * 2021-02-25 2022-07-21 慧榮科技股份有限公司 資料儲存裝置以及非揮發式記憶體控制方法
CN113282249B (zh) 2021-07-19 2021-10-29 苏州浪潮智能科技有限公司 一种数据处理方法、系统、设备以及介质
CN115712386A (zh) * 2021-08-23 2023-02-24 华为技术有限公司 超级块管理方法和装置
US12339771B2 (en) * 2021-09-23 2025-06-24 Samsung Electronics Co., Ltd. Systems and methods for workload distribution across processing units
CN114398297B (zh) * 2021-12-06 2025-09-12 尧云科技(西安)有限公司 一种基于混合地址映射的存储方法及存储装置

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2011024239A1 (en) * 2009-08-31 2011-03-03 Hitachi, Ltd. Storage system having plurality of flash packages
JP2011508349A (ja) * 2007-12-27 2011-03-10 プライアント テクノロジー インコーポレイテッド プロセッサを内部メモリに接続するクロスバー・スイッチを含むフラッシュメモリ用ストレージコントローラ

Family Cites Families (20)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5845313A (en) 1995-07-31 1998-12-01 Lexar Direct logical block addressing flash memory mass storage architecture
JP2003067244A (ja) 2001-08-24 2003-03-07 Matsushita Electric Ind Co Ltd 不揮発性記憶装置及びその制御方法
US7173929B1 (en) * 2001-12-10 2007-02-06 Incipient, Inc. Fast path for performing data operations
US6915405B2 (en) 2002-12-04 2005-07-05 Bull Hn Information Systems Inc. Emulated target associative memory system with a multi-digit incrementable validity counter
US6938145B2 (en) 2002-12-04 2005-08-30 Bull Hn Information Systems Inc. Associative memory system with a multi-digit incrementable validity counter
US7437530B1 (en) 2003-04-24 2008-10-14 Network Appliance, Inc. System and method for mapping file block numbers to logical block addresses
US8504798B2 (en) 2003-12-30 2013-08-06 Sandisk Technologies Inc. Management of non-volatile memory systems having large erase blocks
US7873782B2 (en) 2004-11-05 2011-01-18 Data Robotics, Inc. Filesystem-aware block storage system, apparatus, and method
CN101176074B (zh) 2005-12-09 2010-12-15 松下电器产业株式会社 非易失性存储器件，写入数据的方法，和读出数据的方法
JP4235646B2 (ja) 2005-12-28 2009-03-11 Ｔｄｋ株式会社 メモリコントローラおよびフラッシュメモリシステム
US9396103B2 (en) * 2007-06-08 2016-07-19 Sandisk Technologies Llc Method and system for storage address re-mapping for a memory device
US7949851B2 (en) 2007-12-28 2011-05-24 Spansion Llc Translation management of logical block addresses and physical block addresses
US8276043B2 (en) * 2008-03-01 2012-09-25 Kabushiki Kaisha Toshiba Memory system
JP4164118B1 (ja) 2008-03-26 2008-10-08 眞澄 鈴木 フラッシュメモリを用いた記憶装置
US8065304B2 (en) * 2008-06-11 2011-11-22 International Business Machines Corporation Using asymmetric memory
KR101533744B1 (ko) 2008-10-16 2015-07-10 삼성전자주식회사 플래시 메모리 시스템 및 그것의 플래시 변환 계층 설계 방법
KR101695364B1 (ko) 2009-03-27 2017-01-11 엘에스아이 코포레이션 저장 시스템 로컬 블록 어드레스 할당해제 관리 및 데이터 강화
US8516219B2 (en) 2009-07-24 2013-08-20 Apple Inc. Index cache tree
JP2011192260A (ja) 2010-02-16 2011-09-29 Toshiba Corp 半導体記憶装置
US9286101B2 (en) * 2011-07-28 2016-03-15 Red Hat, Inc. Free page hinting

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2011508349A (ja) * 2007-12-27 2011-03-10 プライアント テクノロジー インコーポレイテッド プロセッサを内部メモリに接続するクロスバー・スイッチを含むフラッシュメモリ用ストレージコントローラ
WO2011024239A1 (en) * 2009-08-31 2011-03-03 Hitachi, Ltd. Storage system having plurality of flash packages

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR20180011365A (ko) * 2014-12-12 2018-01-31 인텔 코포레이션 저장 시스템에서의 가속된 데이터 복구
KR102502352B1 (ko) 2014-12-12 2023-02-23 인텔 코포레이션 저장 시스템에서의 가속된 데이터 복구
US11016881B2 (en) 2018-12-17 2021-05-25 SK Hynix Inc. Memory system and operating method thereof
US11281590B2 (en) 2019-08-05 2022-03-22 SK Hynix Inc. Controller, operating method thereof and storage device including the same

Also Published As

Publication number Publication date
KR20130066524A (ko) 2013-06-20
US20130151754A1 (en) 2013-06-13
US9069657B2 (en) 2015-06-30
US9477596B2 (en) 2016-10-25
US20150301938A1 (en) 2015-10-22
CN103164346B (zh) 2016-10-19
WO2013090133A1 (en) 2013-06-20
EP2605142B1 (en) 2018-09-05
CN103164346A (zh) 2013-06-19
KR101966693B1 (ko) 2019-04-09
TW201346553A (zh) 2013-11-16
TWI516924B (zh) 2016-01-11
KR20130066640A (ko) 2013-06-20
TW201337560A (zh) 2013-09-16
EP2605142A1 (en) 2013-06-19
JP2013137770A (ja) 2013-07-11
TWI566097B (zh) 2017-01-11

Similar Documents

Publication Publication Date Title
KR101457270B1 (ko) Ｌｂａ 비트맵 사용
US8949512B2 (en) Trim token journaling
US10915475B2 (en) Methods and apparatus for variable size logical page management based on hot and cold data
US8812816B2 (en) Garbage collection schemes for index block
EP2472405B1 (en) Handling dynamic and static data for a system having a non-volatile memory
KR101451482B1 (ko) 데이터 이용가능성의 마운트타임 조정
US8478796B2 (en) Uncorrectable error handling schemes for non-volatile memories
US8966209B2 (en) Efficient allocation policies for a system having non-volatile memory
US9063728B2 (en) Systems and methods for handling hibernation data
US8949506B2 (en) Initiating wear leveling for a non-volatile memory
US9235502B2 (en) Systems and methods for configuring non-volatile memory
KR101900760B1 (ko) 비휘발성 메모리를 갖는 시스템에 대한 비정상 셧다운의 핸들링
US20160342509A1 (en) Hierarchical FTL Mapping Optimized for Workload
US8850160B2 (en) Adaptive write behavior for a system having non-volatile memory
US20250264997A1 (en) Storage device and operating method thereof
HK1176420A (en) Handling dynamic and static data for a system having non-volatile memory
HK1172973A (en) Handling dynamic and static data for a system having a non-volatile memory

Legal Events

Date Code Title Description
A201 Request for examination
PA0109 Patent application

St.27 status event code: A-0-1-A10-A12-nap-PA0109

PA0201 Request for examination

St.27 status event code: A-1-2-D10-D11-exm-PA0201

A107 Divisional application of patent
PA0107 Divisional application

St.27 status event code: A-0-1-A10-A18-div-PA0107

St.27 status event code: A-0-1-A10-A16-div-PA0107

PG1501 Laying open of application

St.27 status event code: A-1-1-Q10-Q12-nap-PG1501

D13-X000 Search requested

St.27 status event code: A-1-2-D10-D13-srh-X000

D14-X000 Search report completed

St.27 status event code: A-1-2-D10-D14-srh-X000

E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

St.27 status event code: A-1-2-D10-D21-exm-PE0902

T11-X000 Administrative time limit extension requested

St.27 status event code: U-3-3-T10-T11-oth-X000

T11-X000 Administrative time limit extension requested

St.27 status event code: U-3-3-T10-T11-oth-X000

R17-X000 Change to representative recorded

St.27 status event code: A-3-3-R10-R17-oth-X000

E13-X000 Pre-grant limitation requested

St.27 status event code: A-2-3-E10-E13-lim-X000

P11-X000 Amendment of application requested

St.27 status event code: A-2-2-P10-P11-nap-X000

P13-X000 Application amended

St.27 status event code: A-2-2-P10-P13-nap-X000

E701 Decision to grant or registration of patent right
PE0701 Decision of registration

St.27 status event code: A-1-2-D10-D22-exm-PE0701

GRNT Written decision to grant
PR0701 Registration of establishment

St.27 status event code: A-2-4-F10-F11-exm-PR0701

PR1002 Payment of registration fee

St.27 status event code: A-2-2-U10-U11-oth-PR1002

Fee payment year number: 1

PG1601 Publication of registration

St.27 status event code: A-4-4-Q10-Q13-nap-PG1601

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 4

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 5

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 6

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 7

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 8

PC1903 Unpaid annual fee

St.27 status event code: A-4-4-U10-U13-oth-PC1903

Not in force date: 20221028

Payment event data comment text: Termination Category : DEFAULT_OF_REGISTRATION_FEE

PC1903 Unpaid annual fee

St.27 status event code: N-4-6-H10-H13-oth-PC1903

Ip right cessation event data comment text: Termination Category : DEFAULT_OF_REGISTRATION_FEE

Not in force date: 20221028