As a software Distributed Shared Memory (DSM) becomes attractive on a large system, the focus of attention moves toward improving the reliability of a system. A fault-tolerant DSM has to achieve high reliability and at the same time preserve high performance during failure-free execution. In this thesis, the aim of our work is to propose novel fault-tolerant schemes for efficient software DSMs.
A common approach to fault-tolerant software DSMs is to take checkpoints with message logging. In order to achieve our goal, we first propose an efficient logging scheme, called the remote logging, on a home-based software DSM. The remote logging stores data indispensable for recovery into the volatile memory of a remote node. The remote logging tolerates multiple failures if the backup nodes of failed nodes are alive. It makes the reliability of software DSMs grow much higher. In addition, the logging overhead can be moderated with high-speed system area network and user-level DMA operations supported by modern communication protocols. Thus, the remote logging leads to much lower failure-free overhead than traditional stable logging, which flushes logs into local disk at each synchronization point.
To further enhance the performance of failure-free execution, we propose the lightweight checkpointing scheme dedicated to software DSMs. In our scheme, each node takes no checkpoint of shared memory, but saves the execution states and non-shared data only. When a node fails, it regenerates its pages from the remote copies in live nodes. In order to efficiently reconstruct pages, we extend the remote logging and introduce a XOR-diffing technique. The cliff logs, which have been created by XOR operations during failure-free execution, can be applicable to any version of remote copies either backward or forward for recovery. Experimental results shows that our new approach achieved better performance than traditional independent checkpointing. The performance improvement comes from the reductions in the checkpointing time. Moreover, the imbalance in execution times among nodes, which is the problem of independent checkpointing, can also be alleviated as checkpointing overhead is reduced.
소프트웨어 분산 공유 메모리(software Distributed Shared Memory) 시스템은 각 노드에 분산된 메모리를 공유 메모리로 인식할 수 있도록 사용자에게 가상의 이미지를 제공해준다. 최근까지 분산 공유 메모리 시스템의 성능, 확장성, 프로그램의 용이성을 향상시키기 위해 많은 연구들이 이루어져 왔으며, 그 결과 분산 공유 메모리 시스템은 큰 규모의 시스템 상에서 효율적인 병렬처리를 위해 이용될 수 있었다. 한편, 병렬 시스템의 규모가 점차 커짐에 따라 시스템에서 고장이 발생할 가능성이 높아지게 되었다. 분산 공유 메모리 시스템에서는 노드들 사이에 데이터가 공유되므로 한 노드에서 고장이 발생해도 전체 노드의 재 수행이 요구된다. 따라서 오랜 기간 동작하거나 높은 가용성을 요구하는 응용 프로그램들을 위해 분산 공유 메모리 시스템에서 고장 허용성을 제공해 주는 것이 중요하다.
고장 허용을 위해 일반적으로 많이 사용되는 방법은 체크포인팅(checkpointing)과 롤백(rollback) 이다. 이는 프로그램 수행 중 주기적으로 시스템 이미지를 안전한 저장 장치에 저장하고, 고장이 발생했을 때 체크포인팅 시점으로 되돌아가서 수행을 계속하는 방법이다. 분산 공유 메모리 시스템에서는 공유 페이지를 매개로 여러 노드 사이에 의존 관계가 형성되므로 올바른 시스템 상태로 복구하기 위해 한 노드의 롤백이 다른 노드의 롤백을 연속적으로 요구하는 도미노 현상이 발생할 수 있다. 이를 방지하기 위하여, 각 노드가 독립적으로 체크포인팅을 수행하고 더불어 각 노드 간에 교환되는 메시지를 로깅(logging)하는 방법들이 많이 연구되었다.
고장을 허용하는 소프트웨어 분산 공유 메모리 시스템은 높은 안정성을 제공하는 동시에, 정상 수행 시의 성능 감소가 크지 않아야 한다. 본 논문에서는 이러한 두 가지 사항에 초점을 맞추어, 분산 공유 메모리 시스템을 위한 효율적인 고장 허용 기법을 제안한다.
우선, 본 논문은 오버헤드가 적은 원격 로깅(remote logging) 기법과 복구 기법을 제안한다. 원격 로깅은 각 노드 마다 로그 홈(log home)이라는 특정한 노드를 할당하여 복구에 필요한 메시지 데이터들을 로그 홈의 메모리에 로깅하는 방법이다. 본 방법은 시스템의 안정성을 높이는 방법으로써, 여러 노드에서 동시에 고장이 발생했을 경우에도 그들의 로그 홈이 살아있는 한 항상 복구가 가능하다. 고장이 발생한 노드들은 각각 롤백 한 후 자신의 로그 홈에 있는 로그를 이용하여 연산을 재수행한다. 원격 로깅 방법은 정상 수행 중 빈번한 디스크 접근을 요구하지 않으므로 효율적이다. 특히, 고속의 네트웍 환경에서 사용자 계층 통신 프로토콜의 원격 메모리 쓰기 기능을 활용할 때 로깅으로 인한 성능 감소를 최소화 할 수 있다.
실험 결과, 로그를 디스크에 저장하는 기존의 안정적 로깅(stable logging) 방법은 동시에 발생하는 모든 고장에 대해 항상 복구가 가능한 반면, 빈번한 디스크 접근으로 인한 성능 감소가 최대 206%에 달하였다. 또한 기존의 휘발적 로깅(volatile logging) 방법은 로그를 메시지 전송 노드의 메모리에 남기는 방법으로써 그 오버헤드는 안정적 로깅에 비해 크지 않았지만 언제나 한 노드의 고장만을 허용한다는 제한점이 있었다. 그러나 본 논문에서 제안하는 원격 로깅 방법은 최대 81%의 성능 감소로, 한 노드 이상에서 동시 발생하는 고장을 허용함으로써 시스템 안정성을 높일 수 있었다.
두 번째로, 정상 수행 시의 성능을 더욱 향상시키기 위하여 본 논문에서는 고장 허용 소프트웨어 분산 공유 메모리를 위한 효율적인 체크포인팅 기법을 제안한다. 체크포인팅은 고장 허용 시스템에 있어서 필수불가결한 것이며 일반적으로 프로세서 및 운영체제의 상태, 메모리에 있는 데이터들을 모두 디스크에 저장하기 때문에 그 지연 시간이 성능에 많은 영향을 미칠 수 있다. 특히, 이러한 데이터들 중 공유 메모리는 그 크기가 일반적으로 크기 때문에 체크포인팅으로 인한 성능 감소의 주요한 원인이 된다. 그러나 대부분 기존의 체크포인팅 기법들은 소프트웨어 분산 공유 메모리에 특화된 방법들이 아니며 이러한 특징을 간과하고 있다. 반면, 본 논문에서 제안하는 경량 체크포인팅(lightweight checkpointing) 기법은 정상 수행 시 공유 메모리를 저장하지 않고 단지 비공유 메모리 페이지와 시스템 상태만을 저장한다. 고장이 발생한 경우, 고장 난 노드는 정상 수행 동안 해당 페이지를 공유했던 원격 노드로부터 페이지의 복사본을 얻고 페이지 갱신 로그, 즉 디프(diff) 로그를 적용하여 원하는 버전의 공유 메모리 페이지를 재생성 한다. 적은 양의 디프 로그를 이용하여 효율적으로 페이지를 재생성 하기 위해, 본 논문에서는 원격 로깅 상에서 XOR-디핑(XOR-diffing) 기법을 제안한다. 이는 디프 로그 생성시 갱신 전 데이터와 갱신 후의 데이터를 서로 XOR 하여 그 값을 저장하는 방법이다. 고장이 발생했을 때에는, 복사본의 버전이 재생성 하려는 버전 보다 이전일 경우 복사본에 디프 로그들을 순차적으로 XOR 하여 재생성하고, 그렇지 않은 경우 같은 디프 로그를 역순으로 적용시킴으로써 페이지를 이전 버전으로 되돌릴 수 있다.
제안하는 체크포인팅 방법은 분산 공유 메모리 시스템이 가지는 페이지 중복성을 이용하여 저장할 데이터의 크기를 줄임으로써 기존의 체크포인팅 기법들보다 정상 수행 시 더 높은 성능을 보였다. 특히, 각 노드들이 서로 다른 때에 독립적으로 체크포인팅을 할 경우 발생할 수 있는 수행 시간 불균형이 체크포인팅 시간의 감소에 따라 경감되는 효과를 보였다. 이에 따라 페이지 폴트 및 동기화 시간이 감소하였으며 최대 26% 만큼 성능이 향상하였다. 반면, XOR 연산에 의한 오버헤드는 본 체크포인팅 기법에 의한 성능 향상보다 크지 않았다.
