CHOI HWAN JOON 2010. 08. 02
Application 은 concurrency 와 system failure 에직면했을때의정확성을위해 OS Resource 를 Synchronous 하게접근해야한다. System transaction( 이하 ST) 은개발자가여러종류의 System resource 를 OS가보장하는 ACID 한특성을이용해명시적으로변경할수있도록허용한다. ST 는다른기술로는다루기힘든끊임없는병렬성의문제를효율적이고깨끗하게풀어낸다. 예를들면 ST는 TOCTTOU 경쟁조건때문에발생하는 file system의보안취약성을제거한다. ST 는소프트웨어설치실패의경우 file system 에충격적인병렬적이고독립적인업데이트없이롤백을가능하게합니다. 이논문은 ST 를구현한 Linux2.6.22의변종인 TxOS를설명합니다. TxOS 는빠르고직렬화된 transaction, 그리고 ST와 non-transactional activity 사이에강력한독립성과공정성을제공하기위해새로운구현기술을사용합니다. 이논문의 prototype은상품화된 HW에서동작하는충분히발달된 OS 가타당한성능비용이드는 ST 를제공할수있음을보여줍니다. 예를들면, OpenSSH 의 transactional installation 이오직10% 의오버헤드만을가지는경우와, 리눅스의 non-transactional 컴파일이 TxOS 상에서무시할수있을정도의오버헤드만을발생시키는는경우가있습니다. transactions 을 central OS abstraction으로만드는것만으로 TxOS는새로운 transactional 서비스를가능하게합니다
Atomicity 모든작업이수행되거나아무것도수행되지않거나. Consistency Transaction 의성공 / 실패와상관없이일관성유지 Isolation 각 Transaction 은동일데이터를동시에읽고쓸수없음 Durability Transaction 완료후, 그결과는영구히반영
Time of check to time of use Other Applications
File System Race condition 의보안취약성제거 Transactional SW Install (10% Overhead) Crash consistency (LDAP) User level transaction
프로그래머가 system resource 를일관되게접근할수있는추상화를제공 OS resource(files/pipes/signals) 에대해ACID sys_xbegin() ~ sys_xend() transactionti 처리 Strong isolation : 같은 OS 리소스에대한 transactional 과 non-transactional update 에대해 serialization i 을제공하는것
EX) Transaction A/B 두 Transaction이서로대기한다면 system 은둘중하나를 Restart. OS가선점형이라면 non-transactional thread 를지연시키면서 transactional thread가오랬동안수행되는것을허용. ST가오랫동안수행되며모든 system resource를점유하는것을원하지않으므로 limitation 이존재함 (memory/disk space or kernel thread count)
ST 의 ACID 는 system state 를위한것이다. App state를보장하지는않는다. 따라서 ST가 abort 되었을때 App address space 까지책임지지않는다. 이를위해 TxOS는 checkpoint and restore 메커니즘을제공한다
하나의 ST 안에서다른 thread 의 nontransactional process와통신하는것은 deadlock 유발가능함. (IPC 로보내려고해도 commit될때까지 buffering됨 ) 이것은기본 isolation 전제에위배됨
TxOS 는 kernel memory buffer 와 data structure를이용해 data read / write를 isolate 시키는것으로 ST 를구현했다. Application 이 data를 file system 이나 device에쓰려고할때그 update 는 commit 될때까지 OS buffer 에들어간다. TxOS transaction 은 main memory 에꼭들어맞아야한다. (commit 되지않은 transaction이 disk 로 swapping 되는것은한계점임 future work)
Interoperability Old Transactional system transaction 과 non-transactional 이충돌할경우 transaction이 Rollback 가능하기때문에 transaction을우선 abort. 이러한접근은 fairness를약화 TxOS Non-transactional thread 가 critical section에접근하기전에발견되면 Non-transactional thread 를 suspend 시켜서 fairness 확보.
Eager version management DB나 Old transactional OS는 data를수정하고 undo log를남김. 즉 Transaction을 isolate시키고 commit시까지 lock한다. (Two phase locking). 하지만 Dead lock 을유발가능하다. Dead lock 은 time out 을두는것으로해결하지만 time out 의길이를결정하는것은어렵다. 또한높은우선순위 task 가 block 될수있다. Lazy version management TxOS 는 Transaction 이 Private copy 에서동작. App 은 kernel lock을절대로가지지않는다. 따라서 TxOS는데드락을피할수있다. 대신 commit latency 가발생할수있다.
According to the two-phase locking protocol, a transaction handles its locks in two distinct, consecutive phases during the transaction'ss execution: Expanding phase (number of locks can only increase): locks are acquired and no locks are released. Shrinking phase: locks are released and no locks are acquired. http://en.wikipedia.org/wiki/two-phase_locking phase
Transaction 이 Shared kernel object 에접근하는경우, shadow object 라고불리우는 private copy 를만들어서거기다먼저반영후바꿔치기한다. 단 transaction 자체가충돌없이끝났으나바꿔치기할때충돌할수있다. 왜냐하면바꿔치기한다는의미가이객체를참조하는녀석들을다찾아서그포인터를업데이트하는것인데, 이것은여러곳에걸쳐있고여러가지이슈가생길수있으므로위험하다. 이를위해 disjoint object 를사용한다
해당 object 를헤더와데이터로나눠서헤더는재 해당 object 를헤더와데이터로나눠서헤더는재사용하고데이터만바꿔치기한다
많은 Kernel object 들은오직읽기를위해서만사용된다. Shadow copy를만드는 overhead를피하기위해서 read only 모드를가능하도록한다. (reference counter존재 ) 모든 Reference counter 가 0 이된이후에 shadow 를 update한다. (Read-copy update)
Atransaction 이 Btransaction 에의해점유된 object 를접근할때충돌이발생 Transaction 이발생한 object 를또다른 non- transactional thread가접근하려는경우 (vice versa) TxOS 는 tx_data 를 transaction 처리가되는모든 shared kernel object 의헤더에위치시킨다. tx_data 는 transactional writer 와 reader list 를포함한다. Writer는현재활성화된 transactional writer를가리키는포인터임. Thread 가충돌을감지한경우 TxOS는이필드를사용해서충돌상태인지판단한다.
충돌발생시분쟁해결을위한 contention manager 호출됨. 높은우선순위프로세스우선 같은우선순위면오래된프로세스우선
What is Asymmetric? Transactional 과 non-transactional thread 가충돌 How to solve transaction은언제나 abort나 roll back 가능 non-transactional 은롤백할수없음. non-transactional thread가롤백할수없지만 critical region만아니라면선점되거다 deschedule 될수있다. non-transactional thread가너무많이transaction을 abort 시키면 kernel 이 transaction이굶어죽는것을막기위해 wait queue 에넣어버린다
Transactional state 를관리하기위해메타데이터와통계를저장하는 transaction object 를 Kernel에더했다. Kernel의 thread control block 는 transaction object를가리킨다. Thread 는최대한 1 개의 active transaction 을가진다. 만약다른 Thread와충돌하고이겼을경우상태가 atomic하게변경된다. Transactional system 이충돌때문에완료할수없는상태가되면 Abort 한다. Checkpointed_registers : Roll-Back 을지원하기위한필드로, 트랜젝션중멈추면 checkpoint 로가는것 Defer_event : commit 시까지연기할이벤트저장 Workset_ list : 어떤 transaction이 private copy를가지고있는지를저장, 각 Entry는 stable object 와 shadow copy를가지고있음 transaction 이 work set 에어떤리스트를추가한다는것은 reference count 를증가시킨다는것을의미함.
Prepare sys_xend() Do Something sys_xend() System transaction 결과에따라작업수행 * 일단 Prepare 되면충돌이예상되는작업을하려는또다른 Thread 는 Stall / rollback
TxOS 는 Virtual file system layer 에서충돌을감지하고 versioned data를관리하는것으로 transactional file system 을만드는것을단순화한다. OS는 versioning update 와충돌감지를제공한다. File system 은오직 atomic 한 commit 과 stable 한저장만을제공한다.
Multi thread 가같은 transaction 에참여한다. 같은 transaction에있는thread는 address space 를공유한다. 또는다른 address space 에있을수도있다. 같은 transaction에있는thread들은공유되고 serialize 하게특정상태에접근한다. Process 가 Transaction 이시작되고나서 fork 모든자식프로세스가 sys_xend해야 commit 된다 fork 하고 Transaction 시작 다른프로세스이므로상관없음
TxOS 의 signal 은다른 transaction 에있는 thread 간 isolation을제공한다. non-transactional 과 transactional thread간 isolation을제공한다. Transaction 내부가아닌 thread로의 signal 은 commit 시점까지연기된다. Transaction 이시작되고내부로들어오게되는 signal 은연기되거나수행된다. Speculative delivery : transaction 이좀더responsive하게된다. Deferred delivery : transactionti 을 atomic 하게보고 commit 시까지연기한다.
Networking transaction내부에서어떤 network communication이 commit시까지buffering 되거나 delay되어야한다 IPC 현재 TxOS에서 kernel thread 간에는제공되지만한계가있다. 한 transaction이 abort 되었을때 IPC로메시지를주어다른 transaction이 abort 되는것 User interfaces Transaction 내부에서 user 입력을받는경우를처리못함 Logging 지원하기가복잡하고성능이떨어진다. 예를들어 password attack을하는사람이하나의 transaction에넣고계속공격하면 실패하면 log 마저도 commit되지않는경우도생긴다. 이런것까지방지하려면복잡해진다. 혹은너무 sensitive 하다
Goal : 트랜잭션을효율적으로처리 / non transaction의오버헤드줄이기 Base : transaction 더했을경우 Static S i : transactional list (for concurrency) NoTx : thrad가 transaction을수행하고있는지검사 (2% 이하 slow down) Bgnd TX : non-transactional thread 수행 ( 다른 transaction 있을경우 ) InTX : 트랜잭션내부 TX : sys_xbegin, sys_xend 추가시오버헤드
Post mark : 파일시스템벤치마크 E-mail, network news, e-commerce client LFS Small file benchmark - 10000 개 1024byte 파일 Large file - 100MB read/write RAB 500 개파일생성 mkdir 20000 cp 500 copy to 500 Dir = 250000 For LFS large : 13% 추가메모리사용 For many small file : 1% space 사용 Dpkg (Debian package manager) SW install 에 ACID를제공한다. 25000라인짜리에디터
DB 서버같은 LDAP Server 를테스트 BDB : Berkeley DB LDIF 는 transaction 이없다.
TxOS sys_xbegin() Link Unlink sys_xend()