Abstract
storage device의 발달, file scale의 증가로 filesystem design은 계속해서 변해왔다 근데, in-kernel file system에 이런 새로운 부분을 적용하는 것은 매우 challenging하다 그래서 user-space file system이 주목받아왔다. FUSE는 unix에서 제공하는 user-space file system인데 complex한 internal task가 overhead를 매우 크게 가져가서 성능이 그렇게 좋지 못하다. 해당 논문에서는 scalable message communication between the kernel and userspace를 사용한 새로운 user space filesystem RFUSE를 제안한다.
RFUSE는 per-core ring buffer structure랑 context switch, request copying을 줄여 transmission overhead를 줄였다.
이해
> FUSE는 scalability가 구린데, RFUSE는 cpu별로 ring buffer를 두는 방식으로 scalability를 좋게 만들었음
1. Introduction
filesystem design이 많이 발달되어 왔지만, in-kernel file system을 바꾸는 것은 매우 challenging하다. 매우 complex해서 misusing되었을 때 system crash 되는 등의 문제가 있고, 더해서 specialized file system을 추가하고 싶으면 그것 또한 매우 어려움 그래서 user-space file system이 주목을 받고 있다. user-space file system을 사용하면, 여기에서 에러가 생겨도 그게 system 전체에 영향을 주지는 않는다. 또한 easily portable하기 때문에 다양한 OS에서 사용될 수 있음.
FUSE는 유저가 custom file system을 만들 수 있는 framework를 제공한다. 그래서 specialized한 file system을 만들어서 사용하기 더 쉬워짐. 하지만, complex software stack을 가지고 있다는 단점이 있음 매 FUSE request는 VFS layer에서 만들어지는데, userspace의 implementation을 이루기 위해서 다양한 step을 거쳐야 한다. 이때 FUSE는 kernel, userspace 사이에서 context switch를 일으킨다. 그리고 FUSE driver는 file system request를 관리하기 위해 single Queue를 사용해서 scalable performance가 좋지 않다. 이러한 overhead는 많은 core, high performance device가 늘어가는 현대 사회에 더 좋지 않음.
해당 논문에서 제안하는 RFUSE는 몇 가지 특성으로 scalable communication을 지원한다.
> Scalable kernel-userspace communication
: RFUSE 는 per-core, NUMA-aware ring channel을 이용한다 그래서 request가 다른 channel을 통해서 전달이 되고 lock contention이 일어나지 않는다. 즉, 해당 방법으로 request processing의 parallelism을 구현해서 high scaliability 를 실현한다.
NUMA(Non-Uniform Memory Access)
각 CPU가 독립적인 local memory 공간을 가지고 있어서 여기에서는 lock contention이 일어나지 않고 바로바로 메모리에 접근이 가능하다. 근데 이러면 로컬 메모리가 아닌 다른 프로세서의 메모리에 접근하게 될 때 링크를 통해서 메모리에 접근해야되기 때문에 거기에서 성능 저하가 일어남 > 한 cpu에서 모두 처리할 수 있는 일은 다른 cpu의 메모리에 저장되지 않도록 하는 것이 중요하다.
> Efficient request transmission
: RFUSE는 ring channel을 kernel과 user space의 shared memory에 저장하고, request 요청과 reply 받는 것을 효율적으로 하기 위해 hybrid polling을 사용한다. 그렇게 해서 context switch, request copy overhead를 감소시킨다.
Interrupt vs Polling
: cpu가 IO를 기다리는 방법은 두가지로 나뉘는데, 기존에는 interrupt가 많이 쓰임. 근데 요즘은 device 기술이 많이 발달해서 I/O가 짧은 시간 내에 수행이 되서 return하는 경우가 많다. 이렇게 되면 오히려 interrupt를 거는 것이 context switch overhead를 늘리는 등 더 성능이 좋지 않다. 그래서 해당 논문에서는 일정 시간 동안 그냥 기다리다가 그 시간이 넘어가면 그때 interrupt를 기다리는 hybrid polling을 사용했다.
> Full compatibility with existing FUSE-based filesystems
RFUSE는 FUSE와 같은 API를 제공한다. 그래서 FUSE-based file system도 아무 수정없이 RFUSE를 사용하도록 변경할 수 있다.
2. Background and Motivation
2.1 FUSE ( Filesystem in user space )
FUSE 는 권한이 없는 사용자가 자기만의 file system을 커널 수정없이 만들 수 있게 제공하는 시스템
FUSE driver, FUSE daemon으로 나눠짐
fuse driver가 로드 되면 가장 먼저 /dev/fuse 라는 device를 만드는데 이게 VFS(virtual file system)이랑 FUSE-based file system을 연결시켜주는 중간 다리 역할을 함
FUSE Driver에는 다섯개 유형의 큐가 있다
background, pending, processing, forget, interrupt
맨 앞에 3개는 filesystem operation을 Daemon에게 날려주는 역할
forget queue dcache와의 communication
interrupt는 interrput request처리를 위한 큐 > 이때 이 인터럽트는 커널이 ongoing file system operation에 인터럽트 거는거
fuse filesystem을 기반으로 한 application이 file operation을 실행 ( 이건 아마 VFS에 최초로 전송되겠고 )
> VFS가 FUSE driver에 request를 보냄 > fuse driver가 request를 적절한 queue에 넣어준다.
이때 request는 두 가지로 나뉨
synchronous는 바로 pending queue 로 들어감
asynchronous(read ahead나 write back 같은 operation)는 pending에 들어가기 전에 background queue로 들어감
pending queue로 들어가는 asynchronous 수를 제한해서 bulk asynchronous로 인해 발생하는 문제를 예방한다.
이렇게 해서 synchronous operation이 미뤄지지 않고 바로바로 수행될 수 있도록 한다.
FUSE based system file operation
request > VFS로 전송 > VFS가 driver에 전송 > driver가 적절한 queue에 넣어줌 > 그걸 daemon이 수행
FUSE 기반 파일 시스템이 mount되면 FUSE Daemon이 시작되고 dev/fuse를 open해서 communication chnnel ( 이 communication은 아마 VFS <> FUSE driver 사이의 channel이겠죠 ) 을 열어줌
FUSE daemon은 worker 쓰레드를 시작 > worker 스레드는 read() System call을 불러서 file operation quest를 받아오려고 시도 > pending request가 없으면 FUSE Driver가 관리하는 wait queue에 들어가서 sleep ( cond variable을 쓰나 ? ) / request가 있으면 driver가 read system call에 pending queue의 operation하나 실어다가 return 해줌. > 스레드가 그 request 받아다가 parse해서 수행해준다.
FUSE driver와 deamon은 read(), write() operation을 dev/fuse에 수행해서 서로의 정보를 교환한다.
FUSE daemon은 여러개의 worker 스레드를 가질 수 있다. FUSE Daemon이 driver한테 request를 받았는데 그걸 수행할 스레드가 없으면 그 request handling 전에 새로운 스레드를 만든다. FUSE 에서 explicit한 스레드 개수의 제한은 없다. 하지만 pending queue entry 개수의 제한으로 implicit하게 스레드 개수를 제한할 수 있다
2.2. Overheads in Fuse
-> Latency Overhead
VFS layer와 path lookup에서 약 72%의 시간을 소모하고 있다.
VFS layer내에서 root -> subdirectory, file을 체크하기 위해서 kernel 모드로 실행해야함 근데 path-name resolution process는 Fuse daemon에 의해서 수행되어야 한다. 그래서 kernel <> Fuse Daemon 사이의 context switch가 자주 발생한다. 뿐만 아니라 request copy도 꽤나 크고, FUSE daemon을 기다리고 있는 application을 wake up 시키는 시간도 꽤 길다.
-> bandwidth overhead and scalability issue
VFS layer에서 전달되는 모든 operation들이 같은 pending queue ( 이 pending queue는 shared됨 > 아마 fuse driver안에 큐가 있는 듯 ) 에 들어가기 때문에 여기서 심각한 lock contention 문제가 발생 full bandwidth를 활용하지 못함 + scalable user file system을 만들지 못하는 장애물이 된다.
2.3 motivation
io_uring에 기반을 둠
io_uring의 작동 방식 :
Submission Queue : user space에서 발생하는 I/O 작업을 커널에 전달한다.
Completion Queue : 완료된 I/O 작업의 결과를 커널에서 user space로 전달
Queue의 구조
> head : 커널은 여기에서 entry를 가져옴
> tail : 사용자는 새로운 entry를 여기에 추가
그러면 커널은 큐의 상태를 지속적으로 확인하지 않고도 요청을 처리할 수 있음
커널은 submission에서 요청을 가져와서 결과를 completion에 저장
유저는 submission에 요청을 저장하고 completion에서 결과를 가져옴 (io_uring_enter를 이용해 둘다 수행 가능 )
io_uring은 low-latency device를 위해서 polled IO mode를 제공
해당 모드에서 kernel thread는 user application이 completion queue를 polling하는 동안 submission queue를 monitoring한다. > system call을 자주 만들지 않고 operation이 수행되도록 함
( 왜 monitoring 할까? user application이 polling하고 있다가 completion된 결과 값을 가지고 다시 IO request를 날릴 확률이 높으니까 kernel이 알아서 그걸 기다리고 있다가 들어오자마자 수행할 수 있도록 하는건가? )
io_uring은 shared memory mapped ring buffer between kernal and userspace to process message to/from block devices를 제공한다. (즉, shared memory니까 copy하지 않아도 된다는거겠지)
ring buffer가 많은 장점을 제공
(ring buffer는 들어오는 곳, 나오는 곳이 다르니까 뭘 기다릴 필요 없이 lock을 따로 두면 기다리지 않고 constant time안에 들어갈 수 있다는 얘기를 하는 것 같다 )
> message(request던 completion result던 )가 atomically하게 들어갈 수 있어서 constant time complexity가 정해져있음
그래서 많은 메시지들이 한번에 들어와도 low latency로 감당 가능
> scalibility가 좋음 ring buffer 사이즈 혹은 개수를 늘리면 scalable하게 성능이 좋아짐 특히 이 ring buffer를 cpu마다 두면 lock contention도 적게 일어남
3. Design
ring channel을 도입해서 kernel2user communication도 scalable하게 만들었다.
io_uring은 user2kernel communication을 제공하기때문에 fuse structure과 align하지 않았고, 얘만의 kernel context가 있어서 fuse랑 섞기 쉽지 않았기 때문에 얘를 가져다 사용하진 않았다
3.1 Overall Architecture
대신, 새로운 ring channel을 고안했다. FUSE와 비슷하게 rfuse 드라이버랑 daemon으로 구성
이때 fuse는 싱글큐를 사용하는 반면 rfuse는 ringchannel 을 기반으로 해서 코어별로 메시지를 전달하게 구현
RFUSE 드라이버가 로드되면, /dev/rfuse라는 device를 이용해서 코어별로 ring channel을 만들어준다.
> operation request가 parallel하게 처리될 수 있음
해당 file system에 마운트하면 mmap을 이용해서 링 채널이랑 유저 virtual address랑 mapping을 시켜줌
이렇게 해서 context switch 없이 user file system이 메시지를 exchange할 수 있게 함 ( 원래면 request나 result를 따로 버스나 이런걸 통해서 전달해줬나보다 그래서 이렇게 mapping을 시키면 그냥 그 자리에 각각 접근해서 활용할 수 있으니까 request, result할 때 context switch가 일어나지 않는다 .. 근데 어차피 request, result 받아오려면 context switch해야되는 거 아닌가? 왜 context swtich가 일어나지 않는다고 하는지 모르겠다 > 3.2 section 보면 이해될지도.. )
RFUSE driver가 daemon에 request를 보낼 때, 적절한 ring channel을 결정하는데 이때 current thread가 스케줄링된 cpu core id를 고려해서 그 cpu랑 연결된 ring channel에 넣어준다. ( 즉, RFUSE 기반 어플리케이션이 request함 그걸 mapping 해줄 때 그 어플리케이션이 어떤 cpu에서 스케줄링되서 하고 있는지 본다는 거 )
ring channel이 할당받는 메모리는 NUMA locality를 고려해서 allocate
하나의 ring channel이 각기 다른 NUMA node에 할당되어 있으면 request submission동안의 모든 access는 다른 numa에 접근하는 시간이 필요 > 이걸 완화하기 위해서 각각의 링채널을 같은 cpu 내부의 numa node에 할당해줌 그래서 데몬이 다른 numa에 접근할 필요가 없게됨 ( 즉 한 링채널은 무조건 한 numa node 안에 존재해서 다른 NUMA에 접근하지 않아도 된다. )
3.2 Scalable Kernel-userspace communication
각 ring channel은 3가지 ring buffer가 있음 pending forget interrupt
+ 두 개의 seperate buffer 에 background queue까지!
sync, async operation은 기존의 fuse와 같이 pending, background 으로 각각 들어간다.
pre-defined된 pending queue의 maximum 용량을 넘치 않기 위해 asyn operation들은 차례대로 하나씩 pending queue로 이동한다.
이때 request를 헤더 버퍼랑 arg 버퍼를 이용해서 처리
헤더버퍼 entry는 common, opaque로 나뉨 전자는 opcode, flag와 같은 기본적인 정보들을 포함한다.
Request submission동안 opaque header는 operation specific header를 들고 있는다. userspace에서 결과를 반환해주자마자 그 header buffer entry를 out header로 재사용한다. 이렇게 해서 request의 결과를 빠르게 driver로 전달할 수 있도록 구현 ( Request가 처리될때까지 opague header는 operation-specifiic header > 여기에 뭔 내용이 담겼는진 모르겠음 < 암튼 이걸 들고 있다가 request 처리가 되서 결과가 나오면 이 자리를 그대로 재사용한다는 것 같다. )
이 ring channel의 component들은 mount되어질 때 RFUSE daemon의 virtual address에 mapping이 된다.
이렇게 해서 RFUSE daemon이랑 커널이 shared memory를 가지게 된다. 이 shared buffer 영역을 통해서 kernel은 RFUSE daemon이랑 communicate를 할 수 있게 되었고, filesystem operation이 들어왔을 때, 메모리 영역을 할당하고 request를 copy해서 가져올 필요가 없게 되었다.
RFUSE는 header buffer, argument buffer를 track 하기 위해서 bitmap을 사용
bitmap의 모든 값들이 set되어 있다면 더이상 operation을 집어넣을 수 없다. 그러면 application thread는 sleep에 들어가고 request가 처리되서 빈 자리가 생기면 RFUSE가 자고 있는 스레드를 깨워주게 된다.
예시
VFS Layer가 RFUSE driver에 request 요청을 내렸다.
1. driver가 header buffer에서 entry를 하나 가져옴
2. common header 를 common parameter로 채워주고, opaque header에 CREATE request에 맞는 operation-specific header 값을 채워줌
2-1. CREATE는 file name을 인자로 받으니까 driver가 argument buffer에서 single entry를 가져오고 common header에 그거의 index를 채워주는게 필요
3. 해당 request가 기다리고 있다가 pending queue에서 dequeue되면 header buffer의 index를 가져오고 그 header를 userspace file system에 맞춰서 parse해 가져온다.
4. 실행이 끝난 후에 CREATE는 총 2개의 return 이 있는데 entry_out_header ( 만들어진 파일의 meatadata) 랑 open_out_header(만들어진 파일의 file descriptor information)을 return한다.
5. opaque header랑 argument entry 를 재사용해서 저 return 값들을 전달한다.
3.3 Worker Thread Management
각각의 링 채널별로 RFUSE Daemon은 그 채널의 operation을 관리하는 스레드를 만든다.
이때 그 스레드는 거기에 해당하는 cpu에 묶여있어서 cpu affinity를 잘 이용할 수 있다
완벽히 lock contention을 없애려면 한 ring channel에 한 스레드를 배치하는 것이 좋음
근데 그렇게 하면 성능이 하락된다 FSYNC같은 오래걸리는 operation이 앞에를 차지하고 있으면 그 뒤에 이어지는 operation들은 계쏙 기다려야 하니까 근데 그렇다고 마냥 operation 별로 무한정 스레드를 찎어내면 또 안된다 그러면 한 cpu내에서도 lock contention이 일어나니까
그래서 RFUSE는 한 ring channel 당 여러 개의 스레드를 허용하지만, 맥시멈 숫자를 정함
3.4 Hybrid polling
fuse 에선 더이상 처리해야될 리퀘스트가 없을 때 혹은 데몬의 스레드들은 잠이 들고 또 application이 fuse daemon의 return을 기다려야될 때 잠에 듬 얘네를 깨울때 시스템콜을 사용하면 또 context switch가 발생해서 좋지 않다
그래서 rfuse 에선 polling 방법을 채택
work thread는 pending ring buffer의 request의 head pointer를 poll하고 ( 여기서 뭐가 생기면 바로 처리해줘야되니까 > sleep하지 않는다. )
application thread는 header buffer 안에 있는 그들의 request의 completion flag를 모니터 한다.
이렇게 하면 context switch가 사라지고 스레드를 깨워야하는 오버헤드가 사라진다
하지만 이렇게 되면 cpu가 낭비되는 경우가 생겨서 user-defined 시간동안은 기다리고 이 기간을 넘어가면 sleep하는 hybrid polling을 도입했다.
RFUSE daemon도 비슷하게 작동한다. polling하는 시간 동안 pending ring buffer에 새로운 요청을 기다리고, 그 시간이 지나면 wait queue에 들어가서 잠에 든다.
3.5 Load Balancing of Async Request
Async 요청은 pending되기 전에 back ground에서 기다리는데 burst async가 sync에 영향을 주지 않도록 잘 스케줄링 하는 것이 중요하다
근데 cpu id에만 맞춰서 들어가면 너무 한 cpu에 burst async가 몰리게 된다
> load balancing policy를 도입
1. 현재 백그라운드에 pending ring channel의 capacity를 넘는 async request가 잇는지 확인
2. 지금 daemon 스레드 중에 자고 있는 애들이 있는지 확인
위 두 가지의 경우에 모두 해당되면 congestion이 일어나고 잇다고 확인 ( 이거 확인은 누가 하는거지.. )
congestion이 확인되면 rr 방법으로 다른 ring channel에 request를 나눠준다.
3.6 Transmission ring channel Information
RFUSE 데몬은 ring buffer, header buffer 이런거의 in-kernel data structure의 위치를 알아야함
1. ring channel의 component를 VMA에 mapping ( by mmap() )
2. read, write할 때 data page가 준비되어 있는지 확인
3. ring buffer와 연결되어잇는 sleep state를 ioctl을 사용해 바꾼다 > 스레드가 polling을 멈춰야할 때
4. ioctl로 어플리케이션 깨우기 > completion기다리면서 잠든애
이 주소들은 kernel driver에 의해서 create, manage 됨.
그래서 daemon은 커널 상태로 진입하기 전에는 그 정확한 주소를 알수가 없음
> daemon은 kernel driver랑 communicate할 때 physical address를 사용하지 않고 다른 정보들을 활용 ( like ring channel ID, ring buffer type 등등 ) 이렇게 해서 physical address를 몰라도 kernel driver랑 communicate할 수 있게 한다. mmap system call이 불리면 이 logical identifier 들이 encode되서 kernel driver에 전달된다.
: ioctl할 때 이 숫자를 third 인자로 전달 ( 이게 안에서 어떻게 parsing되는지 모르겠다 )
3.7 Memory usage of Ring Channels
daemon에 의해 매핑된 ring channel은 해당 파일 시스템이 unmount될때까지 계속 메모리 자리를 차지하고 있음
링채널의 수 == cpu 코어의 수 그리고 ring buffer의 entry == header buffer의 entry
그래서 만약 두 개의 인자를 받는 함수가 있으니까 ( like rename ) arg buffer는 ring buffer보다 사이즈가 두배여야 함
> 계산식 확인
3.8 Compatibility with FUSE
RFUSE는 FUSE의 API를 다 그대로 남겨뒀기 때문에 FUSE 기반 시스템도 이걸로 변경할 수 있다.
'백업용' 카테고리의 다른 글
| AI 활용 표현과 문제해결 수업 - CNN 모델 제작 코드 (0) | 2023.04.04 |
|---|