Apache Spark RDDs(Resilient Distributed Datasets)의 이점과 특징 (feat. DSM)

아파치 스파크의 중심에는 데이터 모델인 Resilient Distributed Datasets (RDDs)가 존재합니다. 스파크 연구의 연혁을 살펴보더라도 핵심인 RDDs에 대한 설계 및 구현이 끝난 이후(2012년 4월, [1]) 폭발적으로 다양한 모듈이 이 RDDs에 기반하여 추가되는 것을 알 수 있습니다. 

 

이번 글에서는 RDDs를 중심으로 아래와 같은 부분들을 알아보고자 합니다:

 

• RDDs의 기원인 DSM
• RDDs는 어떻게 다르며, 어떤 이점을 가지는가?
• RDDs의 주요 특징

 

---

RDDs의 기원인 DSM

RDDs를 알아보기 전에, 80년대부터 활발하게 연구되었으며 RDDs와 유사하게 물리적으로 여러 노드에 존재하는 메모리를 공유하여 추상화를 제공하는 Distributed share memory (DSM)를 먼저 알아보겠습니다. 

 

 

DSM

Distributed shared-memory systems implement the shared-memory abstraction on multicomputer architectures, combining the scalability of network-based architectures with the convenience of shared-memory programming.
[2].

 

DSM은 위와 같이 여러 노드에 존재하는 메모리를 공유메모리 추상화 레이어를 제공합니다. 

Distributed shared memory - Image from [2]

Distributed shared memory - Image from [3]

이러한 DSM은 멀티프로세스 하드웨어에서 메모리 접근이 병목이 되는 한계점을 극복할 수 있게 해줍니다. 초기의 DSM의 프로그래밍 모델은 간단한 메시지-passing 패러다임에 국한되었지만, 점점 고도화되며 기존의 하나의 노드에 존재하던 메모리와 같은 추상화 레이어를 제공해주었습니다. 

 

DSM 시스템은 아래와 같은 3가지 방법(또는 한 가지 이상의 조합을 통해)을 사용하여 구현됩니다:

 

• 전통적인 캐싱 기술을 확장성 있는 아키텍쳐로 확장하는 하드웨어 구현
• 가상 메모리 관리 메커니즘을 통해 공유와 coherence를 가능케하는 운영체제와 라이브러리 구현
• 공유된 접근이 자동적으로 동기화와 coherence로 변환되는 컴파일러 구현

 

DSM 디자인의 요소

DSM 시스템 디자인 시에는 구조, granularity, 접근, 일관성, 확장성, heterogeneity와 같은 부분과 관련한 선택을 진행하여야 합니다. 이러한 각 요소들에서 어떠한 옵션이 있는지 살펴보며, 기술적 결정의 trade-off를 명확히 이해할 수 있습니다.

 

• 구조(Structure)와 Granularity

구조와 granularity는 깊게 연관되어 있습니다.

 

구조는 메모리 상에서 공유 데이터의 모양을 말합니다. 대부분의 DSM 시스템은 메모리를 구조화하지 않지만, 몇몇은 데이터를 객체, 특정 언어의 타입 등으로 정형화하기도 합니다. 

 

granularity는 공유 단위의 크기를 말합니다. 바이트, word, 페이지, 복잡한 데이터 구조 등이 이에 해당됩니다. 

 

소프트웨어 기반의 DSM 시스템은 1 KB 단위의 페이지로 공유하거나, 하드웨어의 가상 메모리 기반으로 구현된 경우 하드웨어 페이지 사이즈 몇 개를 합쳐 DSM 상의 공유 단위로 편리하게 사용할 수 있습니다. 하드웨어 기반의 DSM 구현은 보통 16, 32 바이트, 32 비트와 같이 좀 더 작은 grain size를 제공합니다.

 

공유 메모리 프로그램은 참조 locality를 제공하기에, 하나의 프로세스는 짧은 시간 안에 공유 address space의 넓은 영역에 접근합니다. 그러므로, 페이지 사이즈가 클수록 페이징 오버헤드를 줄일 수 있습니다. 그러나, 공유는 경쟁을 발생시키기에, 페이지 사이즈가 클수록 하나 이상의 프로세스가 같은 페이지에 접근하려고 할 가능성이 높아지게 됩니다. 그리고 페이지의 사이즈가 작을 수록 다른 값이 같은 페이지에 위치하게 되는, false sharing의 가능성이 낮아지게 됩니다. 또한, 페이지가 클수록 페이지에 대한 정보를 저장하는 directory information 크기가 작을 수 있습니다. 

 

공유 메모리를 정형화하는 방식에는 데이터 타입을 통한 방법이 있습니다. 공유 메모리는 분산 object-oriented 시스템에서 객체로 정형화 되게 됩니다. 이러한 방식의 시스템에서 객체의 크기는 애플리케이션마다 큰 차이를 보이기에 grain 사이즈가 애플리케이션에 따라 다릅니다.

 

공유 메모리 정형화의 또 다른 방식으로는 데이터베이스와 같이 관계형 메모리인 tuple space로 저장하는 형태가 있습니다. 데이터의 위치가 값과 분리되게 하여, 사용자는 특정한 API를 통해 공유 메모리 space와 커뮤니케이션할 수 있습니다. 

 

 

• Coherence Semantics

DSM을 적절하게 사용하기 위해서, 사용자는 DSM 상에서 병렬 메모리 업데이트가 어떻게 시스템으로 전파되는지 이해하고 있어야 합니다. 여러 단계의 일관성이 '엄격한 정도'에 따라 아래와 같은 순서로 존재할 수 있습니다:

 

Definitions of memory coherence, stricter to weaker - Image from [2]

 

일관성과 관련해 일관성을 어렵게 만드나 여러 이점을 가진 복제가 존재합니다. 복제는 1) 읽기 복제, 2) 쓰기 복제 가 존재하며, 일반적으로 네트워크 트래픽 감소, 병렬성 증진, 낮은 페이지 faults 등의 이점을 제공합니다. 

 

• 확장성

DSM의 이론적인 이점은 메모리와 멀티프로세스가 강하게 결합된 형태보다 더 쉽게 확장가능하다는 점입니다. 확정성은 중심 병목 지점(메모리-멀티프로세스 강결합의 버스 등)과 글로벌 연산과 스토리지(노드의 수에 따라 증가하는 브로드캐스트 메시지, full directories 등)에 영향을 받습니다. 

 

1990년대 대부분 DSM은 이더넷 기반으로 그러한 네트워크 병목으로 인해 최대 100 노드를 지원할 수 있었습니다. 

 

• Heterogeneity

얼핏보면 다른 하드웨어 아키텍쳐를 지닌 노드 간에 기반해 공유 메모리를 구성하는 것은 불가능해 보이나, DSM이 정형방식어서 메모리가 소스코드 상의 객체나 변수로 이뤄져 있다면 좀 더 쉽게 구성할 수 있습니다. 이러한 경우 DSM 컴파일러는 공유 메모리 접근 시에 변환을 추가하게 됩니다. Heterogeneous DSM은 더 많은 노드를 클러스터에 포함시킬 수 있으나, 이점보다 변환의 비용이 더욱 커서 잘 사용되지 않았습니다. 

 

 

DSM의 구현

DSM은 1) 하드웨어의 캐시 coherence circuits이나 네트워크 인터페이스 등을 통해서, 2) 소프트웨어 적으로 이룰 수 있습니다. 소프트웨어적으로 구현한 형태는 크게 아래와 같은 3가지가 존재합니다:

 

• 시스템의 가상 메모리를 사용한 페이지 기반
• 공유 변수에 접근하기 위한 몇 가지 방식을 사용한 공유 변수 기반
• 객체지향 관점을 통한 객체 기반

 

RDDs는 어떻게 다르며, 어떤 이점을 가지는가?

RDDs 디자인의 주요 해결과제는 아래와 같은 문장에 잘 나타나 있습니다:

 

How to design a distributed memory abstraction that is both fault-tolerant and efficient? [4]

 

기존의 스토리지 추상화 도구들을 fine-grained 업데이트에 기반한 인터페이스를 제공하였습니다. 하지만 이러한 시스템들은 데이터와 로그를 여러 노드에 복제하여 fault-tolerance를 만족하였는데, 데이터 인텐시브한 앱에서는 매우 많은 비용이 소모되며 메모리 write과 비교해 10 ~ 100배 느렸습니다. 

 

RDDs는 이러한 문제를 해결하기 위해서 아래와 같은 부분을 중심으로 구현되었습니다:

 

• 제한된 형태의 DSM: Immutable하고, partitioned된 형태의 레코드 콜렉션으로 이뤄져 있습니다. RDDs의 생성은 coase-grained deterministic transformation(map, filter, join 등)을 통해서만 생성될 수 있습니다.
• 리니지를 사용한 효율적인 fault-recovery: 여러 요소들에 적용하기 위한 하나의 연산만 로그를 남기고, 실패 시에 잃어버린 파티션을 재컴퓨팅하게 됩니다. 실패가 없다면, 어떠한 리커버리 비용도 들지 않습니다. 

 

아래의 tradeoff 그래프를 살펴보며 다른 프레임워크와 비교해 보면, RDDs의 타겟지점을 더욱 명확히 알 수 있습니다. 

Tradeoff space - Image from [4]

 

기존 DSM 시스템과의 비교

RDDs는 기존의 DSM 시스템과 같이 분산된(여러 노드에) 메모리에 대한 추상화 레이어를 제공합니다. 아래에서는 이러한 '기존 DSM'에 Piccolo [5]와 같이 공유된 분산해쉬테이블(DHT), 분산데이터베이스도 포함하는데요. 

 

기존의 DSM에서 어떤 부분이 특화되어 RDDs가 개발되었는지, 그렇기에 어떠한 장점으로 위의 문제해결 요구사항을 만족시켰는지 알아보겠습니다. 

 

측면	RDDs	DSM
Reads	Coarse- or fine-grained	Fine-grained
Writes	Coarse-grained	Fine-grained
Consistency	Trivial (immutable)	앱 또는 런타임에 따라
Fault recovery	리니지를 사용하여 fine-grained하며 오버헤드가 낮음	체크포인트와 프로그램 롤백 필요
Straggler mitigation	백업 타스크를 통해 가능	어려움
Work placement	데이터 로컬리티 기반 자동	앱에 따라
Behavior if not enough RAM	기존 데이터 flow 시스템(MapReduce 등)과 유사	낮은 성능

 

RSSs와 DSM의 주요한 차이는 RDDs는 오직 coarse-grained transformation을 통해서만 생성될 수 있는 반면 DSM은 각 메모리 위치에 읽기와 쓰기를 허용한다는 점입니다. 이점은 RDDs를 bulk writes를 진행하는 애플리케이션에만 사용되도록 제한하지만 더욱 효율적인 fault-tolerance를 가능하게 합니다. 특히, RDDs는 리니지를 사용하여 회복되기에, 체크포인팅에 필요한 오버헤드를 가지지 않습니다. 더욱이, 실패 시에 전체 프로그램을 롤백할 필요 없이 RDD 중 잃어버린 파티션만 재컴퓨팅되면 되고 다른 노드에서 병렬적으로 재컴퓨팅될 수 있습니다. 

 

RDDs의 두 번째 이점은 immutable한 특성이 느린 작업에 대한 백업 복제 task를 수행하여 느린 노드(stragglers)의 영향을 낮춘다는 점입니다. 이러한 백업 tasks의 경우 DSM에서는 하나의 task에 대한 2가지 복제본이 같은 메모리 위치에 접근하고 서로의 업데이트를 방해한다는 점 때문에 구현하기가 매우 어렵습니다.

 

세번째로, RDDs 상에서 bulk 연산 시에 런타임은 성능 개선을 위해 데이터 로컬리티에 기반해 tasks를 분배할 수 있습니다. 

 

마지막으로 RDDs는 스캔 기반의 연산에 사용되는한 RDDs를 저장할 메모리가 충분하지 않을 때 graceful하게 중단될 수 있습니다. RAM에 다 들어갈 수 없는 파티션의 경우 디스크에 저장될 수 있고, 그러한 상황에서도 다른 분산 처리 엔진(e.g. MapReduce 등)과 유사한 성능을 가능하게 합니다.

 

 

RDDs의 주요 특징

• Distributed data abstraction
• Resilient & Immutable
• Compile-time Type-safe
• Unstructured/Structured Data: Text
• Lazy

 

 

 

Reference

[1] Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing
[2] Distributed shared memory: a survey of issues and algorithms

[3] https://en.wikipedia.org/wiki/Distributed_shared_memory

[4] https://www.usenix.org/sites/default/files/conference/protected-files/nsdi_zaharia.pdf

[5] Piccolo: Building Fast, Distributed Programs with Partitioned Tables

[6] https://www.youtube.com/watch?v=Ofk7G3GD9jk