[논문]LeaFTL: A Learning-Based Flash Translation Layerfor Solid-State Drives

 

1) LeaFTL should be able to automatically capture diverse data

access patterns, and generate memory-efficient address mapping

3.1 key Ideas of LeaFTL

기존에는 하나씩 메핑하는 방식을 취할때 buffer를 두는데 이걸 활용해서 leaftl은 이런 버퍼를 오버헤드를 최소화 한다.

총 128 개의 LPA-PPA 엔트리를 커버가 가능하다.

each learned index segment can be represented in 8 bytes: 1 byte for 𝑆𝐿𝑃𝐴 and 𝐿, respectively; 2 bytes for 𝐾, and 4 bytes for I

추가적인 데이터를 사용하지 않음으로 완전 랜덤한 경우도 완전 커버가 가능하다.

k : 16 -bit float

SLAP : 는 총 256개의 인덱스

3.2 Learned Index Segment

piecewise linear regression 방식으로 작은 단위로

k 는 기울기 I 는 bias 그리고 L은 segment의 인덱스 수, K=0 이면 1개있는 경우

accurate segment : 기울기와 bias에 따라서 실링의 정확한 PPA값 유추

approximate segement : 감마에 따라서 일정 범위도 넘어가도 허용

( 오차를 허용하기 때문에 misprediction 의 경우가 생긴ㄷ)

Size of Learned Index Segment.

여기서 k 비트의 가장 하위 비트가 타입을 지정한다. 0 이면 accurate , 1이면 approximate

3.3 Improve the Learning Efficiency

네, 맞습니다! 요점을 다시 정리하자면, LeaFTL은 데이터 버퍼에 있는 데이터를 LPA(논리적 페이지 주소)의 오름차순으로 정렬한 후에 플래시 메모리로 쓰기(저장)하는 방식입니다. 이렇게 정렬해서 저장하면, 플래시 메모리 상에서 PPA(물리적 페이지 주소)도 자연스럽게 오름차순으로 정렬됩니다.

이 정렬 과정은 LPA와 PPA 사이의 단조로운(오름차순) 매핑을 보장하여, 인덱스 관리를 더 효율적으로 만들고, 매핑 테이블의 크기도 줄여주는 효과를 가져옵니다.

3.4 Manage Learned Index Segments

로그 구조로 변경해서 그냥 겹치면 새로 만들어버린다. 그런데 이런건 나중에 compation을 해준다.

2) LeaFTL may incur address mispredictions, which could incur

additional flash accesses. LeaFTL should be tolerant of errors and have a low misprediction penalty

misprediction 의 경우

오차 범위를 감안한 approximate segments의 경우 OOB를 통하여 LPA가 매칭이 되었는지를 확인한다.

그래서 만약 잘못 예측을 한거라면 log flash accesses 를 통해서 고친다

그래서 이런 잘못 예측을 방지하기 위해서 인접한 LPA를 같이 OOB에 저장을 하게된다. 만약 page가 블럭의 처음이나 마지막이면 null값으로 채운다. 위의 사진처럼 인접한 LPA를 줘서 오차범위 안에 들어와도 허용

그래서 추가적인 access가 필요한게 아니라 틀리면 그냥 주변꺼 반환하는 한번의 access만으로 해결

3) LeaFTL should work coordinately with other core FTL functions

that include GC and wear leveling (§3.6).

먼저 leaftl 은 greedy 알고리즘을 통해서 지울 블럭을 탐색한다. 여기서 새로 써야하는 valid한 pages들은 DRAM buffer에 추가해서 sorting을 한 이후에 새로운 index segment를 학습하고 `

또한 wear leveling 을 보장하기 위해서 cold, hot block들을 throttling 와 swapping방식으로 처리한다.

4) LeaFTL should be lightweight and not incur much extra overhead to storage operations (§3.7, §3.8 and §3.9).

질문!!! 매핑 테이블을 대신하는거 같은데 여기서 그럼 매핑 테이블은 언제 생성되냐 버퍼에 넣고 하는거임?

creation of learned segments

먼저 데이터 버퍼가 SSD controller에 가득 차면 LPA를 기준으로 정렬해서 greedy piecewise linear regression 을 하여 index segment를 만든다.

3.8 Put It All Together

!! 질문 : 혹시 타임라인의 다른점은?

• Read Operation

먼저 캐시를 탐색하여 page 가 있는지 확인하고 없으면 LeaFTL에 가서 예측을 바로 하고 읽어온다. 하지만 miss나면 OOB로 확인해서 다시 반환해서 읽어온다.

• Write Operation

먼저 data cache 버퍼에 flash block size 만큼 데이터가 차면 sorting 하고나서 이걸 index segment를 만들어서 flash block에 넣는다.

그래서 생성된 index segment를 mapping table 에 저장한다. 그리고 이미 LPA가 메핑 테이블에 존재한다면 BVC, PVT 를 업데이트하고 GC 의 대상으로 삼는다.

1. abstract

실시간으로 데이터의 mapping 패턴을 regression을 통해서 학습해 나간다.

방식

1) LeaFTL should be able to automatically capture diverse data

access patterns, and generate memory-efficient address mapping

3.1 key Ideas of LeaFTL

기존에는 하나씩 메핑하는 방식을 취할때 buffer를 두는데 이걸 활용해서 leaftl은 이런 버퍼를 오버헤드를 최소화 한다.

총 128 개의 LPA-PPA 엔트리를 커버가 가능하다.

each learned index segment can be represented in 8 bytes: 1 byte for 𝑆𝐿𝑃𝐴 and 𝐿, respectively; 2 bytes for 𝐾, and 4 bytes for I

추가적인 데이터를 사용하지 않음으로 완전 랜덤한 경우도 완전 커버가 가능하다.

k : 16 -bit float

SLAP : 는 총 256개의 인덱스

3.2 Learned Index Segment

piecewise linear regression 방식으로 작은 단위로

k 는 기울기 I 는 bias 그리고 L은 segment의 인덱스 수, K=0 이면 1개있는 경우

accurate segment : 기울기와 bias에 따라서 실링의 정확한 PPA값 유추

approximate segement : 감마에 따라서 일정 범위도 넘어가도 허용

( 오차를 허용하기 때문에 misprediction 의 경우가 생긴ㄷ)

Size of Learned Index Segment.

여기서 k 비트의 가장 하위 비트가 타입을 지정한다. 0 이면 accurate , 1이면 approximate

3.3 Improve the Learning Efficiency

네, 맞습니다! 요점을 다시 정리하자면, LeaFTL은 데이터 버퍼에 있는 데이터를 LPA(논리적 페이지 주소)의 오름차순으로 정렬한 후에 플래시 메모리로 쓰기(저장)하는 방식입니다. 이렇게 정렬해서 저장하면, 플래시 메모리 상에서 PPA(물리적 페이지 주소)도 자연스럽게 오름차순으로 정렬됩니다.

이 정렬 과정은 LPA와 PPA 사이의 단조로운(오름차순) 매핑을 보장하여, 인덱스 관리를 더 효율적으로 만들고, 매핑 테이블의 크기도 줄여주는 효과를 가져옵니다.

3.4 Manage Learned Index Segments

로그 구조로 변경해서 그냥 겹치면 새로 만들어버린다. 그런데 이런건 나중에 compation을 해준다.

2) LeaFTL may incur address mispredictions, which could incur

additional flash accesses. LeaFTL should be tolerant of errors and have a low misprediction penalty

misprediction 의 경우

오차 범위를 감안한 approximate segments의 경우 OOB를 통하여 LPA가 매칭이 되었는지를 확인한다.

그래서 만약 잘못 예측을 한거라면 log flash accesses 를 통해서 고친다

그래서 이런 잘못 예측을 방지하기 위해서 인접한 LPA를 같이 OOB에 저장을 하게된다. 만약 page가 블럭의 처음이나 마지막이면 null값으로 채운다. 위의 사진처럼 인접한 LPA를 줘서 오차범위 안에 들어와도 허용

그래서 추가적인 access가 필요한게 아니라 틀리면 그냥 주변꺼 반환하는 한번의 access만으로 해결

3) LeaFTL should work coordinately with other core FTL functions

that include GC and wear leveling (§3.6).

먼저 leaftl 은 greedy 알고리즘을 통해서 지울 블럭을 탐색한다. 여기서 새로 써야하는 valid한 pages들은 DRAM buffer에 추가해서 sorting을 한 이후에 새로운 index segment를 학습하고 `

또한 wear leveling 을 보장하기 위해서 cold, hot block들을 throttling 와 swapping방식으로 처리한다.

4) LeaFTL should be lightweight and not incur much extra overhead to storage operations (§3.7, §3.8 and §3.9).

질문!!! 매핑 테이블을 대신하는거 같은데 여기서 그럼 매핑 테이블은 언제 생성되냐 버퍼에 넣고 하는거임?

creation of learned segments

먼저 데이터 버퍼가 SSD controller에 가득 차면 LPA를 기준으로 정렬해서 greedy piecewise linear regression 을 하여 index segment를 만든다.

3.8 Put It All Together

!! 질문 : 혹시 타임라인의 다른점은?

• Read Operation

먼저 캐시를 탐색하여 page 가 있는지 확인하고 없으면 LeaFTL에 가서 예측을 바로 하고 읽어온다. 하지만 miss나면 OOB로 확인해서 다시 반환해서 읽어온다.

• Write Operation

먼저 data cache 버퍼에 flash block size 만큼 데이터가 차면 sorting 하고나서 이걸 index segment를 만들어서 flash block에 넣는다.

그래서 생성된 index segment를 mapping table 에 저장한다. 그리고 이미 LPA가 메핑 테이블에 존재한다면 BVC, PVT 를 업데이트하고 GC 의 대상으로 삼는다.

1. abstract

실시간으로 데이터의 mapping 패턴을 regression을 통해서 학습해 나간다.

방식

1) LeaFTL should be able to automatically capture diverse data

access patterns, and generate memory-efficient address mapping

3.1 key Ideas of LeaFTL

기존에는 하나씩 메핑하는 방식을 취할때 buffer를 두는데 이걸 활용해서 leaftl은 이런 버퍼를 오버헤드를 최소화 한다.

총 128 개의 LPA-PPA 엔트리를 커버가 가능하다.

each learned index segment can be represented in 8 bytes: 1 byte for 𝑆𝐿𝑃𝐴 and 𝐿, respectively; 2 bytes for 𝐾, and 4 bytes for I

추가적인 데이터를 사용하지 않음으로 완전 랜덤한 경우도 완전 커버가 가능하다.

k : 16 -bit float

SLAP : 는 총 256개의 인덱스

3.2 Learned Index Segment

piecewise linear regression 방식으로 작은 단위로

k 는 기울기 I 는 bias 그리고 L은 segment의 인덱스 수, K=0 이면 1개있는 경우

accurate segment : 기울기와 bias에 따라서 실링의 정확한 PPA값 유추

approximate segement : 감마에 따라서 일정 범위도 넘어가도 허용

( 오차를 허용하기 때문에 misprediction 의 경우가 생긴ㄷ)

Size of Learned Index Segment.

여기서 k 비트의 가장 하위 비트가 타입을 지정한다. 0 이면 accurate , 1이면 approximate

3.3 Improve the Learning Efficiency

네, 맞습니다! 요점을 다시 정리하자면, LeaFTL은 데이터 버퍼에 있는 데이터를 LPA(논리적 페이지 주소)의 오름차순으로 정렬한 후에 플래시 메모리로 쓰기(저장)하는 방식입니다. 이렇게 정렬해서 저장하면, 플래시 메모리 상에서 PPA(물리적 페이지 주소)도 자연스럽게 오름차순으로 정렬됩니다.

이 정렬 과정은 LPA와 PPA 사이의 단조로운(오름차순) 매핑을 보장하여, 인덱스 관리를 더 효율적으로 만들고, 매핑 테이블의 크기도 줄여주는 효과를 가져옵니다.

3.4 Manage Learned Index Segments

로그 구조로 변경해서 그냥 겹치면 새로 만들어버린다. 그런데 이런건 나중에 compation을 해준다.

2) LeaFTL may incur address mispredictions, which could incur

additional flash accesses. LeaFTL should be tolerant of errors and have a low misprediction penalty

misprediction 의 경우

오차 범위를 감안한 approximate segments의 경우 OOB를 통하여 LPA가 매칭이 되었는지를 확인한다.

그래서 만약 잘못 예측을 한거라면 log flash accesses 를 통해서 고친다

그래서 이런 잘못 예측을 방지하기 위해서 인접한 LPA를 같이 OOB에 저장을 하게된다. 만약 page가 블럭의 처음이나 마지막이면 null값으로 채운다. 위의 사진처럼 인접한 LPA를 줘서 오차범위 안에 들어와도 허용

그래서 추가적인 access가 필요한게 아니라 틀리면 그냥 주변꺼 반환하는 한번의 access만으로 해결

3) LeaFTL should work coordinately with other core FTL functions

that include GC and wear leveling (§3.6).

먼저 leaftl 은 greedy 알고리즘을 통해서 지울 블럭을 탐색한다. 여기서 새로 써야하는 valid한 pages들은 DRAM buffer에 추가해서 sorting을 한 이후에 새로운 index segment를 학습하고 `

또한 wear leveling 을 보장하기 위해서 cold, hot block들을 throttling 와 swapping방식으로 처리한다.

4) LeaFTL should be lightweight and not incur much extra overhead to storage operations (§3.7, §3.8 and §3.9).

질문!!! 매핑 테이블을 대신하는거 같은데 여기서 그럼 매핑 테이블은 언제 생성되냐 버퍼에 넣고 하는거임?

creation of learned segments

먼저 데이터 버퍼가 SSD controller에 가득 차면 LPA를 기준으로 정렬해서 greedy piecewise linear regression 을 하여 index segment를 만든다.

3.8 Put It All Together

!! 질문 : 혹시 타임라인의 다른점은?

• Read Operation

먼저 캐시를 탐색하여 page 가 있는지 확인하고 없으면 LeaFTL에 가서 예측을 바로 하고 읽어온다. 하지만 miss나면 OOB로 확인해서 다시 반환해서 읽어온다.

• Write Operation

먼저 data cache 버퍼에 flash block size 만큼 데이터가 차면 sorting 하고나서 이걸 index segment를 만들어서 flash block에 넣는다.

그래서 생성된 index segment를 mapping table 에 저장한다. 그리고 이미 LPA가 메핑 테이블에 존재한다면 BVC, PVT 를 업데이트하고 GC 의 대상으로 삼는다.