poeun 🔅

Original Artwork © Henri Matisse (1869 ~ 1954), Le Cheval L’Ecuyere et le Clown, 1947, 64.6 x 42.5, Centre Georges-Pompidou

개인 저장공간입니다.
도움이 되길 바랍니다.
Since 2021.10

4 분 소요

image

“Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing” 논문을 개인 공부 및 리뷰를 위해 쓴 글입니다.

Contents
1. Introduction
2. Resilient Distributed Datasets
3. Spark Programming Interface
4. Representing RDDs
5. Implementation
6. Evaluation
7. Discussion

논문 출처 : NSDI 12 paper - RDDs




4. Representing RDDs

  • RDD는 광범위한 변환에 걸쳐 계보(lineage)를 추적할 수 있는 RDD의 표현(representation)을 선택한다.
  • RDD를 구현하는 시스템은 가능한 풍부한 변환 연산자 집합을 제공해야 하며 사용자가 임의적인 방법으로 변환 연산자를 구성할 수 있어야 한다.
  • 저자들은 이러한 목표를 용이하게 하는 RDD에 대한 간단한 그래프 기반 표현을 제안한다.
    • spark에서 이 표현을 사용하여 각각의 스케줄러에 특별한 논리를 추가하지 않고 광범위한 변환을 지원하여 시스템 설계를 크게 단순화했다.
      1. 파티션 집합
      2. 부모 RDD에 대한 종속성(dependency) 집합
      3. 부모 RDD에 대한 데이터 집합을 계산하는 기능
      4. 스키마 및 데이터 배치의 파티셔닝에 관한 메타데이터


image

  • 다음으로 RDD 간의 종속성을 어떻게 표현하느냐이다.
  • 저자들은 종속성을 2가지 유형으로 분류했다.
  • 부모 RDD의 각 파티션이 자녀 RDD의 최대 한 파티션에 의해 사용되는 좁은 종속성(narrow dependency)과 여러 자녀 파티션이 종속될 수 있는 넓은 종속성(wide dependency)이다.
    • 좁은 종속성(narrow dependency) : 부모 RDD 파티션이 자식 RDD 파티션과 최대 1:1로 대응된다. 1
      • Shuffling이 거의 발생하지 않으며, 빠르다.
    • 넓은 종속성(wide dependency) : 부모 RDD 파티션이 자식 RDD 파티션과 N:1로 대응된다. 1
      • Shuffling이 많은 데이터에 발생하며, 느리다.
      • 임의의 데이터만으로 실행할 수는 없으며, 특별한 방법, 예를 들면 키의 값에 따라 파티셔닝된 데이터를 요구한다. 2
      • 결국 키의 재분포, 즉 셔플이 필요하다.
    • 사전에 작업된 RDD를 부모 RDD, 이를 바탕으로 작업된 RDD로 정의하며, 자식 RDD를 만들게한 mpa 메소드를 종속성(dependency)이라 한다. 1

image

  • 이같은 구별은 2가지 이유로 유용하다.
  1. 좁은 종속성은 모든 부모 파티션을 계산할 수 있는 하나의 클러스터 노드에서 파이프라인을 실행할 수 있다.
    • 요소별로 맵 다음에 필터를 적용할 수 있다.
    • 반면 넓은 종속성을 위해서는 모든 부모 파티션의 데이터를 사용할 수 있어야 하며 맵리듀스와 같은 작업을 사용하여 노드 간에 서로 섞어야(shuffled) 한다.

  2. 노드 장애 후 복구는 손실된 부모 파티션만 재계산하면 되고 서로 다른 노드에서 병렬로 재계산할 수 있기 때문에 좁은 종속성으로 더 효율적으로 대처할 수 있다.

    • 반면 넓은 종속성의 계보 그래프에서, 하나의 실패한 노드는 RDD의 모든 부모로부터 일부 파티션이 손실되어 완전한 재실행이 필요할 수 있다.
    • RDD를 위한 이 공통 인터페이스는 스파크의 대부분의 변환을 20줄 미만의 코드로 구현가능하다.


  • 아래는 여러 RDD 구현이 요약된 것이다.
  • HDFS files
    • RDD가 HDFS의 파일일 경우, 파티션은 파일의 각 블록에 대해 하나의 파티션(partition)을 반환하고, 기본 설정 위치는 블록이 있는 노드를 제공하며, 반복자(iterator)는 블록을 읽는다.(read)
  • map
    • 임의의 RDD에서 맵을 호출하면 MappedRDD 개체가 반환된다.
    • 이 개체는 부모와 동일한 파티션과 기본 위치를 가지지만 반복자 메서드에서 부모 레코드에 매핑하기 위해 전달된 함수를 적용한다.
  • union
    • 두 개의 RDD에서 union을 호출하면 파티션이 부모의 파티션이 union인 RDD가 반환된다.
    • 각 자식 파티션은 해당 부모에 대한 좁은 종속성을 통해 계산된다.
  • join
    • 2개의 RDD를 결합하면 2개의 좁은 종속성, 2개의 넓은 종속성 또는 혼합이 발생할 수 있다.
      • 좁은 종속성 : 해시(hash)/범위(range)가 모두 동일한 파티션으로 분할될 경우



5. Implementation

  • 각 스파크 프로그램은 자체 드라이버(마스터)와 워커가 있는 별도의 메소스(Mesos) 애플리케이션으로 실행되며, 이들 애플리케이션 간의 리소스 공유는 메소스가 담당한다.
    • Mesos : 데이터 센터에서 리소스를 동적으로 할당하는 것을 목표로 하는 distributed kernel이고 리소스 공유 기능을 사용하는 수많은 프레임워크를 제공한다. 3


5.1 Job Scheduling

image

  • 사용자가 RDD에서 액션(ex. count or save)을 실행할 때마다 스케줄러는 Figure 5와 같이 실행할 단계의 DAG를 구축하기 위해 해당 RDD의 계보 그래프를 검사한다.

    • 방향성 비순환 그래프(DAG; Directed Acyclic Graph) : 개별 요소들이 특정한 방향을 향하고 있으며, 서로 순환하지 않는 구조로 짜여진 그래프 4

      image
      이미지출처 5

  • 단계(stage)들의 경계는 넓은 종속성에 필요한 셔플 연산 또는 부모 RDD의 계산을 단락(short-circuit)시킬 수 있는 “이미” 계산된 파티션이다.
  • 그런 다음 스케줄러는 타겟 RDD를 계산할 때까지 각 단계에서 누락된(missing) 파티션을 계산하는 태스크를 시작한다.
  • 스케줄러는 지연 스케줄링(delay scheduling)을 사용하여 데이터 인접성(locality)을 기반으로 기계에 작업을 할당한다.
  • 스파크의 모든 계산은 현재 드라이버 프로그램에서 호출된 액션에 응답하여 실행된다.


5.2 Interpreter Integration

  • 스칼라(scala) 인터프리터는 일반적으로 사용자가 일력한 각 라인에 대한 클래스를 컴파일하여 JVM에 적재하고 함수를 호출하는 방식으로 동작한다.
  • 이 클래스는 해당 라인의 변수나 함수를 포함하고 초기화 방법으로 라인의 코드를 실행하는 싱글톤(singleton) 객체를 포함한다.
    • 싱글톤 패턴(Singleton Pattern) : 객체의 인스턴스가 오직 1개만 생성되는 패턴을 의미한다.


image

  • 스파크에서 인터프리터를 2가지 변경했다.
  1. 클래스 배송(Class shipping) : 워커 노드가 각 라인에 생성된 클래스에 대한 바이트 코드를 가져올수 있도록 인터프리터가 HTTP를 통해 이러한 클래스를 서비스하도록 했다.
  2. 수정된 코드 생성(Modified code generation) : 일반적으로 코드의 각 라인에 대해 생성된 싱글톤 객체는 해당 클래스의 정적 메서드를 통해 접근한다.


5.3 Memory Management

  • 스파크는 persistent RDD를 저장하기 위한 3가지 옵션(option)을 제공한다.
    • 직렬화(serialization) : 객체를 직렬화하여 네트워크 상으로 전송 가능한 형태로 만드는 것을 의미한다. 객체들의 데이터를 연속적인 데이터로 변형하여 stream을 통해 데이터를 읽도록 한다. 6
      • 객체들을 통째로 파일로 저장하거나 전송하고 싶을 때 주로 사용된다.
    • 역직렬화(deserialization) : 직렬화된 파일 등을 역으로 직렬화하여 다시 객체의 형태로 만드는 것을 의미한다. 6
      • 저장된 파일 읽거나 전송된 스트림 데이터를 읽어 원래 객체의 형태로 복원한다.

      image
      이미지출처 6

  1. 역직렬화된(deserialized) 자바 객체로서의 인메모리(in-memory) 스토리지
    • 인메모리 데이터베이스(in-memory database) : 데이터 스토리지의 메인 메모리에 설치되어 운영되는 방식의 데이터베이스 관리 시스템 7
      • 인메모리 방식은 메모리상에 색인을 넣어 필요한 모든 정보를 메모리상의 색인을 통해 빠르게 검색할 수 있다.
  2. 직렬화된(serialized) 데이터로서의 인메모리 스토리지
  3. 디스크 상의 스토리지
  • 첫 번째 옵션은 JVM이 기본적으로 각 RDD 요소에 액세스할 수 있기 때문에 가장 빠른 성능을 제공한다.
  • 두 번째 옵션은 공간(space)이 제한될 때 성능 저하를 감수하고 자바 객체 그래프보다 메모리 효율적인 표현을 선택할 수 있도록 한다.
  • 세 번째 옵션은 RAM에 보관하기에는 너무 크지만 매번 사용할 때마다 재계산하는 데 비용이 많이 드는 RDD에 유용하다.
  • 사용 가능한 제한된 메모리를 관리하기 위해 RDD 수준의 LRU(Least Recently Used) 제거 정책을 사용한다.
    • LRU(Least Recently Used) : 가장 오랫동안 참조되지 않은 페이지를 교체하는 방식


5.4 Support for Checkpointing

  • 장애(failure)가 발생한 후 RDD를 복구(recovery)하는 데 항상 계보(lineage)를 사용할 수 있지만, 긴 계보 체인을 가진 RDD의 경우 이런 복구는 시간이 많이 걸릴 수 있다.
  • 따라서 일부 RDD를 안정적인 스토리지로 체크포인트하는 것이 도움이 될 수 있다.
  • 스파크는 현재 체크포인트를 위한 API를 제공하지만, 체크포인트할 데이터의 결정은 사용자에게 맡긴다.
    • 좁은 종속성과 넓은 종속성에 따라 계산 차이가 다르다.



6. Evaluation

  • 결과는 다음과 같다.
    • 스파크는 반복적인 기계 학습 및 그래프 애플리케이션에서 하둡을 최대 20배 능가한다.
      • 데이터를 자바 객체로 메모리에 저장함으로써 입출력 및 역직렬화 비용을 피할 수 있기 때문에 속도가 향상된다.
    • 사용자가 작성한 애플리케이션은 성능과 확장성이 뛰어나다.
    • 노드에 장애가 발생하면 스파크는 손실된 RDD 파티션만 재구성하여 신속하게 복구할 수 있다.
    • 스파크는 1TB 데이터 세트를 5-7초의 지연시간(latency)으로 대화식(interactively)으로 쿼리하는 데 사용할 수 있다.


6.1 Iterative Machine Learning Applications

image

  • RDD를 통해 데이터를 공유하면 향후 반복 속도가 크게 빨라진다는 것을 알 수 있다.
  • 하둡은 여러 요인으로 인해 여전히 속도가 느렸다.
  1. 하둡 소프트웨어 스택(stack)의 최소 오버헤드
    • 스택(stack) : 제한적으로 접근할 수 있는 나열 구조 [7]
    • 잡 설정, 작업 시작, 정리 등의 등의 최소 요구 사항을 완료하는 데 최소 25초 이상의 오버헤드가 발생했다.
  2. 데이터를 서빙할 때 HDFS의 오버헤드
    • HDFS는 각 블록에 서비스를 제공하기 위해 여러 개의 메모리 복사본과 체크섬을 수행했다.
  3. 이진 레코드를 사용 가능한 메모리 내 자바 객체로 변환하기 위한 역직렬화 비용

image

  • RDD 요소를 메모리에 자바 객체로 직접 저장함으로써 스파크는 이러한 모든 오버헤드를 피할 수 있다.


6.2 PageRank

image


6.3 Fault Recovery

  • 체크포인트 기반 장애 복구 메커니즘을 사용하는 경우 복구는 체크포인트 빈도에 따라 최소 여러 번 반복을 재실행해야 할 수 있다.
  • 게다가, 시스템은 100GB의 작업 세트(이진수로 변환된 텍스트 입력 데이터)를 네트워크를 통해 복제해야 하며, RAM에 복제하기 위해 스파크의 두 배 메모리를 사용하거나 디스크에 100GB를 쓰기 위해 기다려야 한다.
  • 하지만 RDD에 대한 계보(lineage) 그래프는 모두 크기가 10KB 미만이었다.





References

  1. Spark - RDD Dependency by 물통꿀꿀이 ↩ ↩2 ↩3

  2. [ Spark ] 스파크 넓은 종속성(narrow dependency) vs 좁은 종속성(wide dependency) - 행복한디벨로퍼 ↩

  3. Kubernetes vs Mesos with Marathon (기술적 관점) - 주길재 ↩

  4. 해시넷 - 방향성 비순환 그래프 ↩

  5. wide vs narrow dependencies - rowl1ng ↩

  6. 직렬화(Serialization)와 역직렬화(Deserialization) - 하나스타 ↩ ↩2 ↩3

  7. 위키백과 - 인메모리 데이터베이스 ↩

댓글남기기

참고