Persistent data | Linux 6.18.37

요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.

1. 요약·해설

원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.

재사용 가능한 metadata framework

persistent-data.rst:1-30

여러 target의 중복 metadata 구현을 공통 persistent-data library로 통합합니다.

Block과 transaction 계층

persistent-data.rst:31-54

고정 크기 block access, locking, copy-on-write와 commit durability를 제공합니다.

Space map과 B-tree

persistent-data.rst:55-88

Reference-count allocator와 여러 64-bit key를 지원하는 중첩 B-tree를 설명합니다.

2. 영어 원문 전체

번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.

원문 전체 펼치기

1 ===============

2 Persistent data

3 ===============

5 Introduction

6 ============

8 The more-sophisticated device-mapper targets require complex metadata

9 that is managed in kernel. In late 2010 we were seeing that various

10 different targets were rolling their own data structures, for example:

12 - Mikulas Patocka's multisnap implementation

13 - Heinz Mauelshagen's thin provisioning target

14 - Another btree-based caching target posted to dm-devel

15 - Another multi-snapshot target based on a design of Daniel Phillips

17 Maintaining these data structures takes a lot of work, so if possible

18 we'd like to reduce the number.

20 The persistent-data library is an attempt to provide a re-usable

21 framework for people who want to store metadata in device-mapper

22 targets. It's currently used by the thin-provisioning target and an

23 upcoming hierarchical storage target.

25 Overview

26 ========

28 The main documentation is in the header files which can all be found

29 under drivers/md/persistent-data.

31 The block manager

32 -----------------

34 dm-block-manager.[hc]

36 This provides access to the data on disk in fixed sized-blocks. There

37 is a read/write locking interface to prevent concurrent accesses, and

38 keep data that is being used in the cache.

40 Clients of persistent-data are unlikely to use this directly.

42 The transaction manager

43 -----------------------

45 dm-transaction-manager.[hc]

47 This restricts access to blocks and enforces copy-on-write semantics.

48 The only way you can get hold of a writable block through the

49 transaction manager is by shadowing an existing block (ie. doing

50 copy-on-write) or allocating a fresh one. Shadowing is elided within

51 the same transaction so performance is reasonable. The commit method

52 ensures that all data is flushed before it writes the superblock.

53 On power failure your metadata will be as it was when last committed.

55 The Space Maps

56 --------------

58 dm-space-map.h

59 dm-space-map-metadata.[hc]

60 dm-space-map-disk.[hc]

62 On-disk data structures that keep track of reference counts of blocks.

63 Also acts as the allocator of new blocks. Currently two

64 implementations: a simpler one for managing blocks on a different

65 device (eg. thinly-provisioned data blocks); and one for managing

66 the metadata space. The latter is complicated by the need to store

67 its own data within the space it's managing.

69 The data structures

70 -------------------

72 dm-btree.[hc]

73 dm-btree-remove.c

74 dm-btree-spine.c

75 dm-btree-internal.h

77 Currently there is only one data structure, a hierarchical btree.

78 There are plans to add more. For example, something with an

79 array-like interface would see a lot of use.

81 The btree is 'hierarchical' in that you can define it to be composed

82 of nested btrees, and take multiple keys. For example, the

83 thin-provisioning target uses a btree with two levels of nesting.

84 The first maps a device id to a mapping tree, and that in turn maps a

85 virtual block to a physical block.

87 Values stored in the btrees can have arbitrary size. Keys are always

88 64bits, although nesting allows you to use multiple keys.

3. 한국어 전문 번역

영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.

Device Mapper metadata framework의 배경

1-23

정교한 Device Mapper target은 kernel 안에서 관리하는 복잡한 metadata가 필요합니다. 2010년 말에는 서로 다른 target이 각자 data structure를 구현하는 상황이 반복되고 있었습니다.

Mikulas Patocka의 multisnap 구현
Heinz Mauelshagen의 thin provisioning target
`dm-devel`에 게시된 또 다른 B-tree 기반 caching target
Daniel Phillips의 설계를 바탕으로 한 또 다른 multi-snapshot target

중복 구현 사례

구현Metadata 용도

Mikulas Patocka multisnap여러 snapshot

Heinz Mauelshagen thin provisioningThin allocation

B-tree caching targetCache mapping

Daniel Phillips 기반 targetMulti-snapshot

여러 target이 비슷한 persistent metadata 문제를 독립적으로 풀고 있었습니다.

이러한 data structure를 유지하는 데 많은 작업이 필요하므로 가능한 한 구현 수를 줄이고자 했습니다.

`persistent-data` library는 Device Mapper target에서 metadata를 저장하려는 개발자가 재사용할 수 있는 framework를 제공하려는 시도입니다. 현재 thin-provisioning target과 앞으로 제공될 hierarchical storage target이 사용합니다.

공용 persistent-data 계층

Thin provisioning·hierarchical storage target`persistent-data` library공용 on-disk metadata

Target마다 metadata engine을 다시 만드는 대신 공통 block·transaction·allocation·index 계층을 사용합니다.

고정 크기 block 접근과 cache

24-40

주요 문서는 다음 header file directory에서 찾을 수 있습니다.

under drivers/md/persistent-data.

Block manager 구현 파일은 다음과 같습니다.

dm-block-manager.[hc]

Block manager는 disk data를 고정 크기 block 단위로 접근하게 합니다. Concurrent access를 막는 read/write locking interface를 제공하고, 사용 중인 data는 cache에 유지합니다. `persistent-data` client가 이 계층을 직접 사용할 가능성은 낮습니다.

Block manager 책임

기능역할

Fixed-size block accessDisk data를 일정한 block 단위로 읽고 씀

Read/write locking같은 block의 concurrent access 방지

Cache retention사용 중인 data를 memory에 유지

Client visibility일반 client는 대개 직접 호출하지 않음

상위 metadata 계층에 안전하고 cache 가능한 block I/O primitive를 제공합니다.

Copy-on-write transaction과 crash consistency

41-54

Transaction manager 구현 파일은 다음과 같습니다.

dm-transaction-manager.[hc]

Transaction manager는 block 접근을 제한하고 copy-on-write semantics를 강제합니다. Writable block을 얻는 방법은 기존 block을 shadow하여 copy-on-write를 수행하거나 새 block을 할당하는 것뿐입니다.

같은 transaction 안에서는 중복 shadowing을 생략하므로 성능을 합리적인 수준으로 유지합니다. Commit method는 superblock을 쓰기 전에 모든 data가 flush됐음을 보장합니다. 전원이 끊기면 metadata는 마지막으로 commit한 시점의 상태로 남습니다.

Transaction commit ordering

기존 block shadow 또는 새 block 할당Copy-on-write metadata 수정모든 data flushSuperblock writeCommit 완료

중간 power failure마지막 commit의 superblock 유지이전 metadata 상태 복구

새 metadata tree를 완성하고 durable하게 만든 뒤 마지막에 superblock이 새 상태를 가리키게 합니다.

Reference count와 block allocation

55-68

Space map 관련 구현 파일은 다음과 같습니다.

dm-space-map.h
dm-space-map-metadata.[hc]
dm-space-map-disk.[hc]

Space map은 block의 reference count를 추적하는 on-disk data structure이며 새 block allocator 역할도 합니다. 현재 구현은 두 가지입니다.

두 space-map 구현

구현관리 대상특징

`dm-space-map-disk.[hc]`다른 장치의 blockThin-provisioned data block 등에 쓰는 단순한 구현

`dm-space-map-metadata.[hc]`Metadata space관리 중인 공간 안에 자신의 data도 저장해야 함

관리 대상이 data device인지 metadata 자체 공간인지에 따라 구현 복잡도가 달라집니다.

첫 구현은 thinly-provisioned data block처럼 다른 장치의 block을 관리합니다. 두 번째 구현은 metadata space를 관리하며, 자신의 data structure를 자신이 관리하는 바로 그 공간에 저장해야 하므로 더 복잡합니다.

Space map 역할

Block reference 변경On-disk reference count 갱신Free/used 상태 결정새 block allocation

Reference count와 free-space allocation을 하나의 persistent 계층에서 관리합니다.

여러 key를 지원하는 계층형 B-tree

69-88

현재 data structure 구현 파일은 다음과 같습니다.

dm-btree.[hc]
dm-btree-remove.c
dm-btree-spine.c
dm-btree-internal.h

현재 제공되는 data structure는 hierarchical B-tree 하나뿐이며, 앞으로 array와 비슷한 interface처럼 활용도가 높은 구조를 더 추가할 계획입니다.

이 B-tree는 B-tree를 중첩해 여러 key를 받을 수 있다는 의미에서 'hierarchical'합니다. Thin-provisioning target은 두 단계로 중첩된 B-tree를 사용합니다. 첫 단계는 device id를 mapping tree로 mapping하고, 그 tree가 다시 virtual block을 physical block으로 mapping합니다.

Thin-provisioning의 2단계 B-tree

Key 1: device idDevice mapping treeKey 2: virtual blockPhysical block

첫 key가 device별 mapping tree를 고르고 두 번째 key가 실제 data block 위치를 찾습니다.

B-tree에 저장하는 value 크기는 임의로 정할 수 있습니다. Key는 항상 64-bit이지만, tree nesting을 통해 여러 key를 사용할 수 있습니다.

Hierarchical B-tree 특성

항목제약 또는 기능

Key항상 64-bit

Value임의 크기

복합 keyNested B-tree로 여러 key 사용

현재 구현Hierarchical B-tree

고정 크기 key와 가변 크기 value를 중첩 tree로 조합합니다.