17. Persistence - File Systems Basics

File System Layers

시험용으로 text path를 외우면 다음과 같다.

User-level software
Library
POSIX API: open, read, write, ...
File System: Ext4, ...
Generic Block Layer
Generic Block Interface: blk_read, blk_write
Device Driver: SCSI, SATA
Specific Block Interface
Disk interrupt handler
Hardware

Storage: Logical View

• 저장 장치는 OS에게 보통 block interface로 보인다.
• disk는 byte 단위가 아니라 고정 크기 block 또는 sector의 배열처럼 추상화된다.

block 0 | block 1 | block 2 | ... | block N-1

• 주요 operation은 다음과 같다.
  • Identify(): returns N
    • 저장 장치가 총 몇 개의 block을 가지는지 알려준다.
  • Read(start sector #, # of sectors)
    • 특정 sector부터 여러 sector를 읽는다.
  • Write(start sector #, # of sectors)
    • 특정 sector부터 여러 sector에 쓴다.

File

• persistent storage에 기록되는 관련 정보의 이름 붙은 집합
• 파일은 사용자 입장에서는 이름과 내용으로 보인다.
• 하지만 내부적으로는 각 파일마다 inode number가 있다.
  • inode number는 file system 내부에서 파일을 식별하는 ID다.
  • 같은 file system 안에서 inode number는 특정 시점에 unique하다.

Directory

• Directory는 파일들을 구조적으로 정리하기 위한 특수한 파일이다.
• 핵심 역할은 다음과 같다.

file name -> inode number

• directory는 <file name, inode number> 쌍의 목록이다.
• hierarchical directory tree: 다른 디렉토리 안에 놓일 수 있다

File System Basics: Data, Metadata, Name

1. File contents(daga)
   • 파일의 실제 내용. byte sequence로 저장됨.
2. File attributes(metadata / inode)
   • 파일 자체에 대한 정보.
     • file size
     • owner
     • access control
     • timestamps
     • data block locations
   • 이 metadata가 inode에 들어간다.
3. File name
   • 사용자가 보는 이름. full pathname이 파일을 지정한다.
   • 예:open("/etc/passwd", O_RDONLY);

File System as a Mapping Problem

• 파일 시스템은 본질적으로 mapping 문제다.

<filename, data, metadata> -> <a set of disk blocks>

• 사용자는 다음처럼 생각한다.

"dog.jpg"라는 파일을 열고 싶다.

• file system 내부에서는 다음 문제가 된다.

1. dog.jpg라는 이름은 어느 directory entry에 있는가?
2. 그 이름이 가리키는 inode number는 무엇인가?
3. 그 inode는 어디에 저장되어 있는가?
4. 그 inode가 가리키는 data block들은 어디인가?
5. 그 block들을 어떤 순서로 읽어야 하는가?

File System Design Issues

• 파일 시스템이 설계해야 하는 문제는 꽤 많다.

1. Metadata에는 무엇을 저장할 것인가
   • 파일 크기, 권한, owner, timestamp, block pointer 등을 저장해야 함.
2. Pathname에서 metadata를 어떻게 찾을 것인가
   • 예를 들어 /a/b/c가 들어오면 /부터 시작해서 a, b, c를 차례로 찾아야 함.
3. Metadata와 offset에서 data block을 어떻게 찾을 것인가
   • 예를 들어 파일의 8192번째 byte를 읽으려면, 그 byte가 어느 disk block에 있는지 계산해야 함.
4. Metadata와 data block을 어떻게 관리할 것인가
   • 새 파일을 만들 때 inode를 할당해야 함.
   • 파일이 커지면 data block을 추가로 할당해야 함.
   • 파일을 지우면 inode와 block을 회수해야 함.
5. Crash 이후 어떻게 복구할 것인가
   • 파일 시스템은 여러 block을 순서대로 update함.
   • 중간에 전원이 꺼지면 metadata와 data가 서로 안 맞을 수 있음.

POSIX Inode

• POSIX inode는 파일의 metadata를 담음.
• 대표적인 정보는 다음과 같다.

1. File type
   • regular file
   • directory
   • character device
   • block device
   • FIFO
   • symbolic link 등
2. Device ID
   • 이 파일이 어느 device 또는 file system에 있는지 나타낸다.
3. Inode number
   • file system 내부의 파일 ID다.
4. Access permission
   • owner, group, others에 대한 rwx 권한이다.

r: read
w: write
x: execute

5. Number of hard links
   • 이 inode를 가리키는 directory entry의 개수다.
6. User ID / Group ID
   • 파일 소유자와 그룹 정보다.
7. File size
   • byte 단위의 파일 크기다.
8. Number of allocated blocks
   • 이 파일이 실제로 차지하는 block 수다.
9. Timestamps
   • atime: last access time
   • mtime: last modification time
   • ctime: last status change time

File Operations

• POSIX file system은 여러 system call을 제공한다.

int open(char *pathname, int flags, mode_t mode); // pathname을 file descriptor로 바꾼다.
int creat(char *pathname, mode_t mode); // 새 파일을 생성한다.
ssize_t read(int fd, void *buf, size_t count); // file descriptor에서 데이터를 읽는다.
ssize_t write(int fd, void *buf, size_t count); // file descriptor에 데이터를 쓴다.
off_t lseek(int fd, off_t offset, int whence); // 열린 파일의 현재 offset을 이동한다.
int close(int fd); // file descriptor를 닫는다.
int fsync(int fd); // dirty data를 disk에 강제로 flush한다.
int rename(char *oldpath, char *newpath); // oldpath 이름을 newpath로 변경한다.
int unlink(char *pathname); // 파일 이름을 directory에서 제거한다.
int stat(char *path, struct stat *buf); // 파일의 metadata를 stat 구조체에 채운다.
int link(char *oldpath, char *newpath); // 같은 inode를 가리키는 hard link를 만든다.
int symlink(char *oldpath, char *newpath); // pathname을 가리키는 symbolic link를 만든다.
int mount(char *source, char *target, char *fstype,
          unsigned long mountflags, void *data); // file system을 directory tree에 붙인다.
int umount(char *target); // mount된 file system을 directory tree에서 분리한다.

File Descriptor

• user process가 파일을 직접 inode나 disk block으로 다루지 않고, 대신 작은 정수인 file descriptor를 사용함.

fd 0: stdin
fd 1: stdout
fd 2: stderr

• 예를 들어:

int fd = open("a.txt", O_RDONLY); //fd: process가 열린 파일을 가리키기 위해 사용하는 handle
read(fd, buf, 100);
close(fd);

Unix Kernel의 Open File 표현

• Unix 계열 OS는 열린 파일을 여러 단계의 table로 표현한다.

Descriptor table      Open file table       v-node table
[per process]   ->    [shared system-wide] -> [shared system-wide]

1. Descriptor table
   • process마다 하나씩 있다.
   • fd 번호를 open file table entry에 연결한다.
   • 예: fd 4 -> open file entry
2. Open file table
   • system 전체에서 공유된다.
   • 열린 파일 객체를 나타낸다.
   • 파일의 현재 offset, reference count, access mode 등을 가진다.
3. v-node table
   • 실제 file object, 즉 파일의 metadata 쪽을 나타낸다.
   • file type, file size, access 정보 등을 가진다.
   • Unix 구현에 따라 vnode/inode 등으로 표현된다.

File Position

• 열린 파일은 file position, 즉 현재 offset을 가진다.
• read()나 write()를 하면 이 offset이 이동한다.
• 예를 들어:

read(fd, buf, 10);
read(fd, buf, 10);

• 첫 번째 read()는 offset 0부터 10 byte를 읽고, offset을 10으로 옮긴다.
• 두 번째 read()는 offset 10부터 다시 10 byte를 읽는다.
• 이 offset은 inode 자체에 있는 것이 아니라 open file table entry에 있다.
• 그래서 같은 파일을 두 번 open()하면 서로 다른 file position을 가질 수 있다.

File Sharing: open twice

• 같은 파일을 두 번 open()하면 어떻게 될까?

int fd1 = open("a.txt", O_RDONLY);
int fd2 = open("a.txt", O_RDONLY);

• 이 경우 fd1, fd2는 같은 disk file을 가리키지만, 보통 open file table entry는 서로 다르다.
• 따라서 file position도 따로 가진다.

fd1 -> open file entry 1 -> same vnode/inode
fd2 -> open file entry 2 -> same vnode/inode

• 그래서 fd1으로 읽어서 offset이 변해도, fd2의 offset은 별도로 유지된다.

File Sharing: fork

• fork()를 하면 child process는 parent의 open files를 상속한다.
• 즉 child의 descriptor table은 parent와 같은 open file table entry들을 가리키게 된다.
• 이때 open file table entry의 reference count가 증가한다.
• 
• 
• 이 경우 parent와 child는 같은 open file table entry를 공유한다. 따라서 file position도 공유한다.
• 예를 들어 parent가 먼저 읽어서 offset을 이동시키면, child가 이어서 읽을 때 그 다음 위치에서 읽을 수 있다.
• 중요한 점:
  • fork()는 open files를 상속한다.
  • exec() 이후에도 open files는 기본적으로 유지된다.
  • 단, FD_CLOEXEC 같은 설정을 쓰면 exec 때 닫히게 할 수 있다.

Pathname Translation

• open("/a/b/c", ...)를 호출하면 file system은 pathname을 해석해야 한다.
• 과정은 다음과 같다.

open("/a/b/c", ...)

1. root directory /를 연다.
2. / directory에서 "a"라는 entry를 찾는다.
3. "a"의 inode를 얻고, directory a를 연다.
4. directory a에서 "b"라는 entry를 찾는다.
5. "b"의 inode를 얻고, directory b를 연다.
6. directory b에서 "c"라는 entry를 찾는다.
7. 최종적으로 file c를 연다.

• 각 단계마다 permission check가 필요하다.
• file system은 directory path를 따라 내려가는 데 많은 시간을 쓴다.
• 그래서 OS는 prefix lookup 결과를 cache할 수 있다.
  • 예를 들어 /a/b까지의 lookup 결과를 cache해 두면, /a/b/c, /a/b/d 접근이 빨라진다.

Ensuring Persistence

• write()를 호출했다고 해서 데이터가 즉시 disk에 쓰이는 것은 아님. file system은 성능을 위해 write를 memory에 buffering함. (page cache)
• write buffering의 장점:
  • 여러 작은 write를 모아서 처리할 수 있다.
  • disk I/O 횟수를 줄일 수 있다.
  • 성능이 좋아진다.
• 단점:
  • crash가 나면 아직 disk에 쓰이지 않은 데이터는 사라질 수 있다.
• Linux에서는 dirty data가 최대 수십 초 정도 memory에 남아 있을 수 있다고 설명한다.
• 따라서 정말 disk에 반영되었음을 보장하고 싶으면 fsync()를 호출한다.

int fd = open("foo", O_CREAT | O_WRONLY | O_TRUNC);
int rc = write(fd, buffer, size);
rc = fsync(fd);
close(fd);

• fsync(fd)는
  • dirty data를 disk로 flush하고
  • disk write cache도 media에 반영되도록 요청하고
  • 파일과 관련된 metadata도 flush한다.
• 반면 fdatasync()는 modified metadata까지는 flush하지 않는다.

write()     : 커널 page cache에 쓰고 나중에 disk 반영 가능
fsync()     : data + 관련 metadata까지 disk에 강제 반영
fdatasync() : data 중심으로 반영, modified metadata는 flush하지 않음

Hard Link

• Hard link는 같은 inode를 가리키는 또 다른 파일 이름이다.

ln old.txt new.txt

• 이 명령은 new.txt라는 새 이름을 만들지만, 실제로는 old.txt와 같은 inode를 가리킨다.

old.txt -> inode 10
new.txt -> inode 10

• 중요한 특징:
  • 두 pathname은 같은 inode number를 가진다.
  • 어느 쪽이 원래 이름인지 구분할 수 없다.
  • inode는 hard link 개수, 즉 link count를 유지한다.
  • unlink()로 이름 하나를 지우면 link count가 감소한다.
  • link count가 0이 되고, 더 이상 열린 file descriptor도 없으면 inode와 data block이 제거된다.
  • hard link는 file system boundary를 넘을 수 없다.
• 예시:

ln a.txt b.txt
rm a.txt

• 이 경우 a.txt 이름은 사라지지만, b.txt가 같은 inode를 계속 가리키므로 파일 내용은 남아 있다.

Symbolic Link

• Symbolic link, 또는 soft link는 다른 pathname을 내용으로 가지는 특수한 파일이다.

ln -s old.txt new.txt

• hard link와 달리 같은 inode를 직접 가리키는 것이 아니다.
• new.txt는 “old.txt를 참조하라”는 pathname을 담고 있다.

new.txt -> "old.txt"
old.txt -> inode 10

• Windows의 shortcut과 비슷하다고 볼 수 있다.
• 중요한 특징:
  • 다른 file system을 가리킬 수 있다.
  • directory도 가리킬 수 있다.
  • 원본이 삭제되면 dangling symlink가 될 수 있다.

Hard Link vs Symbolic Link

File System Mounting

• file system은 사용되기 전에 mount되어야 한다.
• Windows에서는 file system이 보통 drive letter로 나타난다.

C:\
D:\

• Unix에서는 file system을 기존 directory에 붙인다.
• 이 directory를 mount point라고 한다.

mount /dev/sdb1 /mnt/usb

• 이 경우 /dev/sdb1 file system이 /mnt/usb 아래에 붙는다.
• Unix의 특징은 여러 file system을 하나의 directory tree 안에 붙여서, 사용자에게는 하나의 큰 tree처럼 보이게 한다는 점이다.

/
├── home
├── usr
├── mnt
│   └── usb   <- 다른 file system mounted
└── var

• 즉 Unix에서는 disk마다 별도 drive letter를 쓰기보다, 하나의 global directory hierarchy에 file system들을 연결한다.

Consistency Semantics

• consistency semantics는 여러 process가 같은 file을 공유할 때, 한 process의 write가 다른 process에게 언제 보이는지를 정의한다.

Unix Semantics

• Unix semantics에서는 files can be shared among processes.
• 어떤 process가 open file에 write하면, 같은 파일을 열고 있는 다른 process에게 그 변경이 즉시 보인다.
• 예:

Process A: write(fd, "hello", 5)
Process B: read(fd2, ...)

• Process B는 A가 쓴 내용을 곧바로 볼 수 있다.
• 일반적인 Unix local file system의 직관과 가장 가깝다.

AFS Session Semantics

• AFS session semantics에서는 write가 즉시 보이지 않는다.
• 어떤 process가 파일을 열어 수정하더라도, 그 변경은 close 이후 나중 session에서 보인다.
• 즉 “open 중인 다른 사용자에게 바로 반영”보다는 “session이 끝난 후 반영”에 가깝다.
• 네트워크 파일 시스템에서 consistency 비용을 줄이기 위한 방식으로 이해하면 된다.

A가 파일을 열고 수정 중
B가 이미 같은 파일을 열고 있음
→ B에게 A의 수정이 즉시 보이지 않을 수 있음

A가 close
→ 이후 새로 여는 session에서 변경이 보임

Immutable Shared Files Semantics

• immutable shared files semantics에서는 한 번 shared로 선언된 파일은 수정할 수 없다.
• 즉 공유 파일은 읽기 전용처럼 취급된다.
• 이렇게 하면 consistency 문제가 단순해진다.
• 누가 쓰는지, 언제 보이는지 고민할 필요가 적다.
• 대신 파일을 수정해야 하는 workload에는 유연성이 떨어진다.

17단원에서 헷갈리기 쉬운 포인트

1. 파일 이름은 inode 안에 있는 게 아니다
   • 이름은 directory entry에 있다.
   • inode는 metadata와 data block 위치를 가진다.
2. 같은 파일을 두 번 open하면 offset이 따로일 수 있다
   • 같은 inode를 가리켜도 open file table entry가 다르면 file position이 다르다.
3. fork하면 open file entry를 공유한다
   • parent와 child가 같은 open file table entry를 가리킨다.
   • 그래서 file position도 공유될 수 있다.
4. write는 곧바로 disk write가 아니다
   • page cache에만 반영될 수 있다.
   • persistence가 필요하면 fsync()를 써야 한다.
5. hard link는 inode를 공유하고, symbolic link는 pathname을 저장한다
6. mount는 file system을 directory tree에 붙이는 것
   • Unix는 여러 file system을 하나의 큰 tree로 보이게 한다.