Mysql B-Tree Index

B-Tree 인덱스

모든 값을 순서대로 저장한다. 각 리프 페이지는 루트에서 같은 거리만큼 떨어져 있다. 속도는 트리의 depth 에 좌우된다. ( depth 를 줄이는 방법으로는 브랜치 블록 노드에 저장하는 key 값의 수를 늘리는 방법이 있다. )

• MyISAM
  • 인덱스를 작게 만드는 프리픽스 압축 기법을 사용
• InnoDB
  • 인덱스를 압축하지 않는다.
  • 기본키 값을 이용해서 인덱스된 행을 참조한다.
  • B+트리 구조를 사용한다.

B-Tree 구조

트리의 생성과정

1. 테이블 데이타 정렬
2. 정렬 결과를 리프 블록에 기록하기 시작
3. 리프 블록이 PCTFREE 에 도달하면, 브랜치 블록을 생성하고 리프 블록의 정보를 기록한다.
4. 브랜치 블록이 PCTFREE 에 도달하면, 루트블록을 생성하고 브랜치 블록의 정보를 기록하고, 새로운 브랜치 블록을 생성한다.
5. 새로운 브랜치 블록이 생길 때마다, 루트 블록에 기록한다.

트리에 인덱스 값 추가시

• PCTFREE 에 도달한 경우에는 새로운 블록을 생성하여 등록한다. 새로운 블록을 생성하였으나 더이상 해당 블록에 값이 안 들어올 경우 공간의 낭비가 발생한다.

인덱스 값 삭제시

• 트리내의 로우에 삭제 표시만 한다.

인덱스 값 갱신시

• 인덱스 삭제 과정과 삽입 과정이 순차적으로 발생한다.

PCTFREE : 인덱스 엔트리를 수용하기 위해, 각 블록에 예약된 공간의 총량

B+Tree 구조

B-Tree 와 달리 트리의 최하위 레벨의 리프 노드에만 데이타가 정렬되어 있다. ( 해당 리프 노드는 양방향 링크드 리스트를 사용하여 데이타를 저장한다. )

Kafka

실시간 Producer-Consumer 메시징 시스템으로 분산 메시징, 대용량 처리에 특화된 구조를 가지고 있다.

• 장점
  • TPS 우수, TCP 기반의 프로토콜로 성능이 우수하다.
  • 파일 시스템에 메시지 저장하여 영속성을 갖는다. 저장 시에는 제로 카피/ 순차접근 방식으로 성능을 높였다.
  • 메시지 전송 후에도 삭제하지 않고 유지하며, 일정 시간이 지난 이후에 삭제한다. 그러므로 consumer 가 메시지를 rewind 할 수 있다.
  • Consumer Pull 방식으로, consumer 의 처리 능력만큼 최대의 성능을 낼 수 있다.
• 단점
  • Exactly Once 를 보장하기 위해선, Consumer 그룹이 마지막으로 소비한 offset 을 저장하고 있어야 한다.
• 사용 사례
  • 실시간 처리
  • 웹 사이트 활동 추적
  • 로그 분석
  • 지표 수집 및 모니터링
  • spark streaming
    • 높은 처리량을 갖는 대기열로 사용 가능하다.
    • spark streaming 은 장애 복구를 위해 ‘체크 포인팅’ 을 사용하는데, Kafka DirectStream 을 사용하면 실제 데이타를 저장하지 않고, offset 만 저장하면 되므로 구조가 간결해진다.

구조

특징

• offset 을 consumer 가 직접 관리,
• 각 파티션 내에서만 메시지 순서를 보장 받을 수 있다.
• producer 가 어떻게 각 파티션으로 메시지를 분배할 지는 사용자가 정의한 분배 알고리즘에 의한다.

Spark

Spark는 빠르고 일반적인 범용 클러스터 컴퓨팅 시스템입니다. Java, Scala, Python 및 R의 고급 API와 일반 실행 그래프를 지원하는 최적화 된 엔진을 제공합니다. 또한 SQL 및 구조화 된 데이터 처리를위한 Spark SQL, 기계 학습을위한 MLlib, 그래프 처리를위한 GraphX 및 Spark Streaming을 비롯한 다양한 고급 도구 세트를 지원합니다.

• 장점
  • rdd 개념에 따라 메모리에 데이타를 투명하게 저장하기 때문에, 디스크에 대한 읽기, 쓰기 작업에 따른 시간 소비를 줄일 수 있다.
  • 다중 언어 지원
  • 지연연산(lazy evaluation) 을 사용해서 기초 데이터에 적용될 변환연산을 기억하고 있고 동작(Action) 이 실행될 때 한번에 실행되어, 최적화가 가능하다.
• 단점
  • 완전한 실시간 처리를 지원하지 않는다.
  • 자체 파일 관리 시스템이 없다. (hdfs 같은 시스템에 의존.)

구조

특징

RDD

탄력적인 분산 데이터 세트 ( Resilient Distributed Datasets ) , 스파크 마스터 / 드라이버는 RDD에 적용된 변환을 기억하므로 파티션이 손실되면 (예 : 슬레이브 머신이 다운 된 경우) 해당 파티션을 클러스터의 다른 머신에서 쉽게 재구성 할 수 있다.

• 여러 분산 노드에 걸쳐서 저장되는 변경 불가능한 데이타의 집합
  • 불변성으로 인해, 프로세스간의 공유 및 복구 문제를 해결한다.
• 각 RDD 는 클러스터 각 노드들에서 연산 가능하도록 여러개의 파티션으로 나뉜다.
  • RDD의 모든 데이터 세트는 여러 서버에 논리적으로 분할되어 클러스터의 다른 노드에서 계산할 수 있습니다
• RDD 는 트랜스포메이션, 액션이라는 2가지 타입의 연산을 갖는다.
• 액션이 실행될 때는 lazy 연산으로 동작한다.

DATAFRAME

• 컬럼이 존재하는 분산 컬렉션
• 구조화 된 테이터 처리를 위한 기능을 제공한다.
  • sql 등을 사용하여 데이터를 join 하고, 추출 가능하다.
• RDD 에 비해 2가지의 장점을 가지고 있다.
  • 사용자 정의 메모리 관리
  • 최적화된 실행 계획
    • 내부적인 동작 방식에는 Catalyst Optimizer를 통해 실행 시점에 최적화된 코드를 제공하고 있어 RDD 프로그래밍과 달리 언어(Scala, Java, Pytho, R)에 상관없이 동일한 성능을 보장한다.

DATASET

• 2.0 부터 DdtaFrame API 가 Dataset 으로 합쳐지게 되었다.
• 인코더를 사용하여, 비구조화, 구조화된 데이타를 모두 다룰 수 있다.
• JVM객체에 대한 바인딩으로 Encoder를 사용하여 유형별 JVM객체를 Tungsten의 내부 메모리 표현으로 매핑하게 된다. 결과적으로 Encoder를 통해 JVM객체를 효율적으로 직렬화/비직렬화 할 수 있으며 소형의 바이트 코드를 생성하게 됨으로 이는 cache size 축소 및 처리시간 관련 성능상 이점을 가질 수 있다.
• 데이터를 off-heap storage에 binary 형태로 시리얼라이즈 하며 여러 트랜스포메이션을 off-heap 메모리상에서 직접 가능하도록 설계되어있다. (스파크에 내장된 엔코더는 off-heap data 와 de-serialize 없이 바로 인터렉트 가능한 바이트코드를 생성할 수 있다)

드라이버

• 사용자의 main() 메서드를 실행한다.
• DAG 논리 그래프를 물리적인 실행 계획으로 변환한다.
• 실행 그래프를 여러 stage 로 분리하며, 각 stage 는 여러 개의 task 로 구분된다. 각 task 들을 각 클러스터로 전송된다.

익스큐터

• 시작되면, 드라이버에 등록된다.
• 각 익스큐터는 task 를 실행하고 RDD 데이타를 저장한다.
• 사용자 프로그램에서 캐쉬하는 RDD 를 저장한다.

공유 변수

• 어큐뮬레이터
  • 쓰기 전용 변수,
  • 캐쉬되어 있던 RDD 가 삭제되어, 재 연산이 수행된다면 중복 연산이 발생할 수 있다.
• 브로드캐스트
  • 크기가 큰, 읽기 전용의 값을 모든 작업 노드에 전송하기 위하여 사용된다.

성능 고려 사항

• 병렬화 수준을 알맞게 조정
• 성능을 위해 직렬화 라이브러리 사용 가능 ( kyro )
• 메모리 관리
• 하드웨어 프로비저닝

Mutex,Semaphore

Mutex

한번에 한 스레드만 특정 락을 소유할 수 있다. 대표적으로 synchronized 가 상호배제 락의 개념을 가지고 있다.

Semaphore

리소스에 액세스할 수 있는 스레드의 갯수를 제한. 갯수가 1개인 경우 binary semaphore, 2개 이상인 경우 counting semaphore 라고 부른다. binary semaphore 의 경우, mutex 와 개념이 같다.

JVM 구조

JVM, JRE, JDK

• JVM
  • 자바 소스 코드로 부터 만들어지는 바이너리 코드 파일(.class)을 클래스 로더로 부터 읽어들여 실행한다.
• JRE
  • JVM 의 실행환경을 구현하기 위해 자바 API 와 JVM 으로 구성되어 있다.
• JDK
  • 자바 개발도구 이며, JRE, javac, java 등을 포함한다.

Hotspot JVM 아키텍쳐

클래스 로더

자바는 런타임에 클래스를 처음으로 참조할 때, 해당 클래스를 로드하고 링크한다.

• 클래스 로드 순서

• Bootstrap Class Loader
  • JVM이 시작되면, 부트스트랩(bootstrap) 클래스로더를 생성하고, 그 다음에 가장 첫번째 클래스인 Object를 비롯해 자바 API 를 로드한다.
• Extension Class Loader
  • 다양한 보안 확장 기능 같은 확장 클래스들을 로드한다. ( jre/lib/ext 등 )
• System Class Loader
  • 사용자가 지정한 $classpath 내의 클래스를 로드한다.
• User-Defined Class Loader
  • 애플리케이션 사용자가 직접 코드 상에서 생성해서 사용하는 클래스 로더이다.

런타임 데이터 영역

PC Register, JVM Stack, Native Method Stack 는 스레드마다 생성되며, 힙, 메서드 영역, 런타임 상수 풀은 모든 스레드가 공유해서 사용한다.

• Program Counter Register
  • 스레드마다 생성되며, 현재 실행 중인 JVM 명령의 주소가 저장된다.
• JVM 스택
  • 스레드마다 생성되며, 메서드가 실행될 때 마다 하나의 스택프레임을 생성되는데, 해당 스택 프레임을 저장하기 위한 장소이다.
    • 스택 프레임
      • 각 스택 프레임은 지역변수 배열, 피연산자 스택, 런타임 상수풀에 대한 레퍼런스를 가진다.
        • 지역변수 배열
          • 0 부터 시작하는 인덱스를 가진 배열이다. 0은 메서드가 속한 클래스 인스턴스의 this 레퍼런스이고, 1부터는 메서드에 전달된 파라미터가 저장되며, 이후부터는 메서드의 지역 변수가 저장된다.
        • 피연산자 스택
          • 메서드의 실제 작업 공간이다. 각 메서드는 피연산자 스택과 지역 변수 배열 사이에서 데이타를 교환하고, 호출 결과를 추가하거나 꺼낸다.
        • 상수풀 참조
• 네이티브 메서드 스택
  • 자바 이외의 언어로 작성된 네이티브 코드를 위한 스택이다.
• 메서드 영역
  • 모든 스레드가 공유하는 영역이며, JVM 이 시작될 때 생성된다. 각 클래스와 인터페이스에 대한 런타임 상수풀, 필드와 메서드 정보, 스태틱 변수, 메서드의 바이트 코드 등을 보관한다. 흔히 Permanent Area ( PermGen ) 이라고 한다.

    자바 8 에서는 Perm 영역이 사라지고 metaspace 로 변경되었으며, 스태틱 변수는 heap 으로 이동되었다. Metaspace 는 heap 공간을 사용하지 않으며, native 메모리 영역을 사용한다. MaxMetaspaceSize 에 도달하면 GC 가 시작된다.

• 런타임 상수풀

  intern 된 스트링(string’s pool)은 heap 에 저장된다.

  • 각 클래스와 인스턴스의 상수 뿐만이 아니라, 메서드와 필드에 대한 모든 레퍼런스를 담고 있다. 즉 어떤 메서드나 필드를 참조할 대, JVM 은 런타임 상수 풀을 통해 해당 메서드나 필드의 실제 물리적인 메모리 상의 주소를 찾아내서 참조하기 위해 사용한다.
• 힙
  • 인스턴스 또는 객체를 저장하는 공간이다.

실행엔진

JIT 컴파일러

자바의 성능을 개선하기 위해 JIT 컴파일러를 만들었고, 이름을 HotSpot 으로 지었다. JIT 컴파일러는 프로그램의 성능에 영향을 주는 지점에 대해서 ‘바이트 코드를 컴파일하고 실행 가능한 네이티브 코드로 변환’ 한다.