본 글은 논문 Exploiting Nil-Externality for Fast Replicated Storage (SOSP '21) 를 읽고 정리한 글입니다.
별도의 명시가 없는 한, 본 글의 모든 그림은 위 논문에서 가져왔습니다.
목차
NXSECTION
- 이후에 등장하는
1.x.section 들은 논문 본문에는 없고 주인장이 임의로 자른것이다.
1.1. Storage Interfaces and Nil-externality
- Interface 를 잘 정의하면 뭐 유지보수성같은 측면 외에도 성능의 관점에서도 이득이 있는 경우가 있기 때문에, 이것은 매우 중허다고 할 수 있다.
- 가령 idempotent interface 와 같은 경우에는 recovery 를 경장히 단순하게 해준다.
- 그럼 storage 에서 높은 성능을 제공할 수 있는 interface 특징이 있을까? 본 논문은 이 질문에 대해 Nil-externality 로 답하고 있다.
- 이놈은 storage 의 상태를 변경 (즉, 데이터를 저장하는 등의) 할 수는 있지만 그 변경된 상태를 외부에 곧바로 노출시키지는 않는 interface 들에 대한 특징이라고 할 수 있다.
- 상태를 곧바로 노출시키지 않기 때문에, 이런 operation 들은 lazy 하게 처리할 수 있고, 따라서 성능이 향상될 수 있다.
1.2. Replicated Storage
- 본 논문에서는 이러한 Nil-externality 를 replicated storage 에 활용해 빠른 replication 을 달성하면서도 데이터의 일관성은 잃지 않는 새로운 방법을 제안한다.
- 여기서의 일관성은 “작업 순서에의 일관성” 라고 생각하면 된다. 여러 작업을 여러 node 에서 동일한 순서로 처리하면 결과적으로 동일한 상태의 데이터가 되기 때문.
- 이것을 논문에서는 Linearizability 라고 부른다.
- 기존까지는 replicated storage 를 구현하는데에 있어 이 순서를 “합의 (consensus)” 하는 알고리즘을 이용해 왔다.
- VR 기준으로 설명하면, 이것은 대략 다음과 같은 단계로 진행된다.
- 일단 leader 가 request 를 받게 되면, 그것의 순서를 결정한 뒤에, 자신의 log 에 적는다 (ordering and making durable).
- 그리고 이 순서와 operation 을 follower 들에게 뿌린 후, 만약에 follower 가 이 순서에 동의한다면 leader 에게 응답한다 (replicating).
- Leader 는 follower 로부터 Quorum 만큼의 응답을 기다린 후, 응답이 오면 이것을 처리한다음 응답한다 (executing and replying).
- Follower 또한 이것을 처리한다.
- 하지만 보다시피 이런 순서에 대한 consensus 의 과정에서 2-RTT 가 필요하고, 이것이 성능을 저하시키게 된다.
1.3. Deferring
- 그럼 위의 단계 중에 lazy (defer) 하게 처리할 수 있는 것을 생각해 보자.
- 일단 durability (log 에 적는) 는 lazy 하게 실행할 수 없다. 단순하게 생각해도 ACK 를 먼저 날려버리면 해당 operation 이 log 에 적히기도 전에 다른 operation 이 와서 write 가 누락될 수 있기 때문이다.
- 하지만 다행인 것은 이 durability 는 consensus 가 필요 없다는 것이다.
- Client 가 직접 replica 들에게 request 를 날려 quorum 이상의 log 가 저장되었는지를 체크하는 식으로 1-RTT 에 durability 를 보장할 수 있다.
- 그럼 ordering, replicating, executing 은 lazy 하게 처리할 수 있을까? 여기서 nilext 가 등장한다.
- Nilext operation 의 경우에는 지금 당장 storage 의 상태를 노출하지 않아도 되기 때문에 이러한 ordering, replicating, executing 을 lazy 하게 처리할 수 있다.
- 이런 deferring 으로 성능이 향상될 것 같기는 한데, 실제로 이런 nilext operation 들이 실용적으로 사용되고 있을까? 본 논문에서는 이런 nilext operation 들이 실용적일 뿐 아니라 “팽배” 하다고 주장한다.
- 가령 KV store 에서 key 에 대한 value 를 추가하는
PUT은 많이 사용되는 operation 인데, 실행 결과가 externalize 되지 않기 때문에 이놈은 nilext 하다고 할 수 있다. - 또한 LSM 와 같은 write-optimized data structure 에서는 거의 모든 update 를 nilext write 로 변형한다.
- 심지어 값을 읽어들인 다음에 그 값을 이용해 update 를 하는 경우에도 실제로는 읽은 뒤에 저장하는 것이 아닌 “읽어들인 뒤에는 어떤 것으로 update 해야 하는지” 에 대한 function 을 write 하는 식 (즉, lazy evaluation 과 유사) 으로 구현해서 이 또한 nilext 의 특성을 가진다.
- 가령 KV store 에서 key 에 대한 value 를 추가하는
- 그래서 key idea 에 대해 다시금 정리해 보자면,
- durability 는 1-RTT 에 eager 하게 보장되지만,
- ordering 과 executing 은 background 로 처리되어 이것을 externalize 하는 시점 전까지 lazy 하게 적용되는 것이라 할 수 있다.
- 이러한 deferring 은 다른 곳에서도 종종 사용되던 것이고, 본 논문에서는 그것을 storage replication 에 적용한 것이다.
- 가령 functional language 에서의 Lazy evaluation 이나
- File IO 에서 external synchrony (이거, 이거, 그리고 이거)
- 하지만 이 방식은 speculative 와는 거리가 좀 있다.
- Speculative execution 에서는 ordering 의 overhead 를 줄이기 위해 order 가 맞다고 간주하고 execution 을 해버린 다음, order 가 맞는지 나중에 확인하는거라면
- 여기에서는 ordering 과 execution 을 전부 뒤로 미뤄버린 것이기 떄문이다.
1.4. Non-nilext Operation Consideration
- 물론 그렇다고 모든 operation 을 nilext 화 하는 것은 실용적이지 못할 것이다.
- Read operation 은 기본적으로 nilext 가 아니고, 경우에 따라서는 바로 결과를 받아봐야 하는 write 도 있을 것이기 때문.
- 따라서 이러한 경우에는 correctness 를 위해 어쩔 수 없이 deferring 을 하지 않는다.
- 하지만 위에서도 말했다시피 이런애들은 그렇게 흔하지 않다.
- Memcached 에서의
PUT이나 - ZippyDB (RocksDB + Paxos)
PUT,DELETE,MERGE같은 애들은 아주 많이 쓰이는 API 임과 동시에 nilext 하기도 하고 - IBM 과 Twitter 의 production trace 에서도 nilext operation 이 아주 많이 사용되는 것을 확인할 수 있었다고 한다.
- Memcached 에서의
- 또한 read 는 synchronous ordering 을 발생시키기는 하지만, 모든 read 가 그런 것은 아니다.
- Ordering, executing 이 background 에서 돌아가고 있기도 하고,
- 한번 read 를 해서 ordering 이 된 애들은 다음부터는 이런 synchronous ordering 을 발생시키지 않기 때문에 빈도가 그리 높지 않다.
1.5. Methodologies
- 그래서 본 논문이 제시하는 Skyros (그리스 스키로스 섬) 는 linearizability 를 보장하는 동시에, nilext interface 에 대해서는 1-RTT 에 작업을 완료하여 performance 를 최적화하는 것에 방점을 둔다.
- 이를 위해 VR 과 같은 state machine replication 을 변형하여 implement 하였고, 여기에 녹아들어간 주요 테크닉들은 다음과 같다.
- Supermajority quorum 을 사용한다. 즉, 단순히 에서의 majority quorum 인 이 아닌 이것보다 큰 quorum 개수를 사용한다는 것.
- 또한 1-RTT durability 를 위한 Durability log 를 추가적으로 사용한다.
- 그리고 1-RTT read 시에 defer 된 operation 들이 완료되었는지를 체크하기 위한 order-and-execution checker 를 사용한다.
- 마지막으로 DAG-based topological sort 로 order 를 복구하는 방법도 사용한다.
1.6. CURP Integrations
- Commutativity 는 수학에서의 “교환법칙” 을 생각하면 되는데, 이 CURP 라는 것은 이러한 “교환이 가능한 (Commute)” 애들은 ordering 이 불필요하다는 것을 활용한 1-RTT replication algorithm 이다.
- 하지만, CURP 에서는 만약에 conflict 가 발생하거나 commute 가 불가능한 경우에는 3-RTT 라는 엄청난 penalty 를 떠안게 된다는 문제점이 있다.
- Conflict 라는 것은 간단하게 말하면 KV store 에서 동일한 key 에 대한 request 가 발생하는 경우로, 이때는 어쩔 수 없이 ordering 이 필요하다.
- 가령 GFS workload 에서는 여러 client 가 같은 file 에 write 하는 경우가 다반사고, 따라서 이 때는 성능이 좋지 않게 나온다.
- 반면에 Skyros 에서는 nilext 에 대해 이러한 ordering 을 defer 하기에 이런 3-RTT penalty 가 없다는 장점을 가진다.
- 근데 이게 중요한게 아니고 중요한 것은 이런 nilext 와 commutivity 가 양립할 수 있다는 것이다.
- 간단하게 말하면, commute 가 가능한 애들은 ordering 을 defer 하는 것도 아니고 그냥 원천적으로 없애버릴 수도 있고
- 만약 commute 가 불가능한 애들은 nilext 에 대해 ordering 을 defer 하는 방식으로 CURP 에서의 3-RTT 를 완화할 수 있는 것이다.
- 이런 점에 착안해 본 논문 마지막에는 이 둘을 짬뽕한 Skyros-COMM 을 구현하여 evaluation 하였다고 한다.
1.7. Evaluation Summary
- 일단 nilext-only workload 에 대해서는 batching 을 사용하지 않은 Paxos 에 비해 3배 throughput 이 좋았고, batching 을 사용했을 때에는 동일 throughput 일때 latency 가 3.1배 낮았다고 한다.
- 추가적으로, write-only 등의 extreme case 까지 포함해 다양한 상황에서의 evaluation 을 수행했고, 거의 모두 baseline 인 Paxos 보다 동등하거나 더 좋았다고 한다.
- YCSB workload 에 대해서는,
- Write-heavy 일 때는 1.7배에서 2.3배까지 성능 향상이 있었고
- Read-heacy 일 때는 평균 성능 향상은 미미했지만 P99 latency 의 경우에는 70% 더 좋았다고 한다.
- CURP 와 비교했을 때에는
- Commute 한 경우에는 거의 동일한 성능 향상이 있었지만
- Commute 하지 않은 경우에는 throughput 은 2배, P99 latency 는 2.7 배 더 좋았다고 한다.
1.8. Contribution Summary
- 본 논문의 contribution 은 크게 4가지이다:
- 우선 Nil-externality 라는 것을 정의하고, 이것이 팽배한 operation 인 것을 확인했다.
- Nil-externality 를 consistent storage 에서 활용하는 방법에 대해 소개했고
- 이것을 활용한 fast replication storage 인 Skyros 를 설계하고 구현했으며
- 이것을 충분한 evaluation 으로 그의 가치를 증명해 냈다고 한다.