Replication is a key technology that enables modern distributed applications to share data. This thesis suggests two building blocks that can facilitate various replication systems.
First, to support efficient implementations of interactive collaborative applications, replicated abstract data types (RADTs) are proposed as building blocks. Collaborative applications highly desire responsive and transparent interactivity, and such interactivity can be achieved with optimistic replication. However, maintaining replica consistency is difficult. Concealing complicated consistency maintenance, RADTs replicate copies of a shared ADT and allow optimistic operations of different orders. In this thesis, a few representative abstract data types (ADTs), such as array, hash table, and growable array (or linked list), are extended into RADTs. Operation commutativity and precedence transitivity are two theoretical principles enabling RADTs to maintain consistency for optimistic operations of RADTs. Especially, precedence transitivity is a practical and efficient way to achieve consistency, for which an s4vector is proposed. Above all, replicated growable arrays (RGAs) can maintain consistency among variable-length ordered objects with insertion/deletion/update operations, which have been highly demanded and studied in collaborative applications for a long time. RGAs make significant improvement in complexity, scalability, and reliability over the effects of the previous approaches. In this dissertation, the experimental results show that the operations of RGAs are more than thousands of times faster than those of the operational transformation methods which have been mainstream approaches for optimistic insertion and deletion.
Second, $\texttt{log}^\prime$ (log-prime) version vector is proposed for dynamic replication wherein replicas are frequently created and destroyed. In replication systems, version vectors are logged with replicas to detect conflicts among operations. Dynamic replications suffer from expensive logging overhead caused by inactive entries. Although the rigmarole of pruning vectors can delete inactive entries, pruned vectors may be incompatible without additional information, which also causes another overhead. $\texttt{Log}^\prime$ version vector consists of only three entries by the mathematic encoding based on the characteristics of prime numbers, and thus can be logged concisely with no pruning technique at a little sacrifice in accuracy. Simulation studies show that $\texttt{log}^\prime$ version vectors are accurate enough to detect almost all conflicts in the replication systems where all replicas are fully synchronizing.
본 연구는 복제(replication)를 위한 두 가지 새로운 구성 요소인 복제 추상화 데이터 타입(Replicated Abstract Data Types)과 로그 프라임 버전 벡터($\texttt{Log}^\prime$ version vector)를 제안한다.
우선, 상호 활동적인 협업 프로그램들의 제작을 위하여 복제 추상화 데이터 타입들은 선실행 명령어(optimistic operation)들을 지원하여 빠른 반응성(responsiveness)과 높은 상호 작용성(interactivity)을 지원하여 원활한 협업 작업을 가능하게 한다. 그러나, 선실행 명령어들은 분산 복제되어 있는 각각의 데이터 타입들이 모두 다른 순서로 명령어들을 실행하게 되므로 일관성(consistency) 유지가 어렵다. 이를 위해 명령어 교환성(operation commutativity)과 우선순위 이행성(precedence transitivity)라는 두 가지 원칙을 제시하고, 이 두 원칙들이 복제 추상화 데이터 타입의 일관성 유지에 효율적인 방법임을 보여준다. 또한, 우선순위 이행성을 구페적으로 실현시킬 수 있는 S4Vector를 제시하고, 이를 바탕으로 대표적인 세 가지 대표적인 추상화 데이터 타입(ADT)들인 배열(array), 해시테이블(hash table), 그리고 증가 가능한 배열(growable array)들을 각각의 복제 추상화 데이터 타입인 RFA(Replicated Fixed-size Array), RHT(Replicated Hash Table), 그리고 RGA(Replicated Growable Array)로 확장하였다. 특히, RGA는 순서를 가진 오브젝트들에 대해서 추가(insertion)와 삭제(deletion) 명령어를 지원하는 복제 추상화 데이터 타입으로써 과거의 다른 접근 방법들과 비교해서 복잡성(complexity), 확장성(scalability), 그리고 신뢰성(reliability) 면에서 우수하다. 또한, RGA의 우수한 성능을 실험을 통하여 보여줌으로써 RGA가 실제로 상호 활동적인 협업 프로그램들을 제작하는데 효과적으로 활용 가능함을 보여주었다.
다음으로, 동적인 복제환경(dynamic replication)에서 유용한 로그 프라임 버전 벡터($\texttt{Log}^\prime$ version vector)를 제안한다. 버전 벡터는 명령어(operation)들 간의 인과성 관계를 밝혀내어 명령어들간의 충돌(conflict)을 감지하고 이를 해결할 수 있는 실마리를 제공하는 복제시스템의 핵심적인 구성요소이다. 그러나, 기존의 버전 벡터는 동적인 환경, 즉 사이트들이 동적으로 참여하고 탈퇴를 반복하는 환경에서는, 벡터의 일방적으로 증가하는 데이터 구조로 인하여 값비싼 기록 오버헤드(logging overhead)와 복잡한 관리 방법을 요구한다. 새로 제안된 로그 프라임 버전 벡터는 소수(prime number)들의 곱에 로그(log) 값을 취하는 수학적 인코딩 방법을 도입하여 로그 프라임 벡터의 크기가 사이트의 갯수와는 독립적인 특성을 갖는다. 그러나, 디지털 시스템에서 무리수인 로그값의 표현은 에러(error)를 피할 수 없기 때문에, 에러를 최소화 할 수 있는 구현 방법을 제시하였다. 최종적으로, 본 연구는 제안된 로그 프라임 버전 벡터의 구현이 동적 복제 환경에서 충분히 감당할 수 있는 적은 양의 에러가 발생하며, 기록 오버헤드에서 상당한 이득을 보임을 모의 실험을 통하여 보여준다.
