Performance-optimal read-only transactions

Haonan Lu, Siddhartha Sen, and Wyatt Lloyd. 2020. Performance-optimal read-only transactions. In Proceedings of the 14th USENIX Conference on Operating Systems Design and Implementation (OSDI'20). USENIX Association, USA, Article 19, 333–349.

N+O+C を performance optimal read-only transactions と定義している．

NOC: **O**ne round of **N**on-blocking communication with a **C**onstant amount of metadata

これに **S**trict serializabilityを加えてNOCS. このNOCS is impossible を定理立てて証明しているのが個人的見どころ．

証明の中では C がfully exploitされていて，metadata が constant ではN+O+Sが不可能であることを帰納法で証明している．

具体的には，NOCSではメタデータがサーバ数に比例して増大する．

この論文ではその解決としてNOCを維持してSを一部妥協したPORTというデザインを提案している．

所感

研究的には，Sをあきらめるならよくあるsnapshot readsでもよいわけだから（この論文でもそれに言及している），Sを諦めずefficientに実装する方法を考えることがテクニカルだと思う．

でも，実践的には，freshnessが保障されないことをアプリケーションユーザに意識させるほうがうまくいくしスケールするだろうとも思う．