11. LFS - Log-structured Filesystem (서울대 고급 운영체제 강의록)

서울대학교 컴퓨터공학과 김진수 교수님의 "고급 운영체제" 강의를 필기한 내용입니다.

다소 잘못된 내용과 구어적 표현 이 포함되어 있을 수 있습니다.

LFS, A Log-structured Filesystem §

• 자세한 Background, problem statement 내용은 논문 리뷰 에서 확인하자
  • 간단하게 말하면 (1) small file write 가 너무 많아 FFS 의 cylinder group 을 사용해도 operation time 대부분이 seek time 로 도배되어 버리는 것과 (2) 이 small file 의 대부분인 metadata (directory, inode) 는 synchronous 하게 작동한다는 것이다.
  • LFS 가 핵심적으로 해결하려고 하는 문제는 write overhead 이다; read 는 memory size 가 커짐에 따라 이곳을 cache 로 사용하게 되며 오버헤드가 그리 크지 않다고 한다.
• 이 small file synchronous write overhead 를 줄이는 핵심 아이디어는 Log-structured sequential write 이다.
  • 뭔가를 “변경” 하기 위해 그곳을 찾아가는 seek time 이 오래걸리니까
  • 찾아가지 말고 그냥 sequential append 를 해버리자는 생각
  • 이래 하면 seek time 이 거의 “소멸” 되어버린다.
• 하지만 이 방식은 딱봐도 두가지의 문제가 있어보인다:
  • 그럼 변경 전 데이터와 후 데이터가 공존하게 되는데, 어떻게 효율적으로 변경 후 데이터를 읽어올까?
  • 변경 전 데이터가 점점 쌓일텐데, 어떻게 정리해불까?
• 이 두 문제를 해결하는 것이 이 LFS 의 challenge 이고 이것을 아래 나오는 방식으로 기가맥혀버리게 해결했다고 한다..

Inode, Inode map §

• 기존 FFS 에서 문제가 되던 small file synchronous write overhead 에의 저 “small file” 에는 inode 와 directory 가 큰 비중을 차지하기에 LFS 에서는 얘네들을 logging 해버린다.
  • 즉, 이제는 더이상 inode 가 FFS 처럼 고정된 위치에 박혀있는게 아니라 logging 되며 이리저리 움직인다는 것.
• 따라서 현재 inode 가 어디 있는지 알아낼 방법이 필요하고, 이것은 inode map 에 정리된다.
• 근데 심지어 이 inode map 도 logging 되고, inode map 이 어디에 있는지도 어딘가에 정리되어야 하는데 이것은 고정위치의 (드디어 고정위치!) checkpoint region 에 적힌다.
  • 지금 드는 생각은 inode map 까지 logging 했어야 됐나 싶긴 하다.
• 이 inode map 에는 각 inode 들의 version number 가 들어가고, inode 의 file 이 삭제되거나 data block 사이즈가 0이 되면 증가한다.
  • 이 “version number” 라는 놈은 뒤에서 나올 segment cleaning 에 사용된다.

Block R/W §

• 따라서 어떤 block 을 읽는 것은 다음처럼 된다.
  • Checkpoint region 에서 inode map 위치 찾기
  • Inode map 에서 원하는 inode 위치 찾기
  • Inode 에서 원하는 block 찾기
• 그리고 파일에 어떤 block 을 추가하는 것은 다음처럼 된다.
  • 추가된 block 을 logging
  • Block 이 추가됐으므로, inode 가 바뀌어야 하기에 새로운 inode 를 logging
  • Inode 의 위치가 바뀌었으므로, 새로운 inode map 을 logging
  • 이 새로운 inode map 의 위치를 checkpoint region 에 random write

Segment §

• Segment 는 다음의 특징을 가진 단위이다:
  • 디스크 전체는 이 고정크기의 공간인 segment 들로 분할된다.
  • Log 는 다수의 segment 로 구성된다.
  • 하나의 segment 는 invalid data 를 제거하는 작업인 cleaning 의 단위가 된다.
  • 하나의 segment 는 크기가 꽤 커서 (512K ~ 1M) 이 segment 를 write 하는 transfer time 이 seek time 를 상회한다.
    • 즉, seek time 은 상쇄된다.

Segment Summary Block §

• Segment 의 모든 block 들 각각에 대한 정보를 모아둔 공간이 segment 내에 있는데, 이것을 Segment Summary Block 이라 한다.
• Segment Summary Block 의 각 entry 는 다음과 같다.
  • 해당 block 이 속한 file 의 inode number
  • 해당 block 이 속한 file 의 inode version
  • 해당 block 이 속한 file 의 block number (즉, file 내에서의 offset)
• 그럼 도대체 이놈의 것을 왜하느냐… segment 내의 live block 을 식별하기 위해서이다.
  • 위에서 말한 대로, logging 을 하다 보면 invalid block 이 점점 쌓일 것이고 이것을 치우는 cleaning 이 필요한데
  • 이때 어떤 놈이 live (즉, valid) 한지 파악해야 하기 때문.
• 대강 다음과 같이 식별할 수 있다.
  • 어떤 block $b$ 가 live 한지 알아보고 싶다고 해보자.
  1. 그럼 $b$ 에 대한 SSB entry 를 꺼내서 inode number 와 block number 를 알아낸다.
  2. Inode map 과 inode number 를 이용해서 inode 를 알아내고
  3. Inode 와 block number 를 이용해 inode 가 이 $b$ 를 가리키고 있는지 확인한다.
  4. 당연히 가리키고 있으면 valid, 가리키고있지 않으면 invalid.
• 여기서 한가지 최적화가 들어간 것이 저 version number 이다.
  • 만일 (2) 번 과정에서 inode map 의 version number 를 확인했을 때 SSB entry 에 있던 version number 와 다르다면, 고민할 필요 없이 invalid 처리된다.
  • 이것은 inode 의 direct/indirect 를 돌아다니며 block 이 실제로 inode 에 의해 pointing 되고 있는지 확인하는 것보다 더 빠르게 수행할 수 있다는 장점이 있다.
  • 하지만 version number 는 자주 바뀌지 않기 때문에 그냥 뭐 아쉬운거지
    • 왜 근데 version number 가 file 이 삭제되는 등의 상황에서만 증가할까
    • 만약에 inode 가 변경될때마다 증가한다고 해보자.
    • 그럼 inode 에 속한 block 들 중에는 변경된 놈도 있을 것이고 변경되지 않은 놈도 있을 텐데
    • 변경된 놈은 SSB entry 에서 version 를 업데이트한다고 치더라도 변경되지 않은 놈에 대한 SSB entry 의 version number 를 다 업데이트해야하기 때문시
    • 뭐 이거 말도 안되죠? 그래서 inode 의 data block 들이 전부 invalid 되는 상황에서만 version number 를 증가시키는 거시다.
• SSB 는 segment 의 맨 처음에 logging 된다.
  • 이게 뭔 모순된 개소린가 싶을 수 있는데, segment 는 우선 메모리상에 축적되다가 다 차면 disk 로 쓰여진다는 점을 생각해 보면 알 수 있다.
  • 즉, segment 가 다 차야 disk 로 write 한다는 것이고, 이 이후에는 해당 segment 가 변경되지는 않아 SSB 도 변경되지 않고, 따라서 항상 disk-segment 의 맨 앞에 박혀있게 되는 것.

Segment cleaning policy… Write Cost and Cost-benefit model §

Write Cost §

• Segment cleaning policy 들의 performance 비교를 위한 metric 이다.
• 무언가를 write 힐 때, cleaning 이 없는 ideal 한 상황은 1 로 상수값이고,
• Cleaning 이 수반되어 추가적인 IO 가 발생하게 되면 그때부터는 달라진다.
  • Cleaning 에 필요한 overhead (즉, cleaning 에 필요한 read 와 write) 를 추가하여 값을 산정
• 자세한건 논문 리뷰 에서 확인하고, 몇가지만 적어보면
  • u 가 live block 이면, (1 - u) 가 dead block 이고 결과적으로 2 / (1 - u) 가 되는 것
  • 여기서 segment 를 전부 read 한다고 가정했는데
  • 실제로는 다 읽을 필요는 없고
  • 따라서 read 도 N * u 로 하기도 한다
• 그래프를 그려보면 이래된다.

• 위 그래프는 이렇게 이해하면 된다: segment utilization u 에 따라 clean-and-write 를 했을 때의 write cost 변화
  • 좀 더 러프하게 보면 u 에 따라 clean 했을 때의 write cost 인 셈이다.
• 위 그래프를 이렇게 이해해 보자:
  • LFS 와 FFS today 와 비교했을 때, u 가 0.8 일때 cleaning 을 시작하면 write cost 가 FFS today 와 비슷해지고, 0.8 보다 작을 때 시작하면 FFS today 보다 좋아지며, 0.8 보다 클때 시작하면 FFS today 보다 안좋아진다.
  • LFS 와 FFS improved 와 비교했을 때, u 가 0.5 일때 cleaning 을 시작하면 write cost 가 FFS improved 와 비슷해지고, 0.5 보다 작을 때 시작하면 FFS improved 보다 좋아지며, 0.5 보다 클때 시작하면 FFS improved 보다 안좋아진다.
  • FFS improved 와 FFS today 를 비쇼하면, FFS today 의 경우에는 u 를 더 높여도 여전히 LFS 가 더 좋고, FFS improved 는 u 를 낮춰야 LFS 가 더 놓아지기 때문에 LFS 에 더 많이 손해를 보게 해야 비슷한 성능이 나오는 FFS improved 가 FFS today 에 비해 더 좋은 것이라 이해할 수 있다.
• 여기까지는 이론적인 예측이었고, 실제로 실험을 진행했을 때 어떻게 되나 보자.

Greedy Policy §

#draft Record 15m

• Greedy Policy 는 live block 이 적은 놈을 victim 으로 골라 cleaning 하는 정책이다.
• 이때, 실험 결과는 아래와 같이 나온다:

• 일단 x 축이 Segment util 이 아니라 disk util 로 바뀌었다.
• 그래프가 오른쪽 아래로 깔릴수록 더 좋다 - util 을 올려도 write cost 가 잘 오르지 않는다는 것이므로
• No variance 는 disk util 과 동일한 양상으로 seg util 가 변화한다고 가정했을 때의 그래프이다.
  • 당연히 disk util 과 seg util 이 동일하니까 그래프로 위의 “이론적인 예측” 그래프와 동일하다.
• Uniform 는 random access 를 했을 때 이다.
  • 생각으로는 공평한 확률로 random access 하기 때문에 No variance 와 동일한 그래프가 나와야 할 것으로 보이지만 실제 결과는 보다시피 좀 다르다.
  • 이것은 실제로는 공평한 확률로 random access 를 해도 실제로는 disk util 과 seg util 간에는 차이가 있다는 것을 암시한다.
• Hot-and-cold: 데이터의 hotness 를 조절한 (즉, 균일하지 않은 확률로 access 를 한) 그래프이다.
  • Uniform 에 비해 실제 현실상황과 좀 더 유사한 실험이라고 할 수 있다.
  • Invalid 를 많이 모아두면 greedy 에 의해 victim 으로 선정되어 clean 될테니 free 를 더 많이 확보할 수 있어 좋지 않을까 생각했지만,
  • 그런데 이것은 틀렸습니다 - 보다시피 Uniform 이랑 별 다를바가 없다.

Greedy Policy 의 문제점 §

• 사실은 Greedy 를 적용하면 이런 일이 발생한다:
  • Hot invalid 는 빨리 생성되고 빨리 회수되는 반면
  • Cold invalid 잘 생성되지 않고 따라서 hot invalid 와의 victim 으로 선정경쟁에서 져 잘 회수도 안된다.
• 그런데 좀 생각해보면 hot invalid 보다 cold invalid 가 더 회수 우선순위가 높다는 것을 알 수 있다.
  • hot invalid 은 어차피 계속 생길것이기 때문에 양이 많아도 나중에 정리해도 되지만,
  • cold invalid 는 잘 안생기기 때문에 빨리 정리해 주는 것이 유리
• 그래서 cold segment 를 victim 으로 만들어서 여기에의 free 를 회수해야 하는 policy 를 고안할 필요가 있었다.
  • Cold invalid 는 util 은 다소 높더라도 cleaning 을 돌려 회수하고,
  • Hot invalid 는 util 이 낮아질때까지 기다렸다가 cleaning 을 돌려 회수하도록

Cost-benefit Policy §

• 생각해보자
  • 일단 더 많은 invalid 들이 회수되는 segment 일수록 우선순위가 높을테고 - Hot invalid 고려
  • Segment 내의 block 들의 나이가 많을 수록 더 우선순위가 높을테고 - Cold invalid 고려
  • Cost (full read + valid write) 는 적을수록 더 우선순위가 높을테다
• 그래서 이런 수식이 나오고

$$\frac{(1-u)\ast age}{1+u}$$

• 이런 그래프가 나온다.

• 즉, 이렇게 하니 hot 은 낮은 util 에서, cold 는 높은 util 에서 정리되어 결과적으로 아주 좋아졌다는 것,,,
  • 근데 util 이 80% 를 넘어가면 FFS improved 보다 더 안좋아지게 되는 문제가 아직까지도 있음
  • SSR - util 이 80% 가 넘으면 다른 곳의 dead block 에 그냥 overwrite 하자

Segment Usage Table §

• 이제 이 Cost-benefit policy 에 사용될 값들을 알아낼 방법이 필요해 졌고, 이에 따라 도입된 것이 Segment Usage Table 이다.
  • 우선 Segment 내의 live byte 의 개수를 저장해 $util$ 을 계산한다.
  • 그리고 last modified time 을 저장해 $age$ 를 계산한다.
• 이놈도 logging 되는 놈으로, 이놈의 위치는 Checkpoint 에 저장된다.

Checkpoint §

• Checkpoint 는 “완전한 Log 상태” 를 저장하는 곳이다.
  • 일단 메모리에 있던 modified data 를 전부 logging 하고
  • Inode map 과 summary usage table 의 block 들 주소를 checkpoint 에 적어놓는다.
• 그리고 이 “완전한 상태” 를 가지고 crash recovery 를 수행하게 되는 것.
• sync syscall 로 강제로 수행할 수도 있음
• segment 를 새로 쓸 때도 수행
  • 혹은 주기적으로
• checkpoint 할 때 error 가 날 수 있기 때문에 두개의 checkpoint region 을 사용

Roll Forward §

• Checkpoint 생성 이후에의 변경에 대해 복구하는 것을 일컫는다.
• Segment summary block 을 이용해 inode map 을 복구
  • 만약 SSB 에 inode 가 있는데 inode map 에는 없다? 그럼 해당 inode block 을 inode map 에 적어놓게 되고
  • SSB 에 data block 이 있는데 inode 에는 없다? 그럼 해당 data block 은 지운다.
• Segment usage table 도 업데이트
  • SSB 를 보고 live block count 를 새로 계산해서 SUT 에 업데이트
• Directory operation log…#draft
  • inode 상태 (reference count) 와 directory entry 상태를 sync
  • directory entry 가 있는지까지 확인을 해서 복구할지 말아야 할지 결정해야 하기 때문에 추가적인 log 를 수행 + roll forward 에서 복구

Evaluation §

• read 과정에서 inode map 을 타기 때문에 안좋아져야 할 것 같은데 좋아진 이유 - 논문에 있다?#draft sequential read 이기 때문에?
• sequential write + random update → 이 경우에는 write 순서가 다 깨져있으므로 이때 sequential read 를 때리면 왔다갔다 해야 하기 때문에 더 성능이 떨어짐

Seltzer vs Ousterhout debate §

• Seltzer 가 BSD 에 LFS 를 포팅했더니 최신의 FFS 에 비해서는 성능이 또이또이했다 - USENIX ‘93
• Ousterhout 는 이것을 공개 비판
• Seltzer 가 이것을 반영해서 새로 비교 - USENIC ‘95
• 뭐 그 뒤로도 여러번의 논쟁이 있었는데
• 결론은 완벽한 FS 을 만들기도, 이것을 비교하기도 어렵다더라
• ext 가 지금까지 살아있는 것은 LFS 에서 free space 가 20% 보다 떨어질 때부터 성능이 안좋아지는 문제 때문