KR101818578B1

KR101818578B1 - 비휘발성 메모리를 갖는 시스템을 위한 동적 및 정적 데이터의 처리

Info

Publication number: KR101818578B1
Application number: KR1020120001364A
Authority: KR
Inventors: 다니엘 제이. 포스트; 니어 제이. 워크랫
Original assignee: 애플 인크.
Priority date: 2011-01-03
Filing date: 2012-01-05
Publication date: 2018-01-15
Also published as: TW201245959A; KR20120079026A; EP2472405B1; CN102693184A; TWI519950B; US20120173832A1; WO2012094237A1; CN102693184B; KR101390134B1; TWI448890B; TW201241623A; US8521948B2; EP2472405A1; KR20120079023A

Abstract

비휘발성 메모리("NVM")를 갖는 시스템을 위한 동적 및 정적 데이터를 처리하기 위한 시스템들 및 방법들이 개시된다. NVM에 기입되고 있는 데이터가 동적인지를 결정함으로써, 시스템의 NVM 인터페이스는 NVM 상의 어느 곳에 데이터를 최초로 배치할지를 결정할 수 있다(예를 들어, 데이터를 동적 스트림 블록 또는 정적 스트림 블록에 배치할 수 있다). 더욱이, 이 정보는 NVM 인터페이스가 쓰레기 수거("GC") 및 마모 균등화 양자의 효율들을 향상시킬 수 있게 한다.

Description

비휘발성 메모리를 갖는 시스템을 위한 동적 및 정적 데이터의 처리{HANDLING DYNAMIC AND STATIC DATA FOR A SYSTEM HAVING NON-VOLATILE MEMORY}

본 발명은 비휘발성 메모리를 갖는 시스템을 위한 동적 및 정적 데이터의 처리에 관한 것이다.

NAND 플래시 메모리는 물론, 다른 타입의 비휘발성 메모리("NVM")들은 일반적으로 대용량 저장을 위해 사용된다. 예를 들어, 휴대용 미디어 플레이어들과 같은 소비자 전자 장치들은 종종 음악, 비디오 및 다른 미디어를 저장하기 위한 플래시 메모리를 포함한다.

NVM은 전자 장치가 필요로 하는 데이터(예로서, "유효 데이터") 및 전자 장치가 더 이상 필요로 하지 않는 데이터(예로서, "실효 데이터")의 양자를 포함할 수 있다. NVM에 저장된 유효 데이터는 자주 갱신 또는 변경되는 데이터(예로서, "동적 데이터") 및 거의 갱신 또는 변경되지 않는 데이터(예로서, "정적 데이터")로 더 분류될 수 있다. 통상적으로, NVM 내의 데이터의 배치는 다소 임의적이며, 따라서 동적 및 정적 데이터의 혼합이 NVM의 단일 블록 내에 저장될 수 있다.

일부 NVM들은 프로그래밍된 메모리 위치들의 블록이 블록 내의 임의의 메모리 위치가 재프로그래밍될 수 있기 전에 소거되는 것이 필요하도록 구성된다. 따라서, 전자 장치들은 통상적으로 소거 및 재프로그래밍할 블록들을 자유롭게 하기 위해 "쓰레기 수거"("GC")라고 하는 작업을 수행한다. 소거할 블록 내의 모든 메모리 위치들을 자유롭게 하기 위해, 전자 장치는 블록의 유효 데이터를 다른 블록의 메모리 위치들에 복사할 수 있다. 블록 상에는 동적 및 정적 데이터의 혼합이 존재하므로, GC의 효율이 낮을 수 있는데, 이는 복사되어야 하는 유효 데이터의 양이 상당할 수 있기 때문이다.

게다가, 전자 장치들은 때때로 "마모 균등화(wear leveling)"라고 하는 작업을 이용하여 블록에 대한 GC를 수행할 수 있다. 마모 균등화는 일반적으로 NVM의 유효 수명을 연장하는 데 사용된다. 종종, 시스템들은 NVM의 불필요한 마모 균등화를 수행할 수 있으며, 이는 사실상 NVM을 더 많이 마모시킬 수 있다.

비휘발성 메모리를 갖는 시스템을 위한 동적 및 정적 데이터를 처리하기 위한 시스템들 및 방법들이 개시된다. NVM에 기입되고 있는 데이터가 동적인지를 결정함으로써, 시스템의 NVM 인터페이스는 NVM 상의 어느 곳에 데이터를 최초로 배치할지를 결정할 수 있다. 더욱이, 이것은 NVM 인터페이스가 쓰레기 수거 및 마모 균등화 양자의 효율들을 향상시킬 수 있게 한다.

본 발명의 상기 및 다른 양태들 및 장점들은 첨부 도면들과 관련하여 이루어지는 아래의 상세한 설명을 고찰할 때 더 명확해질 것이며, 도면들 전반에서 동일한 참조 부호들은 동일한 요소들을 지시하고, 도면들에서:
도 1 및 2는 본 발명의 다양한 실시예들에 따라 구성된 전자 장치들의 블록도들이고,
도 3은 본 발명의 다양한 실시예들에 따른 논리 블록 어드레스들의 물리 페이지들로의 예시적인 맵핑의 블록도이고,
도 4는 본 발명의 다양한 실시예들에 따른 논리 대 물리 어드레스 맵핑들을 제공하는 데 사용되는 예시적인 트리의 블록도이고,
도 5는 본 발명의 다양한 실시예들에 따른 사용자 데이터와 연관될 수 있는 메타데이터의 그래픽 도면이고,
도 6은 본 발명의 다양한 실시예들에 따른 비휘발성 메모리에 데이터를 프로그래밍하기 위한 예시적인 프로세스의 흐름도이고,
도 7은 본 발명의 다양한 실시예들에 따른 비휘발성 메모리 상에서 쓰레기 수거를 행하기 위한 예시적인 프로세스의 흐름도이고,
도 8은 본 발명의 다양한 실시예들에 따른 비휘발성 메모리 상에서 마모 균등화를 수행할지를 결정하기 위한 예시적인 프로세스의 흐름도이다.

비휘발성 메모리("NVM")를 갖는 시스템을 위한 동적 및 정적 데이터를 처리하기 위한 시스템들 및 방법들이 제공된다. NVM에 기입되고 있는 데이터가 동적인지를 결정함으로써, 시스템의 NVM 인터페이스는 NVM 상의 어느 곳에 데이터를 최초로 배치할지를 결정할 수 있다. 더욱이, 이것은 NVM 인터페이스가 쓰레기 수거("GC") 및 마모 균등화 양자의 효율들을 향상시킬 수 있게 한다.

예를 들어, 논리 블록 어드레스("LBA") 범위에 대응하는 기입 요청의 수신에 응답하여, NVM 인터페이스는 LBA 범위와 관련된 데이터가 동적인지를 결정할 수 있다. 일부 실시예들에서, NVM 인터페이스는 트리 또는 메타데이터로부터 얻은 하나 이상의 파라미터에 기초하여 이러한 결정을 행할 수 있다. 하나 이상의 파라미터는 예를 들어 특정 LBA 범위가 기입된 횟수를 지시하는 카운터, 애플리케이션 및/또는 운영 체제에 의해 데이터가 언제 LBA 범위에 최종 기입되었는지를 지시하는 사용자 위브 시퀀스(user weave sequence), 임의의 소스에 의해(예로서, GC 프로세스에 의해 또는 애플리케이션 또는 운영 체제에 의해) 데이터가 언제 LBA 범위에 최종 기입되었는지를 지시하는 위브 시퀀스 및/또는 이들의 임의 조합과 같은 임의의 적절한 파라미터일 수 있다. LBA 범위와 관련된 데이터가 동적인지의 여부의 결정에 기초하여, NVM 인터페이스는 데이터를 동적 스트림 블록 또는 정적 스트림 블록에 프로그래밍할 수 있다.

본 명세서에서 사용될 때, "동적 스트림 블록"은 NVM 인터페이스에 의해 동적 스트림의 일부로서 지정된 NVM의 임의의 적절한 블록일 수 있다. 동적인 것으로 분류되는 착신 데이터는 하나 이상의 동적 블록 상에 선택적으로 배치될 수 있다. 또한, 본 명세서에서 사용될 때, "정적 스트림 블록"은 NVM 인터페이스에 의해 정적 스트림의 일부로서 지정된 NVM의 임의의 적절한 블록일 수 있다. 정적인 것으로 분류되는 착신 데이터는 하나 이상의 정적 블록 상에 선택적으로 배치될 수 있다.

착신 데이터를 2개의 분리된 기입 스트림으로 분할함으로써, GC 기입 증폭이 감소할 수 있으며, 결과적으로 GC의 효율이 향상될 수 있다. 게다가, 데이터가 동적인지의 여부의 결정은 NVM 인터페이스가 NVM의 불필요한 마모 균등화를 피할 수 있게 한다.

도 1은 전자 장치(100)의 블록도를 나타낸다. 일부 실시예들에서, 전자 장치(100)는 휴대용 미디어 플레이어, 셀룰러 전화, 포켓 사이즈의 개인용 컴퓨터, 개인용 휴대 단말기("PDA"), 데스크탑 컴퓨터, 랩탑 컴퓨터 및 임의의 다른 적절한 타입의 전자 장치이거나, 이들을 포함할 수 있다.

전자 장치(100)는 시스템-온-칩("SoC")(110) 및 비휘발성 메모리("NVM")(120)를 포함할 수 있다. 비휘발성 메모리(120)는 부유 게이트 또는 전하 트랩핑 기술에 기초하는 NAND 플래시 메모리, NOR 플래시 메모리, 소거 및 프로그래밍 가능한 판독 전용 메모리("EPROM"), 전기적으로 소거 및 프로그래밍 가능한 판독 전용 메모리("EEPROM"), 강유전체 RAM("FRAM"), 자기저항 RAM("MRAM") 또는 이들의 임의 조합을 포함할 수 있다.

NVM(120)은 최소 소거 가능 단위일 수 있는 "블록들"로 체계화되거나, 프로그래밍 또는 판독될 수 있는 최소 단위일 수 있는 "페이지들"로서 더 체계화될 수 있다. 일부 실시예들에서, NVM(120)은 다수의 집적 회로를 포함할 수 있으며, 각각의 집적 회로는 다수의 블록을 가질 수 있다. 대응하는 집적 회로들로부터의 메모리 위치들(예로서, 블록들 또는 블록들의 페이지들)은 "수퍼 블록들"을 형성할 수 있다. NVM(120)의 각각의 메모리 위치(예로서, 페이지 또는 블록)는 물리 어드레스(예로서, 물리 페이지 어드레스 또는 물리 블록 어드레스)를 이용하여 참조될 수 있다.

시스템-온-칩(110)은 SoC 제어 회로(112), 메모리(114) 및 NVM 인터페이스(118)를 포함할 수 있다. SoC 제어 회로(112)는 SoC(110) 및 SoC(110) 또는 장치(100)의 다른 컴포넌트들의 일반 동작들 및 기능들을 제어할 수 있다. 예컨대, 사용자 입력들 및/또는 애플리케이션 또는 운영 체제의 명령들에 응답하여, SoC 제어 회로(112)는 판독 또는 기입 요청들을 NVM 인터페이스(118)에 발행하여, NVM(120)으로부터 데이터를 얻거나 데이터를 그 안에 저장할 수 있다. 명료화를 위해, SoC 제어 회로(112)가 저장 또는 검색을 위해 요청할 수 있는 데이터는 사용자 또는 사용자 애플리케이션과 직접 연관되지 않을 수 있는 경우에도 "사용자 데이터"로서 지칭될 수 있다. 오히려, 사용자 데이터는 (예를 들어, 애플리케이션 또는 운영 체제를 통해) SoC 제어 회로(112)에 의해 생성되거나 얻어지는 디지털 정보의 임의의 적절한 시퀀스일 수 있다.

SoC 제어 회로(112)는 하드웨어, 소프트웨어 및 펌웨어의 임의 조합, 및 전자 장치(100)의 기능을 구동하도록 동작하는 임의의 컴포넌트들, 회로 또는 논리를 포함할 수 있다. 예를 들어, SoC 제어 회로(112)는 NVM(120) 또는 메모리(114)에 저장된 소프트웨어/펌웨어의 제어하에 동작하는 하나 이상의 프로세서를 포함할 수 있다.

메모리(114)는 임의의 적절한 타입의 휘발성 메모리, 예를 들어 랜덤 액세스 메모리("RAM")(예로서, 정적 RAM("SRAM"), 동적 랜덤 액세스 메모리("DRAM"), 동기식 동적 랜덤 액세스 메모리("SDRAM"), 더블 데이터 레이트("DDR") RAM), 캐시 메모리, 판독 전용 메모리("ROM") 또는 이들의 임의 조합을 포함할 수 있다. 메모리(114)는 비휘발성 메모리(120) 내에 프로그래밍하거나 그로부터 판독하기 위해 사용자 데이터를 임시 저장할 수 있는 데이터 소스를 포함할 수 있다. 일부 실시예들에서, 메모리(114)는 SoC 제어 회로(112)의 일부로서 구현되는 임의의 프로세서들에 대한 메인 메모리로서 역할할 수 있다.

NVM 인터페이스(118)는 SoC 제어 회로(112)와 NVM(120) 사이에 인터페이스 또는 드라이버로서 역할하도록 구성되는 하드웨어, 소프트웨어 및/또는 펌웨어의 임의의 적절한 조합을 포함할 수 있다. NVM 인터페이스(118)에 포함된 임의의 소프트웨어 모듈들에 대해, 대응하는 프로그램 코드가 NVM(120) 또는 메모리(114)에 저장될 수 있다.

NVM 인터페이스(118)는 SoC 제어 회로(112)가 NVM(120)에 액세스하고, NVM(120)의 메모리 위치들(예로서, 페이지들, 블록들, 수퍼 블록들, 집적 회로들) 및 그 안에 저장된 데이터(예로서, 사용자 데이터)를 관리할 수 있게 하는 다양한 기능들을 수행할 수 있다. 예를 들어, NVM 인터페이스(118)는 SoC 제어 회로(112)로부터 판독 또는 기입 요청들을 해석하고, 마모 균등화를 수행하고, NVM(120)의 버스 프로토콜과 호환되는 판독 및 프로그램 명령들을 생성할 수 있다.

NVM 인터페이스(118) 및 SoC 제어 회로(112)가 개별 모듈들로서 도시되지만, 이것은 본 발명의 실시예들의 설명을 간략화하기 위한 것일 뿐이다. 이러한 모듈들은 하드웨어 컴포넌트들, 소프트웨어 컴포넌트들 또는 이들 양자를 공유할 수 있다는 것을 이해해야 한다. 예를 들어, SoC 제어 회로(112)는 NVM 인터페이스(118)에 대한 소프트웨어 기반 메모리 드라이버를 실행할 수 있다.

일부 실시예들에서, 전자 장치(100)는 NVM(120) 또는 NVM 인터페이스(118)의 일부 또는 전부를 포함하는 플래시 메모리 드라이브 또는 SD 카드와 같은 타겟 드라이브를 포함할 수 있다. 이러한 실시예들에서, SoC(110) 또는 SoC 제어 회로(112)는 타겟 장치에 대한 호스트 제어기로서 역할할 수 있다. 예로서, 호스트 제어기로서, SoC(110)는 타겟 장치에 대해 판독 및 기입 요청들을 발행할 수 있다.

도 2는 전자 장치(200)의 블록도로서, 다양한 실시예들에 따른 전자 장치(100)(도 1)의 펌웨어, 소프트웨어 및/또는 하드웨어 컴포넌트들의 일부를 더 상세히 나타낼 수 있다. 전자 장치(200)는 도 1과 관련하여 전술한 임의의 특징들 및 기능들을 가질 수 있고, 그 반대도 마찬가지다. 도시된 바와 같이, 파선들은 계층들의 경계를 정한다. 경계선들 내에 어느 컴포넌트들이 속하는지에 대한 묘사는 예시적일 뿐이며, 하나 이상의 컴포넌트가 다른 계층과 관련될 수 있다는 것을 이해해야 한다.

전자 장치(200)는 파일 시스템(210), NVM 드라이버(212), NVM 버스 제어기(216) 및 NVM(220)을 포함할 수 있다. 일부 실시예들에서, 파일 시스템(210) 및 NVM 드라이버(212)는 소프트웨어 또는 펌웨어 모듈들일 수 있으며, NVM 버스 제어기(216) 및 NVM(220)은 하드웨어 모듈들일 수 있다. 따라서, 이러한 실시예들에서, NVM 드라이버(212)는 NVM 인터페이스(218)의 소프트웨어 또는 펌웨어 양태를 나타낼 수 있고, NVM 버스 제어기(216)는 NVM 인터페이스(218)의 하드웨어 양태를 나타낼 수 있다.

파일 시스템(210)은 임의의 적절한 타입의 파일 시스템, 예를 들어 파일 할당표("FAT") 파일 시스템 또는 계층 구조 파일 시스템 플러스("HFS+")를 포함할 수 있으며, 전자 장치(200)의 운영 체제의 일부(예로서, 도 1의 SoC 제어 회로(112)의 일부)일 수 있다. 일부 실시예들에서, 파일 시스템(210)은 페이지들의 논리 대 물리 맵핑을 제공하는 플래시 파일 시스템을 포함할 수 있다. 이러한 실시예들에서, 파일 시스템(210)은 후술하는 NVM 드라이버(212)의 기능들의 일부 또는 전부를 수행할 수 있으며, 따라서 파일 시스템(210) 및 NVM 드라이버(212)는 개별 모듈들이거나 아닐 수 있다.

파일 시스템(210)은 애플리케이션 및 운영 체제에 대한 파일 및 폴더 구조들을 관리할 수 있다. 파일 시스템(210)은 전자 장치(200) 상에서 실행되는 애플리케이션 또는 운영 체제의 제어하에 동작할 수 있으며, 애플리케이션 또는 운영 체제가 NVM(220)으로부터 정보를 판독하거나 그 안에 정보를 저장할 것을 요청할 때 기입 및 판독 요청들을 NVM 드라이버(212)에 제공할 수 있다. 각각의 판독 또는 기입 요청과 더불어, 파일 시스템(210)은 사용자 데이터가 어디서 판독되고 어디에 기입되어야 하는지를 지시하기 위한 논리 어드레스, 예컨대 논리 페이지 어드레스 또는 페이지 오프셋을 갖는 논리 블록 어드레스를 제공할 수 있다.

파일 시스템(210)은 NVM(220)과 직접 호환되지 않는 판독 및 기입 요청들을 NVM 드라이버(212)에 제공할 수 있다. 예를 들어, 논리 어드레스들은 하드 드라이브 기반 시스템들에 고유한 규약들 또는 프로토콜들을 이용할 수 있다. 하드 드라이브 기반 시스템은 플래시 메모리와 달리 블록 소거를 먼저 수행하지 않고 메모리 위치에 재기입할 수 있다. 더욱이, 하드 드라이브들은 장치의 수명을 증가시키기 위한 마모 균등화를 필요로 하지 않을 수 있다. 따라서, NVM 인터페이스(218)는 메모리에 고유한, 벤더에 고유한 또는 이들 양자에 고유한 임의의 기능들을 수행하여, 파일 시스템 요청들을 처리하고, NVM(220)에 적합한 방식으로 다른 관리 기능들을 수행할 수 있다.

NVM 드라이버(212)는 번역 계층(214)을 포함할 수 있다. 일부 실시예들에서, 번역 계층(214)은 플래시 번역 계층("FTL")이거나 이를 포함할 수 있다. 기입 요청시에, 번역 계층(214)은 제공된 논리 어드레스를 NVM(220) 상의 자유로운 소거된 물리 위치로 맵핑할 수 있다. 판독 요청시에, 번역 계층(214)은 제공된 논리 어드레스를 이용하여, 요청된 데이터를 저장할 물리 어드레스를 결정할 수 있다. 각각의 NVM은 NVM의 크기 또는 벤더에 따라 상이한 레이아웃을 가질 수 있으므로, 이러한 맵핑 동작은 메모리 및/또는 벤더에 고유할 수 있다.

논리 대 물리 어드레스 맵핑에 더하여, 번역 계층(214)은 플래시 번역 계층들에 고유할 수 있는 임의의 다른 적절한 기능들을 수행할 수 있다. 예를 들어, 번역 계층(214)은 소거할 NVM(220)의 프로그래밍된 블록을 자유롭게 하기 위해 쓰레기 수거("GC")를 수행할 수 있다. 자유화되고 소거된 메모리 위치들은 예를 들어 파일 시스템(210)으로부터 수신된 새로운 사용자 데이터를 저장하는 데 사용될 수 있다. 일부 예들에서, GC 프로세스는 프로그래밍된 블록으로부터의 유효 데이터를 소거된 메모리 위치들을 갖는 다른 블록으로 복사하여 프로그래밍된 블록 내의 유효 데이터를 실효시키는 단계를 포함할 수 있다. 프로그래밍된 블록 내의 모든 메모리 위치들이 실효되면, 번역 계층(214)은 프로그래밍된 블록에 대한 소거 작업을 수행하도록 버스 제어기(216)에 지시할 수 있다. 본 명세서에서 사용될 때, "유효 데이터"는 하나 이상의 논리 어드레스(예로서, LBA)에 대응하는 가장 최근의 기입 요청에 응답하여 프로그래밍된 사용자 데이터를 지칭할 수 있으며, 따라서 하나 이상의 논리 어드레스에 대한 사용자 데이터의 유효 버전일 수 있다.

다른 예로서, 번역 계층(214)은 NVM(220)에 대해 마모 균등화를 수행할 수 있으며, 이는 NVM(220)의 다양한 블록들 상에 마모를 분산시키는 데 사용될 수 있다. 마모 균등화가 필요한 이유는 NVM(220)의 일부가 (예로서, 사이클링 사양을 초과하여) NVM(220)의 다른 부분들보다 훨씬 더 많이 사이클링되어 잠재적으로 시스템이 사용 가능 공간을 고갈시키게 할 수 있기 때문이다. 게다가, NVM(220)의 작은 부분 상의 과다한 마모는 전반적으로 더 열악한 데이터 보유를 유발할 수 있다.

번역 계층(214)은 먼저 NVM(220)의 각각의 블록이 사이클링한 사이클들(예로서, 소거 사이클들 및/또는 기입 사이클들)의 수를 모니터링함으로써 마모 균등화를 수행할 수 있다. 이어서, 적절한 시간에(예로서, 유휴 시간 동안 또는 GC 프로세스 동안), 번역 계층(214)은 NVM(220)의 블록을 선택하여 마모 균등화를 개시할 수 있다. 일부 실시예들에서, 블록은 마모 균등화 큐를 이용하여 선택될 수 있다.

블록을 선택한 후에, 번역 계층(214)은 그 블록에 대해 마모 균등화를 개시할 수 있다. 예를 들어, 번역 계층(214)은 (예를 들어, 블록에 저장된 유효 데이터를 다른 블록에 복사하고, 블록을 소거함으로써) 블록에 대해 GC를 수행할 수 있다.

일부 실시예들에서, NVM 드라이버(212)는 NVM 버스 제어기(216)와 인터페이스하여 NVM 액세스 요청들(예로서, 프로그램, 판독 및 소거 요청들)을 완료할 수 있다. 버스 제어기(216)는 NVM(220)에 대한 하드웨어 인터페이스로서 역할할 수 있으며, NVM(220)의 버스 프로토콜, 데이터 레이트 및 다른 사양들을 이용하여 NVM(220)과 통신할 수 있다.

NVM 인터페이스(218)는 때때로 본 명세서에서 "메타데이터"라고 하는 메모리 관리 데이터에 기초하여 NVM(220)을 관리할 수 있다. 메타데이터는 NVM 드라이버(212)에 의해 생성될 수 있거나, NVM 드라이버(212)의 제어하에 동작하는 모듈에 의해 생성될 수 있다. 예를 들어, 메타데이터는 논리 및 물리 어드레스들 사이의 맵핑 관리, 불량 블록 관리, 마모 균등화에 사용되는 임의의 정보, 데이터 에러들을 검출 또는 정정하는 데 사용되는 ECC 데이터 또는 이들의 임의 조합을 포함할 수 있다. 메타데이터는 논리 어드레스와 같은 사용자 데이터와 더불어 파일 시스템(210)에 의해 제공되는 데이터를 포함할 수 있다. 따라서, 일반적으로, "메타데이터"는 사용자 데이터에 대한 또는 사용자 데이터와 관련된 또는 비휘발성 메모리의 동작 및 메모리 위치들을 관리하기 위해 일반적으로 사용되는 임의의 정보를 지칭할 수 있다.

NVM 인터페이스(218)는 NVM(220)에 메타데이터를 저장하도록 구성될 수 있다. 일부 실시예들에서, NVM 인터페이스(218)는 사용자 데이터를 저장한 동일 메모리 위치(예로서, 페이지)에 사용자 데이터와 관련된 메타데이터를 저장할 수 있다. 예를 들어, NVM 인터페이스(218)는 사용자 데이터, 관련 논리 어드레스 및 사용자 데이터에 대한 ECC 데이터를 NVM(220)의 하나 이상의 메모리 위치에 저장할 수 있다. NVM 인터페이스(218)는 사용자 데이터에 대한 다른 타입의 메타데이터도 동일 메모리 위치에 저장할 수 있다. 메타데이터는 도 5와 관련하여 더 상세히 설명될 것이다.

NVM 인터페이스(218)는 논리 어드레스를 저장할 수 있으며, 따라서 NVM(220)의 시동시에 또는 NVM(220)의 동작 동안에 전자 장치(200)는 그 위치에 어떤 데이터가 위치하는지를 결정할 수 있다. 특히, 파일 시스템(210)은 사용자 데이터를 그의 물리 어드레스가 아니라 그의 논리 어드레스에 따라 참조할 수 있으므로, NVM 인터페이스(218)는 사용자 데이터와 논리 어드레스를 함께 저장하여, 그들의 연관성을 유지할 수 있다. 이러한 방식으로, NVM(220) 내의 물리 대 논리 맵핑을 유지하는 개별적인 표가 구식이 되는 경우에도, NVM 인터페이스(218)는 예를 들어 전자 장치(200)의 시동 또는 재부팅시에 적절한 맵핑을 여전히 결정할 수 있다.

이제, 도 3을 참조하면, 논리 블록 어드레스들(302)의 물리 페이지들(304)로의 예시적인 맵핑을 나타내는 블록도가 도시되어 있다. 논리 블록 어드레스들은 논리 공간 내의 논리 블록들에 대응할 수 있다. 각각의 논리 블록은 판독 및/또는 기입이 가능한 논리 공간의 최소 입자 단위일 수 있으며, 예를 들어 512 바이트, 4K 또는 8K와 같은 임의의 적절한 크기를 가질 수 있다.

파일 시스템(예로서, 도 2의 파일 시스템(210))은 임의의 적절한 수의 LBA들을 파일에 할당할 수 있다. 예컨대, 도 3에 도시된 바와 같이, LBA들(302)은 파일들(A-G)에 대응할 수 있으며, 파일들(A-G)의 각각은 특정 LBA 범위를 할당받는다. 예로서, 파일 A는 LBA 범위 0-39를 할당받고, 파일 B는 LBA 범위 40-99를 할당받고, 파일 C는 LBA 범위 100-339를 할당받고, 기타 등등이다. 각각의 파일(A-G)의 크기는 파일들 좌측의 번호 구간들로 표시된다.

게다가, 파일 시스템은 LBA들을 이용하여, NVM(예로서, 도 1의 NVM(120) 또는 도 2의 NVM(220))의 하나 이상의 메모리 위치에 저장된 데이터를 참조할 수 있다. 예를 들어, LBA들(302)의 각각의 LBA는 페이지들(304) 중 하나의 페이지에 맵핑될 수 있다. 따라서, 각각의 LBA는 대응 페이지의 물리 어드레스에 맵핑될 수 있다. 도 3에 도시된 바와 같이, 예를 들어, 파일 A에 대한 LBA 범위는 P2로 시작하고 P3-1로 끝나는 물리 어드레스들에 맵핑되고, 파일 B에 대한 LBA 범위는 P0으로 시작하고 P1-1로 끝나는 물리 어드레스들로 맵핑되고, 기타 등등이다.

도 4는 논리 대 물리 맵핑들 제공하는 데 사용될 수 있는 트리(400)의 블록도를 나타낸다. 특히, 트리(400)는 LBA 범위들(예로서, 도 3의 LBA들(302)의 LBA 범위)과 NVM(예로서, 도 1의 NVM(120) 또는 도 2의 NVM(220))의 대응하는 물리 어드레스들(예로서, 도 3의 페이지들(304)의 물리 어드레스들) 사이의 맵핑을 제공할 수 있다. 일부 실시예들에서, 트리(400)는 휘발성 메모리(예로서, 도 1의 메모리(114))에 저장되고 유지될 수 있다.

트리(400)는 다수의 노드를 포함할 수 있으며, 각각의 노드는 메모리 할당 목적을 위해 일관된 크기를 가질 수 있다(예로서, 각각의 노드는 64 바이트의 고정 크기를 가질 수 있다. 게다가, 트리(400)의 각각의 노드는 하나 이상의 엔트리를 포함할 수 있다. 예로서, 도 4에 도시된 바와 같이, 노드(402)는 4개의 엔트리(예로서, 엔트리 404-410)를 포함할 수 있다.

노드의 각각의 엔트리는 LBA 범위(예로서, 실행-길이 인코딩 압축된("rle 압축된") 범위)에 대응할 수 있고, 다른 노드에 대한 포인터("노드 포인터") 또는 NVM의 물리 어드레스("NAND 포인터")를 포함할 수 있다. 예를 들어, 도 4에 도시된 바와 같이, 엔트리들(404-410)은 LBA 범위들(340, 200, 260, 224)에 각각 대응하는 것으로 도시되어 있다.

더욱이, 도 4에 도시된 바와 같이, 엔트리들(404-410)의 각각은 트리 내의 추가 노드들을 가리키는 노드 포인터들을 가질 수 있다. 특히, 엔트리(404)는 노드(420)를 가리키는 것으로 도시되며, 이 노드는 또한 2개의 엔트리(예로서, 엔트리 430 및 432)를 갖는다. 이 분야의 기술자들은 엔트리들(406-410)이 트리(400) 내의 다른 노드들(예로서, 노드들 422-426)을 가리킬 수도 있다는 것을 알 것이다. 그러나, 간략화를 위해, 이러한 노드들은 상세히 설명되지 않고, 파선 박스들로서 도시된다.

엔트리들(404-410)의 각각은 특정 LBA 범위가 기입된 횟수를 나타낼 수 있는 카운터들(412-415)을 포함할 수 있다. 예를 들어, 도 4에 도시된 바와 같이, 엔트리들(404-410)의 각각에 대응하는 LBA 범위들은 10, 13, 20 및 10의 값들을 갖는 카운터들에 각각 갖는다. 카운터들은 아래에 더 상세히 설명될 것이다.

노드(420)의 엔트리(430)는 NVM의 물리 어드레스(예로서, 페이지 어드레스 P2)를 가리키는 NAND 포인터(433)를 갖는다. 이와 달리, 노드(420)의 엔트리(432)는 트리(400) 내의 다른 노드(예로서, 노드 440)를 가리키는 노드 포인터(438)를 갖는다. 간략화를 위해, 노드(440)는 상세히 도시되지 않고, 파선 박스로서 도시된다.

LBA 범위들(예로서, rle 압축된 범위들)이 LBA들 대신에 트리(400)에 저장되므로, NVM 인터페이스(예로서, 도 1의 NVM 인터페이스(118) 또는 도 2의 NVM 인터페이스(218))는 특정 파일의 논리 대 물리 맵핑을 얻기 위해 최상위 노드로부터 최하위 노드들까지 트리(400)를 트래버스(traverse)하는 것이 필요할 수 있다. 예를 들어, 파일의 LBA들에 기초하여, NVM 인터페이스는 트리(400)의 최상위 노드로부터 확장할 때 결과적인 어드레스 탤리(tally)가 파일의 LBA들과 매칭될 때까지 어드레스 탤리를 증가시킬 수 있다. 이 분야의 기술자들은 트리(400)가 임의의 적절한 트리 구조를 가질 수 있다는 것을 알 것이다. 일부 예들에서, 트리(400)는 예를 들어 b 트리 또는 b* 트리와 같이 특정 엔트리에 대한 검색 시간을 개선하는 트리 구조를 가질 수 있다.

LBA들(예로서, 시작 및 종료 LBA들)을 저장하는 맵핑 시스템에 비해, 트리(400)의 각각의 엔트리는 더 적은 양의 메모리를 할당받을 수 있으며, 이는 공간 제한들을 갖는 시스템에 유리하다. 특히, 트리(400)의 각각의 엔트리는 엔트리에 저장된 범위의 크기에 대응하는 수의 비트들을 할당받을 수 있다. LBA 범위의 크기가 증가함에 따라, 대응하는 엔트리에 할당되는 비트들의 수도 증가한다. 예를 들어, 노드의 엔트리가 작은 rle 압축된 범위에 대응하는 경우, 엔트리는 더 작은 크기(예를 들어, 4 바이트)를 할당받을 수 있다. 대안으로서, 노드의 엔트리가 큰 rle 압축된 범위를 저장하고 있는 경우, 엔트리는 더 큰 크기(예로서, 6 바이트)를 할당받을 수 있다. 특정 엔트리에 할당되는 크기는 동적이므로, 트리(400)의 각각의 엔트리는 가변 수의 엔트리들에 적합할 것이다.

더욱이, LBA들 대신에 LBA 범위들을 저장함으로써, 트리(400)의 각각의 노드에는 더 많은 포인터(예를 들어, 노드 및 NAND 포인터들)가 포함될 수 있다. 예를 들어, 트리(400)의 각각의 노드가 64 바이트를 할당받고, 이어서 각각의 엔트리가 4 내지 6 바이트를 할당받을 경우, 트리(400)의 각각의 노드는 10 내지 16 포인터를 저장하는 것이 가능할 수 있다.

도 4에 도시된 바와 같이, 트리(400)의 하나 이상의 엔트리는 엔트리와 관련된 정보를 포함하는 필드들을 가질 수 있다. 예로서, 엔트리(430)는 범위(434) 및 페이지 어드레스(435)를 포함할 수 있으며, 이들은 각각 엔트리의 LBA 범위 및 페이지 어드레스를 제공할 수 있다. 특히, 엔트리(430)가 파일 A에 대응하는 경우(도 3), 범위(434) 및 페이지 어드레스(435)는 각각 40 및 P2의 값들을 가질 수 있다.

게다가, 카운터(436)는 LBA 범위(434)가 기입된 횟수를 지시할 수 있다. 예를 들어, NVM 인터페이스가 파일 시스템(예로서, 도 2의 파일 시스템(210))이 특정 LBA 범위(예로서, LBA 범위에 할당된 파일)에 대한 기입 요청을 발행한 것을 검출할 때, NVM 인터페이스는 그 LBA 범위에 대응하는 카운터를 증가시킬 수 있다(예로서, 카운터를 1만큼 증가시킬 수 있다). 도 4에 도시된 예에서, 예를 들어, 카운터(436)는 범위(434)가 지금까지 4회 기입되었음을 지시한다. 이 분야의 기술자들은 엔트리들(404-410, 430, 432)의 각각이 도 4에 도시되지 않은 추가적인 필드들을 포함할 수 있다는 것을 알 것이다.

일반적으로, 트리(400)의 엔트리들에 대응하는 카운터들은 하나의 데이터가 얼마나 동적 또는 정적인지에 대한 지시를 제공할 수 있다. 예를 들어, 데이터가 새로운 파일에 처음 기입될 때, 파일과 관련된 데이터가 동적인지 또는 정적인지가 불명확할 수 있다. 그러나, 파일이 계속 갱신될 때, 파일이 기입된 횟수에 기초하여, 파일과 관련된 데이터가 동적 데이터인지에 대한 추정이 이루어질 수 있다. 본 명세서에서 사용될 때, "동적 데이터"는 자주 갱신 또는 변경되는 NVM에 저장된 유효 데이터일 수 있다. 이와 달리, "정적 데이터"는 거의 갱신 또는 변경되지 않는 NVM에 저장된 유효 데이터일 수 있다.

트리(400)의 카운터들은 하나 이상의 이벤트의 발생에 따라 다양한 방식으로 변경될 수 있다. 예를 들어, 트리 내의 엔트리에 대응하는 카운터는 결국 최대값(예로서, 8비트 카운터의 경우 0xff)에서 포화될 수 있다. 따라서, 일부 예들에서, NVM 인터페이스는 트리(400)의 카운터들을 모니터링하고, 트리(400) 내의 카운터가 언제 최대값에 도달하였는지를 검출할 수 있다. 카운터가 최대값에 도달한 것을 검출한 때, NVM 인터페이스는 트리의 모든 카운터들의 값들을 반감시킬 수 있다. 이것이 가능한 이유는 시스템 내의 데이터의 동적/정적 특성들의 측정이 상대적이기 때문이다.

다른 예로서, 연속적인 LBA 범위가 둘 이상의 범위로 분할되는 경우, NVM 인터페이스는 LBA 범위와 이전에 관련된 카운터를 둘 이상의 분할된 범위 각각과 관련된 엔트리에 복사할 수 있다. 이어서, NVM 인터페이스는 기입되고 있는 분할된 범위들과 관련된 카운터들을 증가시킬 수 있다. 도 4에 도시된 예에서, 예를 들어, LBA 범위(434)가 2개의 범위(예로서, 하위 범위 및 상위 범위)로 분할되는 경우, NVM 인터페이스는 카운터(436)의 값을 결과적인 엔트리들의 각각에 복사할 수 있다. 이어서, 상위 범위에 대해 기입 요청이 발행되는 경우, NVM 인터페이스는 상위 범위의 카운터를 갱신할 수 있지만, 하위 범위의 카운터에 대해서는 동일 값을 유지할 수 있다.

또 다른 예로서, NVM 인터페이스가 LBA 범위가 삭제된 것으로 결정하는 경우, NVM 인터페이스는 LBA 범위에 대응하는 카운터를 디폴트 값(예로서, 0의 디폴트 값)으로 재설정할 수 있다. 이것은 특정 LBA 범위에 기입되는 데이터의 동적 특성들이 종종 LBA 범위에 할당되는 파일의 타입에 의존할 수 있기 때문이다. 따라서, LBA 범위에 할당되는 새로운 파일은 LBA 범위에 할당된 이전 파일과 다른 동적 특성들을 가질 수 있으며, 따라서 트리(400) 내의 대응 카운터도 재설정되어야 한다.

일부 실시예들에서, 트리(400)의 하나 이상의 엔트리는 데이터가 애플리케이션 및/또는 운영 체제에 의해 특정 LBA 범위에 최종 기입된(예를 들어, 데이터가 호스트에 의해 최종 기입된) 나이에 대응할 수 있는 사용자 위브 시퀀스(437)도 포함할 수 있다. 일부 예들에서, 사용자 위브 시퀀스(437)는 LBA 범위에 대해 데이터 갱신들이 이루어질 때 증가하는 카운터(예로서, 48비트 카운터)일 수 있다. 예를 들어, 도 4에 도시된 바와 같이, 예를 들어, 트리(400) 내의 사용자 위브 시퀀스(437)는 데이터가 범위(434)에 최종 기입된 나이가 10임을 지시한다.

이 분야의 기술자들은, 트리(400)에 사용자 위브 시퀀스를 저장하는 대신에 또는 그에 더하여, 데이터의 사용자 위브 시퀀스가 시스템 내의 임의의 다른 적절한 위치에 저장될 수 있다는 것을 알 것이다. 예를 들어, 사용자 위브 시퀀스는 NVM(예로서, 도 1의 NVM(120) 또는 도 2의 NVM(220))의 페이지 내에 메타데이터로서 저장될 수 있다.

이제, 도 5를 참조하면, 메타데이터(500)는 NVM(예로서, 도 1의 NVM(120) 또는 도 2의 NVM(220))에 저장된 사용자 데이터와 연관될 수 있는 상이한 타입의 메타데이터를 나타낼 수 있다. 도 5에 도시된 바와 같이, 메타데이터(500)는 데이터가 애플리케이션 및/또는 운영 체제에 의해 관련 LBA 범위(예로서, LBA 범위 506)에 최종 기입된 나이에 대응할 수 있는 사용자 위브 시퀀스(502)를 포함할 수 있다. 결과적으로, 사용자 위브 시퀀스(502)는 사용자 위브 시퀀스(437)(도 4)와 유사할 수 있다. 결과적으로, 나중에 비교를 행하는 것이 필요할 때, NVM 인터페이스는 트리(예로서, 도 4의 트리(400)) 또는 메타데이터(500)로부터 사용자 위브 시퀀스를 얻는 것이 가능할 수 있다.

일부 실시예들에서, 메타데이터(500)는 데이터가 임의의 소스에 의해(예로서, GC 프로세스에 의해 또는 애플리케이션 또는 운영 체제에 의해) LBA 범위(506)에 최종 기입된 나이에 대응할 수 있는 위브 시퀀스(504)를 포함할 수 있다. 이 분야의 기술자들은 임의의 적절한 타입의 메타데이터가 NVM에 저장될 수 있다는 것을 알 것이다. 예를 들어, 도 5에 도시된 바와 같이, 메타데이터(500)는 사용자 데이터와 관련된 하나 이상의 페이지 어드레스에 대응할 수 있는 페이지 어드레스(505)도 포함할 수 있다. 다른 예로서, (도 5의 카운터들(412-415) 또는 카운터(436)와 유사한) 하나 이상의 카운터 및/또는 (도 5에 도시되지 않은) ECC 데이터도 메타데이터(500)에 포함될 수 있다. 이 분야의 기술자들은 위브 시퀀스가 그 대신에 또는 그에 더하여 트리(예로서, 도 4의 트리(400))에 저장될 수 있다는 것도 알 것이다.

임의의 적절한 접근법을 이용하여, LBA 범위(예로서, 파일)와 관련된 데이터가 동적인지를 결정할 수 있다. 일부 실시예들에서, NVM 인터페이스는 LBA 범위와 관련된 동적 값이 사전 결정된 임계치 이상인지를 결정할 수 있다. 동적 값은 LBA 범위의 카운터(예로서, 도 4의 카운터들(412-415) 중 하나 또는 카운터(436)), 사용자 위브 시퀀스, 위브 시퀀스, 임의의 다른 적절한 값 및/또는 이들의 임의 조합에 대응할 수 있다.

따라서, 사전 결정된 임계치는 NVM에 저장된 데이터의 평균 동적 값에 대응할 수 있다. 일부 예들에서, 사전 결정된 임계치는 트리(400)를 스크러빙(scrubbing)함으로써 얻어진 휴리스틱들(heuristics)을 이용하여 결정될 수 있다. 따라서, 평균 동적 값은 파일 시스템에 의한 기입 발행들의 총 수 및 NVM 상에 저장된 모든 데이터의 동적 특성들에 따라 시간에 따라 변할 수 있다. 따라서, 특정 데이터가 동적인지에 대한 결정은 NVM에 저장된 모든 데이터의 평균 동적 값과 관련될 수 있다.

일례로서, NVM 인터페이스는 먼저 트리(400)의 각각의 노드를 스크러빙하여 NVM에 저장된 데이터의 동적 특성들의 분포를 결정함으로써 사전 결정 임계치를 얻을 수 있다. 이어서, 동적 특성들의 분포를 이용하여, NVM 인터페이스는 NVM에 저장된 데이터의 평균 동적 값을 계산할 수 있다.

다른 실시예들에서, NVM 인터페이스는 카운터와 데이터의 나이, 예컨대 데이터의 사용자 위브 시퀀스(예로서, 도 4의 사용자 위브 시퀀스(437) 또는 도 5의 사용자 위브 시퀀스(502)) 사이의 상대 비교를 수행함으로써 LBA 범위와 관련된 데이터가 동적인지를 결정할 수 있다. 일부 실시예들에서, NVM 인터페이스는 사용자 위브 시퀀스를 시스템의 현재 나이와 비교함으로써 사용자 위브 시퀀스가 젊었는지 또는 늙었는지를 결정할 수 있다.

사용자 위브 시퀀스가 젊었는지 또는 늙었는지를 결정한 후에, NVM 인터페이스는 사용자 위브 시퀀스와 카운터를 비교할 수 있다. 예를 들어, 사용자 위브 시퀀스가 비교적 젊고, 카운터가 높은 값을 갖는 경우(예로서, LBA 범위가 자주 기입된 경우), NVM 인터페이스는 데이터가 비교적 동적인 것으로 결정할 수 있다. 대안으로서, 사용자 위브 시퀀스가 비교적 늙었고, 카운터가 작은 값을 갖는 경우(예로서, LBA 범위가 드물게 기입된 경우), NVM 인터페이스는 데이터가 비교적 정적인 것으로 결정할 수 있다. 더구나, 사용자 위브 시퀀스가 비교적 늙었고, 카운터가 높은 값을 갖는 경우, NVM 인터페이스는 데이터가 동적이었지만 현재는 정적인 것으로 결정할 수 있다. 이 분야의 기술자들은 NVM 인터페이스가 카운터와 사용자 위브 시퀀스를 비교하는 대신에 카운터와 위브 시퀀스(예로서, 도 5의 위브 시퀀스(504)) 또는 LBA 범위가 최초 기입된 나이를 비교할 수 있다는 것을 알 것이다.

추가 실시예들에서, NVM 인터페이스는 LBA 범위가 최종 기입된 나이와 LBA 범위가 최초 기입된 나이를 비교함으로써 LBA 범위와 관련된 데이터가 동적인지를 결정할 수 있다. LBA 범위가 최종 기입된 나이는 위브 시퀀스(예로서, 도 5의 위브 시퀀스(504)) 또는 사용자 위브 시퀀스(예로서, 도 4의 사용자 위브 시퀀스(437) 또는 도 5의 사용자 위브 시퀀스(502))에 대응할 수 있다.

위의 비교에 기초하여, NVM 인터페이스는 나이 차이를 구할 수 있고, 나이 차이가 사전 결정된 임계치보다 작은지를 결정할 수 있다. 나이 차이가 사전 결정된 임계치 아래인 경우, NVM 인터페이스는 LBA 범위와 관련된 데이터가 동적인 것으로 결정할 수 있다.

추가 실시예들에서, NVM 인터페이스는 데이터의 나이(예로서, 사용자 위브 시퀀스 또는 위브 시퀀스)와 최종 부트-업 이벤트의 시간을 비교함으로써 데이터가 동적인지를 결정할 수 있다. 최종 부트-업 이벤트의 시간은 데이터의 나이와 비교하기 위한 상대 기준선을 설정할 수 있다.

더 추가적인 실시예들에서, NVM 인터페이스는 운영 체제로부터 수신된 정보에 기초하여 데이터가 동적인지를 결정할 수 있다. 예를 들어, 하나 이상의 LBA, LBA 카운트 및 NVM에 저장될 데이터와 관련된 버퍼를 제공하는 것에 더하여, 운영 체제는 데이터가 정적인지에 관한 정보도 제공할 수 있다.

이제, 도 6-8을 참조하면, 본 발명의 다양한 실시예들에 따른 예시적인 프로세스들의 흐름도들이 도시되어 있다. 이러한 프로세스들은 시스템(예로서, 도 1의 전자 장치(100))의 하나 이상의 컴포넌트에 의해 실행될 수 있다. 예를 들어, 도 6-8의 프로세스들 내의 단계들 중 적어도 일부는 NVM 인터페이스(예로서, 도 1의 NVM 인터페이스(118) 또는 도 2의 NVM 인터페이스(218))에 의해 수행될 수 있다.

먼저, 도 6을 참조하면, 데이터를 NVM(예로서, 도 1의 NVM(120) 또는 도 2의 NVM(220))에 프로그래밍하기 위한 프로세스(600)가 도시되어 있다. 프로세스(600)는 단계 602에서 시작할 수 있다. 단계 604에서, NVM 인터페이스는 LBA 범위에 대응하는 기입 요청을 수신할 수 있다. 예를 들어, NVM 인터페이스는 LBA 범위(434)(도 4)에 대한 기입 요청을 수신할 수 있다.

단계 606에서, NVM 인터페이스는 트리로부터 적어도 하나의 파라미터를 얻을 수 있으며, 트리는 논리 대 물리 어드레스 맵핑들을 저장할 수 있다. 예로서, NVM 인터페이스는 먼저 LBA 범위에 대응하는 트리(예로서, 도 4의 트리(400)) 내의 엔트리를 식별할 수 있다. 엔트리를 식별한 후에, NVM 인터페이스는 식별된 엔트리로부터 적어도 하나의 파라미터를 얻을 수 있다. 적어도 하나의 파라미터는 LBA 범위가 기입된 횟수를 지시하는 카운터(예로서, 도 4의 카운터들(412-415) 중 하나 또는 카운터(436)) 및/또는 데이터가 애플리케이션 및/또는 운영 체제에 의해 LBA 범위에 최종 기입된 나이에 대응하는 사용자 위브 시퀀스(예로서, 도 4의 사용자 위브 시퀀스(437))를 포함할 수 있다.

단계 608로 계속되어, NVM 인터페이스는 적어도 하나의 파라미터에 적어도 부분적으로 기초하여 LBA 범위와 관련된 데이터가 동적인지를 결정할 수 있다. 예를 들어, NVM 인터페이스는 LBA 범위와 관련된 카운터가 사전 결정된 임계치(예로서, 트리로부터 얻어진 휴리스틱들을 이용하여 결정된 NVM에 저장된 데이터의 평균 동적 값) 이상인지를 결정할 수 있다.

다른 예로서, NVM 인터페이스는 카운터와 데이터의 나이 사이의 상대 비교를 수행할 수 있다. 데이터의 나이는 예를 들어 데이터의 사용자 위브 시퀀스, 데이터의 위브 시퀀스(예로서, 도 5의 위브 시퀀스(504)) 또는 LBA 범위가 최초 기입된 나이와 같은 임의의 적절한 나이일 수 있다. 또 다른 예로서, NVM 인터페이스는 LBA 범위가 최종 기입된 나이(예로서, 사용자 위브 시퀀스 또는 위브 시퀀스)와 LBA 범위가 최초 기입된 나이를 비교할 수 있다.

단계 608에서 NVM 인터페이스가 LBA 범위와 관련된 데이터가 동적인 것으로 결정하는 경우, 프로세스(600)는 단계 610으로 이동할 수 있다. 단계 610에서, NVM 인터페이스는 기입 요청과 관련된 데이터를 NVM의 동적 스트림 블록에 프로그래밍하도록 버스 제어기(예로서, 도 2의 NVM 버스 제어기(216))에 지시할 수 있다. 이어서, 프로세스(600)는 단계 612에서 종료될 수 있다.

본 명세서에서 사용될 때, "동적 스트림 블록"은 NVM 인터페이스에 의해 동적 스트림의 일부로서 지정된 NVM의 임의의 적절한 블록일 수 있다. 동적인 것으로 분류되는 착신 데이터는 하나 이상의 동적 블록에 선택적으로 배치될 수 있다. 예를 들어, 일 실시예에서, 동적 스트림 블록은 이전에는 나중에 동적 스트림 블록으로 지정된 NVM의 낮게 사이클링된 블록이었을 수 있다.

단계 608에서, NVM 인터페이스가 LBA 범위와 관련된 데이터가 동적이 아닌 것으로 대신 결정하는 경우, 프로세스(600)는 단계 614로 이동할 수 있다. 단계 614에서, NVM 인터페이스는 기입 요청과 관련된 데이터를 NVM의 정적 스트림 블록에 프로그래밍하도록 버스 제어기에 지시할 수 있다. 이어서, 프로세스(600)는 단계 612에서 종료될 수 있다.

본 명세서에서 사용될 때, "정적 스트림 블록"은 NVM 인터페이스에 의해 정적 스트림의 일부로서 지정된 NVM의 임의의 적절한 블록일 수 있다. 정적인 것으로 분류되는 착신 데이터는 하나 이상의 정적 블록에 선택적으로 배치될 수 있다. 일 실시예에서, 정적 스트림 블록은 이전에는 나중에 정적 스트림 블록으로 지정된 NVM의 높게 사이클링된 블록이었을 수 있다.

일부 실시예들에서, NVM 인터페이스는 개별 기입 포인터들을 이용하여, 동적 스트림 블록 또는 정적 스트림 블록에 기입할 수 있다. 예를 들어, NVM 인터페이스는 동적 기입 포인터를 이용하여 동적 스트림 블록에 기입하고, 정적 기입 포인터를 이용하여 정적 스트림 블록에 기입할 수 있다.

따라서, 특정 데이터가 동적인지 또는 정적인지를 결정함으로써, NVM 인터페이스는 NVM 상의 데이터의 초기 배치를 더 양호하게 결정할 수 있다. 이것은 쓰레기 수거("GC")의 효율을 향상시켜 NVM의 마모를 줄일 수 있다. 예로서, 동적 및 정적 데이터를 NVM 상의 개별 블록들로 분할함으로써, NVM 인터페이스는 NVM의 정적 스트림 블록 대신에 동적 스트림 블록에 대해 GC를 수행하는 것을 선택할 수 있다. 동적 스트림 블록은 결국에는 동적 데이터가 갱신되는 빈도로 인해 유효 페이지를 거의 또는 전혀 갖지 않을 수 있으므로, GC 동안에 이동되어야 하는 유효 데이터의 양은 최소가 된다. 결과적으로, GC 기입 증폭이 감소할 수 있다.

예를 들어, 이제, 도 7을 참조하면, NVM(예로서, 도 1의 NVM(120) 또는 도 2의 NVM(220))에 대해 GC를 수행하기 위한 예시적인 프로세스의 흐름도가 도시되어 있다. 프로세스(700)는 단계 702에서 시작될 수 있다. 단계 704에서, NVM 인터페이스는 NVM의 블록에 대해 GC가 수행되는 것이 필요한 것으로 결정할 수 있다. 단계 706에서, NVM 인터페이스는 유효 데이터를 갖는 블록의 페이지를 선택할 수 있다.

단계 708로 계속하여, NVM 인터페이스는 페이지 상에 저장된 데이터가 동적 데이터인지를 결정할 수 있다. 전술한 바와 같이, NVM 인터페이스는 임의의 적절한 접근법을 이용하여 데이터가 동적인지를 결정할 수 있다. 예로서, NVM 인터페이스는 데이터의 LBA 범위에 대응하는 트리(예로서, 도 4의 트리(400))의 엔트리(예로서, 도 4의 엔트리(430))를 발견할 수 있다. 이어서, NVM 인터페이스는 엔트리의 카운터(예로서, 도 4의 카운터들(412-415) 중 하나 또는 카운터(436))가 사전 결정된 임계치(예로서, 평균 동적 값) 이상인지를 결정할 수 있다. 다른 예로서, NVM 인터페이스는 운영 체제로부터 수신된 정보에 기초하여 데이터가 동적인지를 결정할 수 있다.

단계 708에서 NVM 인터페이스가 페이지에 저장된 데이터가 동적 데이터인 것으로 결정하는 경우, 프로세스(700)는 단계 710으로 이동할 수 있다. 예를 들어, NVM 인터페이스는 트리의 대응하는 엔트리의 카운터가 사전 결정된 임계치 이상인 것으로 결정할 수 있다.

단계 710에서, NVM 인터페이스는 데이터를 NVM의 동적 스트림 블록에 복사하도록 버스 제어기(예로서, 도 2의 NVM 버스 제어기(216))에 지시할 수 있다. 이어서, 단계 712로 계속하여, NVM 인터페이스는 유효 데이터를 갖는 블록의 추가 페이지가 존재하는지를 결정할 수 있다.

단계 712에서 NVM 인터페이스가 유효 데이터를 갖는 추가 페이지가 존재하는 것으로 결정하는 경우, 프로세스(700)는 단계 708로 복귀할 수 있고, 여기서 NVM 인터페이스는 블록의 다른 페이지에 저장된 데이터가 동적 데이터인지를 결정할 수 있다. 이어서, NVM 인터페이스는 유효 데이터를 갖는 블록의 각각의 페이지에 대해 이 프로세스를 반복할 수 있다.

단계 712를 다시 참조하면, NVM 인터페이스가 유효 데이터를 갖는 블록의 추가 페이지가 존재하지 않는 것으로 대신 결정하는 경우, 프로세스(700)는 단계 714로 이동할 수 있다.

단계 714에서, NVM 인터페이스는 블록을 소거하도록 버스 제어기에 지시할 수 있고, 프로세스(700)는 단계 716에서 종료될 수 있다. 블록의 소거는 결과적으로 블록이 새로운 데이터로 재프로그래밍될 수 있게 한다.

단계 708을 다시 참조하면, NVM 인터페이스가 페이지에 저장된 데이터가 동적 데이터가 아닌 것으로 대신 결정하는 경우, 프로세스(700)는 단계 718로 이동할 수 있다. 예로서, NVM 인터페이스는 트리의 대응 엔트리의 카운터가 사전 결정된 임계치보다 작은 것으로 결정할 수 있다. 결과적으로, NVM 인터페이스는 데이터가 정적인 것으로 결정할 수 있다.

단계 718에서, NVM 인터페이스는 데이터를 NVM의 정적 스트림 블록에 복사하도록 버스 제어기에 지시할 수 있다. 이어서, 프로세스(700)는 단계 712로 이동할 수 있으며, 여기서 NVM 인터페이스는 유효 데이터를 갖는 블록의 추가 페이지가 존재하는지를 결정할 수 있다.

따라서, 그러한 접근법을 이용하여, NVM 인터페이스는 데이터가 동적인지 또는 정적인지에 대한 초기 결정을 변경하는 것이 가능할 수 있다. 따라서, 특정 데이터가 동적 데이터에서 정적 데이터로 또는 정적 데이터에서 동적 데이터로 변경된 경우, NVM 인터페이스는 블록에 대한 GC를 수행하는 동안 그 데이터의 배치를 변경할 수 있다.

이제, 도 8을 참조하면, NVM(예로서, 도 1의 NVM(120) 또는 도 2의 NVM(220))에 대해 마모 균등화를 수행할지를 결정하기 위한 예시적인 프로세스(800)의 흐름도가 도시되어 있다. 프로세스(800)는 단계 802에서 시작할 수 있다.

단계 804에서, NVM 인터페이스는 트리(예로서, 도 4의 트리(400))의 다수의 노드의 각각의 노드를 스크러빙하여, NVM에 저장된 데이터의 동적 특성들의 분포를 결정할 수 있다. 이어서, NVM 인터페이스는 동적 특성들의 분포에 적어도 부분적으로 기초하여 NVM에 대한 마모 균등화가 필요한지를 결정할 수 있다. 일부 예들에서, NVM 인터페이스는 동적 특성들의 분포를 이용하여 NVM에 저장된 데이터의 평균 동적 값을 계산할 수 있다.

예를 들어, 단계 806에서, NVM 인터페이스는 NVM의 높게 사이클링된 블록인 블록을 NVM으로부터 선택할 수 있다. 일부 예들에서, 블록은 특정 수의 사이클(예를 들어, 소거 사이클 및/또는 기입 사이클)을 가질 수 있으며, 사이클들의 수는 NVM의 다른 블록들의 사이클링을 사전 결정된 갭만큼 초과한다.

단계 808에서 계속하여, NVM 인터페이스는 블록이 동적 블록인지를 결정할 수 있다. 예를 들어, 트리(예로서, 도 4의 트리(400))로부터 얻어진 또는 메타데이터(예로서, 도 5의 메타데이터(500))로부터 얻어진 하나 이상의 파라미터에 기초하여, NVM 인터페이스는 블록에 저장된 데이터의 블록 동적 값을 계산할 수 있다.

이어서, NVM 인터페이스는 블록 동적 값과 NVM에 저장된 데이터의 동적 특성을 비교할 수 있다. 일부 실시예들에서, NVM 인터페이스는 블록에 저장된 데이터가 평균 동적 값 이상인 블록 동적 값을 갖는지를 결정할 수 있다. 다른 실시예들에서, NVM 인터페이스는 블록에 저장된 데이터가 평균 동적 값의 상수 배인 블록 동적 값을 갖는지를 결정할 수 있다. 추가 실시예들에서, NVM 인터페이스는 블록에 저장된 데이터가 평균 동적 값으로부터 사전 결정된 수의 표준 편차들 밖인 블록 동적 값을 갖는지를 결정할 수 있다.

단계 808에서 NVM 인터페이스가 블록이 동적 블록이 아닌 것으로 결정하는 경우, 프로세스(800)는 단계 810에서 종료할 수 있다. 결과적으로, NVM 인터페이스는 블록 상의 데이터를 유지할 수 있다. 이러한 방식으로, NVM 인터페이스는 블록에 대한 마모 균등화의 수행이 불필요한 것으로 결정되었으므로 이를 피할 수 있다.

단계 808에서 NVM 인터페이스가 블록이 동적 블록인 것으로 대신 결정하는 경우, 프로세스(800)는 단계 812로 이동할 수 있다. 단계 812에서, NVM 인터페이스는 블록을 정적 스트림 블록으로 지정할 수 있다. 결과적으로, 파일 시스템(예로서, 도 2의 파일 시스템(210))으로부터 수신된 미래의 정적 데이터는 블록에 저장될 수 있다.

이어서, 단계 814로 계속하여, NVM 인터페이스는 블록의 페이지에 저장된 데이터가 동적 데이터인지를 결정할 수 있다. 단계 814에서 NVM이 페이지에 저장된 데이터가 동적 데이터인 것으로 결정하는 경우, 프로세스(800)는 단계 816으로 이동할 수 있다.

단계 816에서, NVM 인터페이스는 페이지에 저장된 데이터를 동적 스트림 블록에 복사하도록 버스 제어기(예로서, 도 2의 NVM 버스 제어기(216))에 지시할 수 있다. 이어서, 프로세스(800)는 단계 818로 이동할 수 있다.

단계 818에서, NVM 인터페이스는 유효 데이터를 갖는 블록 상의 추가 페이지가 존재하는지를 결정할 수 있다. 단계 818에서 NVM 인터페이스가 유효 데이터를 갖는 추가 페이지가 존재하는 것으로 결정하는 경우, 프로세스(800)는 단계 814로 복귀할 수 있다. 단계 814에서, NVM 인터페이스는 블록의 다른 페이지에 저장된 데이터가 동적 데이터인지를 결정할 수 있다. 이어서, NVM 인터페이스는 유효 데이터를 갖는 블록의 각각의 페이지에 대해 이 프로세스를 반복할 수 있다.

단계 818에서 NVM 인터페이스가 유효 데이터를 갖는 추가 페이지가 존재하지 않는 것으로 결정하는 경우, 프로세스(800)는 단계 810에서 종료할 수 있다. 결과적으로, GC가 블록에 대해 수행될 수 있다. 예컨대, 블록에 저장된 모든 유효 데이터가 NVM의 다른 메모리 위치들로 복사되면, 블록이 소거될 수 있다. 블록 소거 후, NVM 인터페이스는 블록 상의 (예로서, GC 및/또는 호스트 기입들로부터의) 정적 데이터 배치를 시작할 수 있다.

단계 814를 다시 참조하면, NVM 인터페이스가 페이지에 저장된 데이터가 동적 데이터가 아닌 것으로 대신 결정하는 경우, 프로세스(800)는 단계 820으로 이동할 수 있다. 단계 820에서, NVM 인터페이스는 페이지에 저장된 데이터를 정적 스트림 블록에 복사하도록 버스 인터페이스에 지시할 수 있다. 이어서, 프로세서(800)는 단계 818로 이동할 수 있으며, 여기서 NVM 인터페이스는 유효 데이터를 갖는 블록 상의 추가 페이지가 존재하는지를 결정할 수 있다.

데이터가 동적인지 정적인지를 결정하고 이러한 정보와 마모 균등화를 통합함으로써, 시스템은 마모 균등화가 필요한지에 대한 더 나은 결정을 행할 수 있다. 불필요한 마모 균등화를 피함으로써, 시스템은 NVM에 대해 수행되는 사이클들의 수 및 시스템의 총 대역폭을 줄일 수 있다. 더욱이, 데이터가 동적인지에 대한 정보는 또한 시스템이 블록에 대한 마모 균등화를 수행하는 동안 데이터를 어디로 이동시킬지에 대한 더 나은 결정을 행할 수 있게 한다.

더구나, 이러한 접근법은 시스템이 일반적으로 전체 블록에 대해 마모 균등화가 수행되는 통상의 마모 균등화 시스템에서 가능한 것보다 정밀한 입도(예로서, 블록의 페이지들)로 마모 균등화 결정을 행할 수 있게 한다. 이러한 정밀하게 튜닝된 결정 프로세스는 또한 NVM에 대한 마모의 양을 줄일 수 있고, NVM의 유효 수명을 연장할 수 있다.

도 6-8 각각의 프로세스 600, 700 및 800은 예시적일 뿐이다. 본 발명의 범위를 벗어나지 않고, 임의 단계들이 제거, 변경 또는 결합될 수 있으며, 임의의 추가 단계들이 추가될 수 있다.

설명된 본 발명의 실시예들은 한정이 아니라 예시적인 목적으로 제공된다.

Claims

데이터를 저장하도록 동작하는 복수의 블록을 포함하는 비휘발성 메모리("NVM");
복수의 노드를 포함하는 트리를 저장하기 위한 휘발성 메모리 - 상기 복수의 노드 중 적어도 하나의 노드는 실행-길이 인코딩 압축된 논리 블록 어드레스("LBA") 범위들을 포함함 -; 및
메모리 인터페이스
를 포함하고,
상기 메모리 인터페이스는
상기 NVM과 통신하기 위한 버스 제어기; 및
제어 회로
를 포함하고,
상기 제어 회로는
상기 NVM의 블록에 대해 쓰레기 수거(garbage collection)를 수행할 필요가 있는 것을 결정하고;
유효 데이터를 갖는 상기 블록의 각각의 페이지에 대해, 상기 트리로부터 얻은 파라미터에 적어도 부분적으로 기초하여, 상기 페이지에 저장된 데이터가 동적인지를 결정하고;
상기 데이터가 동적이라는 결정에 응답하여, 상기 데이터를 상기 NVM의 동적 스트림 블록에 복사하도록
동작하는 시스템.
제1항에 있어서,
상기 제어 회로는 상기 블록을 소거하도록 동작하는, 시스템.
제1항에 있어서,
상기 제어 회로는
복수의 엔트리를 포함하는 상기 트리를 유지하고 - 상기 트리는 논리 블록 어드레스("LBA") 범위들과 상기 NVM 내의 대응하는 물리 어드레스들 간의 맵핑을 제공함 -;
상기 트리 내의 복수의 카운터를 모니터링하도록
동작하고,
상기 복수의 카운터의 각각의 카운터는 상기 복수의 엔트리 중의 엔트리에 대응하고, 상기 카운터는 대응하는 LBA 범위가 기입된 횟수를 나타내는, 시스템.
제3항에 있어서,
상기 제어 회로는
상기 복수의 엔트리 중에서, 상기 데이터의 LBA 범위에 대응하는 엔트리를 찾고;
상기 찾아진 엔트리의 카운터가 사전 결정된 임계치 이상인지를 결정하고;
상기 찾아진 엔트리의 카운터가 사전 결정된 임계치 이상이라는 결정에 응답하여 상기 데이터가 동적인 것으로 결정하도록
동작하는, 시스템.
제4항에 있어서,
상기 제어 회로는
상기 찾아진 엔트리의 카운터가 상기 사전 결정된 임계치보다 작다는 결정에 응답하여 상기 데이터가 정적인 것으로 결정하고;
상기 데이터를 상기 NVM의 정적 스트림 블록에 복사하도록
동작하는, 시스템.
제3항에 있어서,
상기 제어 회로는
상기 복수의 카운터 중의 하나의 카운터가 최대 값에 도달한 것을 검출하고;
상기 트리의 상기 복수의 카운터의 값들을 반감시키도록(halve)
동작하는, 시스템.
제3항에 있어서,
상기 제어 회로는
특정 LBA 범위가 삭제된 것으로 결정하고;
상기 복수의 카운터 중에서, 상기 특정 LBA 범위에 대응하는 카운터를 디폴트 값으로 재설정하도록
동작하는, 시스템.
제3항에 있어서,
상기 제어 회로는
파일 시스템이 특정 LBA 범위에 대한 기입 요청을 발행한 것을 검출하고;
상기 복수의 카운터 중에서, 상기 특정 LBA 범위에 대응하는 카운터를 증가시키도록
동작하는, 시스템.