BTT - Block Translation Table

BTT의 목적과 원자적 섹터 갱신

영구 메모리 기반 저장 장치는 바이트 단위, 더 정확히는 캐시 라인 단위로 I/O를 수행할 수 있지만, 흔히 이를 전통적인 블록 장치로 노출해야 합니다. 영구 메모리 블록 드라이버가 이 역할을 하지만 자체적으로 원자성을 보장하지는 않습니다.

전통적인 SSD는 보통 커패시터에 저장된 에너지로 진행 중인 블록 쓰기를 마치거나 펌웨어에서 처리해 torn sector를 방지합니다. 영구 메모리에서는 쓰기 도중 전원이 끊기면 블록에 이전 데이터와 새 데이터가 섞일 수 있고, 응용 프로그램은 이런 상태를 처리하지 못할 수 있습니다.

Block Translation Table, BTT는 영구 메모리 장치에 원자적 섹터 갱신 의미론을 제공합니다. 섹터 쓰기가 찢어지지 않는다고 가정하는 응용 프로그램을 그대로 지원하기 위해 stacked block device로 나타나며, 하위 저장 공간 일부를 메타데이터용으로 예약합니다.

핵심은 볼륨의 모든 블록을 다시 매핑하는 indirection table입니다. BTT는 원자적 섹터 갱신 기능만 제공하는 매우 단순한 파일 시스템으로 생각할 수 있습니다.

=============================
BTT - Block Translation Table
=============================


1. Introduction
===============

Persistent memory based storage is able to perform IO at byte (or more
accurately, cache line) granularity. However, we often want to expose such
storage as traditional block devices. The block drivers for persistent memory
will do exactly this. However, they do not provide any atomicity guarantees.
Traditional SSDs typically provide protection against torn sectors in hardware,
using stored energy in capacitors to complete in-flight block writes, or perhaps
in firmware. We don't have this luxury with persistent memory - if a write is in
progress, and we experience a power failure, the block will contain a mix of old
and new data. Applications may not be prepared to handle such a scenario.

The Block Translation Table (BTT) provides atomic sector update semantics for
persistent memory devices, so that applications that rely on sector writes not
being torn can continue to do so. The BTT manifests itself as a stacked block
device, and reserves a portion of the underlying storage for its metadata. At
the heart of it, is an indirection table that re-maps all the blocks on the
volume. It can be thought of as an extremely simple file system that only
provides atomic sector updates.

Arena와 정적 저장 배치

BTT를 배치할 수 있는 하위 저장 장치 자체에는 별도 제한이 없습니다. 다만 BTT는 사용 가능한 공간을 최대 512 GiB 크기의 청크인 Arena로 나눕니다.

모든 Arena는 같은 메타데이터 배치를 따르며, 다음 Arena를 가리키는 한 필드를 제외하면 Arena 안의 모든 참조는 그 Arena 내부에서 끝납니다.

Backing Store에는 Arena 0, Arena 1과 이후 Arena가 연속해 놓입니다. 각 Arena 내부에는 선두의 4K Arena info block, 실제 Data Blocks, BTT Map, BTT Flog, 그리고 끝의 4K info block 복사본이 차례로 배치됩니다.

2. Static Layout
================

The underlying storage on which a BTT can be laid out is not limited in any way.
The BTT, however, splits the available space into chunks of up to 512 GiB,
called "Arenas".

Each arena follows the same layout for its metadata, and all references in an
arena are internal to it (with the exception of one field that points to the
next arena). The following depicts the "On-disk" metadata layout::


    Backing Store     +------->  Arena
  +---------------+   |   +------------------+
  |               |   |   | Arena info block |
  |    Arena 0    +---+   |       4K         |
  |     512G      |       +------------------+
  |               |       |                  |
  +---------------+       |                  |
  |               |       |                  |
  |    Arena 1    |       |   Data Blocks    |
  |     512G      |       |                  |
  |               |       |                  |
  +---------------+       |                  |
  |       .       |       |                  |
  |       .       |       |                  |
  |       .       |       |                  |
  |               |       |                  |
  |               |       |                  |
  +---------------+       +------------------+
                          |                  |
                          |     BTT Map      |
                          |                  |
                          |                  |
                          +------------------+
                          |                  |
                          |     BTT Flog     |
                          |                  |
                          +------------------+
                          | Info block copy  |
                          |       4K         |
                          +------------------+

BTT Map과 주소 용어

BTT Map은 외부 LBA를 내부 블록으로 연결하는 단순 lookup/indirection table입니다. 각 map entry는 32비트이며, 최상위 2비트는 Error와 Zero 플래그이고 나머지 30비트는 내부 postmap block 번호입니다.

플래그가 `00`이면 초기 상태로 읽기는 0을 반환하고 Premap과 Postmap이 같습니다. `01`은 Zero 상태로 읽기가 0을 반환합니다. `10`은 Error 상태로 읽기가 실패하며 쓰기가 `E` 비트를 지웁니다. `11`은 유효한 postmap을 가진 정상 블록입니다.

External LBA는 상위 계층에 보이는 LBA입니다. ABA는 Arena Block Address, 즉 Arena 안의 블록 오프셋 또는 번호입니다. Premap ABA는 External LBA 범위를 검사해 정한 Arena 내부 오프셋이고, Postmap ABA는 map 간접 참조 뒤 Data Blocks 영역에서 얻은 블록 번호입니다.

`nfree`는 어느 시점이든 유지하는 free block 수이며, 동시에 해당 Arena에 실행할 수 있는 쓰기 수이기도 합니다.

예를 들어 BTT가 1,024G 디스크를 노출하고 768G의 External LBA를 읽으면 두 번째 512G Arena 안의 256G 지점이므로 Premap ABA는 256G입니다. map에서 이 블록 X가 블록 Y, 예를 들어 64를 가리키면 Postmap ABA는 64입니다.

3. Theory of Operation
======================


a. The BTT Map
--------------

The map is a simple lookup/indirection table that maps an LBA to an internal
block. Each map entry is 32 bits. The two most significant bits are special
flags, and the remaining form the internal block number.

======== =============================================================
Bit      Description
======== =============================================================
31 - 30         Error and Zero flags - Used in the following way::

           == ==  ====================================================
           31 30  Description
           == ==  ====================================================
           0  0          Initial state. Reads return zeroes; Premap = Postmap
           0  1          Zero state: Reads return zeroes
           1  0          Error state: Reads fail; Writes clear 'E' bit
           1  1          Normal Block – has valid postmap
           == ==  ====================================================

29 - 0         Mappings to internal 'postmap' blocks
======== =============================================================


Some of the terminology that will be subsequently used:

============        ================================================================
External LBA        LBA as made visible to upper layers.
ABA                Arena Block Address - Block offset/number within an arena
Premap ABA        The block offset into an arena, which was decided upon by range
                checking the External LBA
Postmap ABA        The block number in the "Data Blocks" area obtained after
                indirection from the map
nfree                The number of free blocks that are maintained at any given time.
                This is the number of concurrent writes that can happen to the
                arena.
============        ================================================================


For example, after adding a BTT, we surface a disk of 1024G. We get a read for
the external LBA at 768G. This falls into the second arena, and of the 512G
worth of blocks that this arena contributes, this block is at 256G. Thus, the
premap ABA is 256G. We now refer to the map, and find out the mapping for block
'X' (256G) points to block 'Y', say '64'. Thus the postmap ABA is 64.

BTT Flog와 allocating write

BTT는 모든 쓰기를 free block에 수행하는 allocating write로 만들어 섹터 원자성을 제공합니다. Free block의 실행 목록은 BTT flog로 관리하며, `flog`라는 이름은 free list와 log를 합친 것입니다.

Flog에는 `nfree`개의 entry가 있습니다. `lba`는 쓰는 Premap ABA, `old_map`은 쓰기가 끝나면 free가 될 기존 Postmap ABA, `new_map`은 map에 반영할 새 Postmap ABA입니다. 복구가 필요할 때를 위해 새 `lba -> postmap_aba` 관계를 flog에도 남깁니다.

`seq`는 flog entry의 두 section 중 어느 쪽이 최신이고 유효한지 표시합니다. 정상 동작 중 이진수 `01 -> 10 -> 11 -> 01`로 순환하며 `00`은 초기화되지 않은 상태입니다. 프라임이 붙은 `lba'`, `old_map'`, `new_map'`, `seq'`는 대체 section입니다.

모든 필드는 32비트이므로 한 entry의 실제 필드 크기는 32바이트이며, 캐시 라인 공유나 aliasing을 피하려고 64바이트로 padding합니다. 갱신할 때 sequence number로 오래된 section을 골라 덮어쓰고, 새 section에서는 sequence number를 마지막에 기록합니다.

b. The BTT Flog
---------------

The BTT provides sector atomicity by making every write an "allocating write",
i.e. Every write goes to a "free" block. A running list of free blocks is
maintained in the form of the BTT flog. 'Flog' is a combination of the words
"free list" and "log". The flog contains 'nfree' entries, and an entry contains:

========  =====================================================================
lba       The premap ABA that is being written to
old_map   The old postmap ABA - after 'this' write completes, this will be a
          free block.
new_map   The new postmap ABA. The map will up updated to reflect this
          lba->postmap_aba mapping, but we log it here in case we have to
          recover.
seq          Sequence number to mark which of the 2 sections of this flog entry is
          valid/newest. It cycles between 01->10->11->01 (binary) under normal
          operation, with 00 indicating an uninitialized state.
lba'          alternate lba entry
old_map'  alternate old postmap entry
new_map'  alternate new postmap entry
seq'          alternate sequence number.
========  =====================================================================

Each of the above fields is 32-bit, making one entry 32 bytes. Entries are also
padded to 64 bytes to avoid cache line sharing or aliasing. Flog updates are
done such that for any entry being written, it:
a. overwrites the 'old' section in the entry based on sequence numbers
b. writes the 'new' section such that the sequence number is written last.

Lane과 Read Tracking Table

`nfree`가 한 Arena에서 동시에 처리할 수 있는 I/O 수라면, `nlanes`는 BTT 장치 전체가 동시에 처리할 수 있는 I/O 수입니다. 값은 `min(nfree, num_cpus)`입니다.

모든 I/O는 시작할 때 lane 번호를 얻고, I/O가 끝날 때까지 온디스크와 메모리 내 자료 구조를 색인하는 데 그 번호를 사용합니다. CPU 수가 사용 가능한 최대 lane 수보다 많으면 spinlock으로 lane을 보호합니다.

RTT가 없으면 느린 reader가 map에서 얻은 기존 Postmap block을 읽는 동안 writer가 같은 External LBA에 새 쓰기를 완료해 map을 새 Postmap ABA로 바꿀 수 있습니다. 그러면 reader가 아직 읽는 이전 블록이 free list에 들어가고, 같은 LBA의 다음 writer가 그 블록을 골라 덮어써 reader가 잘못된 데이터를 읽게 됩니다.

이를 막는 Read Tracking Table, RTT는 Arena마다 `nfree`개의 entry를 둡니다. Reader는 읽는 Postmap ABA를 `rtt[lane_number]`에 넣고 읽기가 끝나면 지웁니다. Writer는 free block을 얻은 뒤 RTT에 그 블록이 있는지 확인하고, 있다면 reader가 entry를 지울 때까지 기다린 뒤 쓰기를 시작합니다.

c. The concept of lanes
-----------------------

While 'nfree' describes the number of concurrent IOs an arena can process
concurrently, 'nlanes' is the number of IOs the BTT device as a whole can
process::

        nlanes = min(nfree, num_cpus)

A lane number is obtained at the start of any IO, and is used for indexing into
all the on-disk and in-memory data structures for the duration of the IO. If
there are more CPUs than the max number of available lanes, than lanes are
protected by spinlocks.


d. In-memory data structure: Read Tracking Table (RTT)
------------------------------------------------------

Consider a case where we have two threads, one doing reads and the other,
writes. We can hit a condition where the writer thread grabs a free block to do
a new IO, but the (slow) reader thread is still reading from it. In other words,
the reader consulted a map entry, and started reading the corresponding block. A
writer started writing to the same external LBA, and finished the write updating
the map for that external LBA to point to its new postmap ABA. At this point the
internal, postmap block that the reader is (still) reading has been inserted
into the list of free blocks. If another write comes in for the same LBA, it can
grab this free block, and start writing to it, causing the reader to read
incorrect data. To prevent this, we introduce the RTT.

The RTT is a simple, per arena table with 'nfree' entries. Every reader inserts
into rtt[lane_number], the postmap ABA it is reading, and clears it after the
read is complete. Every writer thread, after grabbing a free block, checks the
RTT for its presence. If the postmap free block is in the RTT, it waits till the
reader clears the RTT entry, and only then starts writing to it.

Map lock과 Flog 복구

두 writer가 같은 LBA에 동시에 쓰면 `free[lane] = map[premap_aba]`와 `map[premap_aba] = postmap_aba` 사이에 경합이 생길 수 있습니다. 두 thread가 각자의 `free[lane]`에 같은 이전 Postmap ABA를 넣으면 free entry 하나는 사라지고 다른 하나는 두 lane에 중복되어 배치가 일관성을 잃습니다.

Arena마다 map lock 하나를 두면 이 순서를 보호할 수 있지만 경합이 지나치게 클 수 있습니다. BTT는 대신 `nfree`개의 `map_locks` 배열을 만들고 `premap_aba modulo nfree`로 색인합니다.

시작할 때 BTT flog를 분석해 free block 목록을 다시 만듭니다. 각 lane에서 가능한 두 section 중 sequence number가 나타내는 가장 최신 section만 봅니다.

복구 규칙은 단순합니다. `map[log_entry.lba]`를 읽고 `log_entry.new`가 map entry와 같으면 `log_entry.old`가 free입니다. 다르면 `log_entry.new`가 free입니다. 두 번째 경우는 전원 장애나 안전하지 않은 종료 때문에만 생길 수 있습니다.

e. In-memory data structure: map locks
--------------------------------------

Consider a case where two writer threads are writing to the same LBA. There can
be a race in the following sequence of steps::

        free[lane] = map[premap_aba]
        map[premap_aba] = postmap_aba

Both threads can update their respective free[lane] with the same old, freed
postmap_aba. This has made the layout inconsistent by losing a free entry, and
at the same time, duplicating another free entry for two lanes.

To solve this, we could have a single map lock (per arena) that has to be taken
before performing the above sequence, but we feel that could be too contentious.
Instead we use an array of (nfree) map_locks that is indexed by
(premap_aba modulo nfree).


f. Reconstruction from the Flog
-------------------------------

On startup, we analyze the BTT flog to create our list of free blocks. We walk
through all the entries, and for each lane, of the set of two possible
'sections', we always look at the most recent one only (based on the sequence
number). The reconstruction rules/steps are simple:

- Read map[log_entry.lba].
- If log_entry.new matches the map entry, then log_entry.old is free.
- If log_entry.new does not match the map entry, then log_entry.new is free.
  (This case can only be caused by power-fails/unsafe shutdowns)

Read와 Write 절차

읽기는 External LBA를 Arena 번호와 Premap ABA로 변환하고 lane과 lane lock을 얻는 것으로 시작합니다. Map entry를 읽어 Postmap ABA를 얻고 이를 `RTT[lane]`에 넣습니다.

Map의 TRIM 플래그가 설정되어 있으면 0을 반환하고, ERROR 플래그가 있으면 `EIO`로 끝냅니다. 그렇지 않으면 해당 블록의 데이터를 읽습니다. 마지막에는 `RTT[lane]`에서 Postmap ABA를 지우고 lane과 lock을 반환합니다.

쓰기도 External LBA를 Arena와 Premap ABA로 변환하고 lane을 얻습니다. Lane으로 메모리 내 free list를 색인해 새 블록, 다음 flog index, 다음 sequence number를 구합니다.

선택한 free block이 RTT에 있는지 검사해 있으면 기다리고, 비워지면 그 블록에 데이터를 씁니다. Map에서 기존 Postmap ABA를 읽고 `[premap_aba / old postmap_aba / new postmap_aba / seq_num]` flog entry를 기록합니다.

그 뒤 새 Postmap ABA를 map에 기록하고, 이전 Postmap entry를 free list에 넣습니다. 다음 sequence number를 계산해 free-list entry에 기록한 뒤 lane과 lane lock을 반환합니다.

g. Summarizing - Read and Write flows
-------------------------------------

Read:

1.  Convert external LBA to arena number + pre-map ABA
2.  Get a lane (and take lane_lock)
3.  Read map to get the entry for this pre-map ABA
4.  Enter post-map ABA into RTT[lane]
5.  If TRIM flag set in map, return zeroes, and end IO (go to step 8)
6.  If ERROR flag set in map, end IO with EIO (go to step 8)
7.  Read data from this block
8.  Remove post-map ABA entry from RTT[lane]
9.  Release lane (and lane_lock)

Write:

1.  Convert external LBA to Arena number + pre-map ABA
2.  Get a lane (and take lane_lock)
3.  Use lane to index into in-memory free list and obtain a new block, next flog
    index, next sequence number
4.  Scan the RTT to check if free block is present, and spin/wait if it is.
5.  Write data to this free block
6.  Read map to get the existing post-map ABA entry for this pre-map ABA
7.  Write flog entry: [premap_aba / old postmap_aba / new postmap_aba / seq_num]
8.  Write new post-map ABA into map.
9.  Write old post-map entry into the free list
10. Calculate next sequence number and write into the free list entry
11. Release lane (and lane_lock)

Arena 오류 판정과 read-only 전환

버그나 미디어 오류로 메타데이터가 복구 불가능하게 손상되면 Arena는 오류 상태가 됩니다.

오류 조건에는 info block checksum 불일치와 복사본을 통한 복구 실패, map된 블록과 BTT flog에서 얻은 free block의 합이 모든 내부 가용 블록을 유일하고 완전하게 가리키지 못하는 경우가 포함됩니다.

또한 flog로 free list를 재구성할 때 누락·중복·불가능한 entry가 나오거나 map entry가 범위를 벗어나면 오류입니다.

이 조건 중 하나라도 발견하면 info block의 플래그를 사용해 해당 Arena를 read-only 상태로 전환합니다.

4. Error Handling
=================

An arena would be in an error state if any of the metadata is corrupted
irrecoverably, either due to a bug or a media error. The following conditions
indicate an error:

- Info block checksum does not match (and recovering from the copy also fails)
- All internal available blocks are not uniquely and entirely addressed by the
  sum of mapped blocks and free blocks (from the BTT flog).
- Rebuilding free list from the flog reveals missing/duplicate/impossible
  entries
- A map entry is out of bounds

If any of these error conditions are encountered, the arena is put into a read
only state using a flag in the info block.

ndctl로 BTT namespace 생성

BTT는 libnvdimm subsystem이 노출하는 어떤 디스크 namespace에도 설정할 수 있으며, `pmem` 모드와 `blk` 모드를 모두 지원합니다.

가장 쉬운 설정 방법은 `ndctl` 유틸리티를 사용하는 것입니다. 예제 명령은 `namespace0.0`에 4K sector size의 BTT namespace를 강제로 생성하며 mode를 `sector`로 지정합니다.

추가 선택지는 `ndctl create-namespace --help`에서 확인할 수 있고, 문서는 pmem의 `ndctl` GitHub 저장소를 참조합니다.

5. Usage
========

The BTT can be set up on any disk (namespace) exposed by the libnvdimm subsystem
(pmem, or blk mode). The easiest way to set up such a namespace is using the
'ndctl' utility [1]:

For example, the ndctl command line to setup a btt with a 4k sector size is::

    ndctl create-namespace -f -e namespace0.0 -m sector -l 4k

See ndctl create-namespace --help for more options.

[1]: https://github.com/pmem/ndctl