CS 5일차

• Heap
• Merge Sort
• DNS round robin
• 프로세스 주소 공간
• DB - 인덱스
• JVM

Heap

• 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리 자료 구조이다.
• 완전 이진 트리이기 때문에 배열을 이용하여 손쉽게 구현할 수 있다.
• max - heap은 부모가 자식보다 항상 큰 자료구조이고, min - heap 은 부모가 항상 자식보다 작은 자료 구조이다.
• 이를 응용하여 우선 순위 큐를 구현할 수 있다.
• 새로운 원소가 삽입 될 때나 root 원소를 추출하고 나서 heap 규칙을 따르도록 원소의 위치를 바꾸는 과정을
  heapify 라 불리며 log n 이 소요 된다.
• 새로운 원소는 항상 힙 구조의 제일 끝 원소로 추가되며 heapify 과정을 통해 자신의 자리를 찾아 올라가고,
  root 값인 min, max 값을 뽑고서는 제일 끝 원소를 root으로 옮기고 heapify를 진행하며 내려간다.
• BST 와 다르게 노드가 같은 레벨이어도 크기를 알 수 없다. 단지 부모보다 큰지 작은지만을 따져서 위치가 정해지기 때문인다.
• max-heap 구조일 때, heapify 함수는 다음과 같다.

void heapify(int arr[], int idx, int heapSize){
    int nextIdx = idx*2;
    if(nextIdx > heapSize){
        return;
    }
    if(nextIdx + 1 <= heapSize){
        if(arr[nextIdx] < arr[nextIdx+1]){
            nextIdx += 1;
        }
    }
 
    if(arr[nextIdx] > arr[idx]){
        int tmp = arr[idx];
        arr[idx] = arr[nextIdx];
        arr[nextIdx] = tmp;
 
        heapify(arr, nextIdx, heapSize);
    }
}

 

Merge Sort

void merge(int arr[], int left, int mid, int right){
    int i = left;
    int j = mid+1;
    int idx = left;
 
    while(i <= mid && j <= right){
        if(arr[i] < arr[j]){
            outPlace[idx] = arr[i];
            ++idx;
            ++i;
        }else{
            outPlace[idx] = arr[j];
            ++idx;
            ++j;
        }
    }
 
    if(i > mid){
        while(j <= right){
            outPlace[idx] = arr[j];
            ++idx;
            ++j;
        }
    }else{
        while(i <= mid){
            outPlace[idx] = arr[i];
            ++idx;
            ++i;
        }
    }
 
    idx = left;
    while(idx <= right){
        arr[idx] = outPlace[idx];
        ++idx;
    }
}
 
void mergeSort(int arr[], int left, int right){
    if(left < right){
        int mid = (left + right) / 2;
 
        mergeSort(arr, left, mid);
        mergeSort(arr, mid+1, right);
        merge(arr, left, mid, right);
    }
}

• 머지 소트는 분할 정복 방식의 O(n logn) 속도를 지닌 빠른 정렬 기법이다.
• 퀵정렬에 비해 다소 느리지만, 퀵정렬과 다르게 항상 n log n 의 시간복잡도를 지니는 장점이 있다.
• merge 함수는 n 시간이 소요되며, 이때 새로운 배열에 기존 요소들을 정렬하며 담고, 마지막에 원래 배열로 복사가 이루어진다.
• 따라서 시간 복잡도에 비해 메모리 지역성이 다소 떨어지고 추가 메모리 공간이 필요하다.
• mergeSort 함수는 배열을 계속해서 반으로 나누는 분할 과정이고 log n 시간이 소요된다.
• 앞 서 언급한대로 추가 배열이 필요하기 때문에 2n 만큼이지만 빅오 표기법상 O(n)이라 할 수 있다.
• 이를 응용하면, 외부 병합 정렬을 이용할 수 있다.
• out of place 기법이다. ( in place로도 할 수는 있다고 한다. )

Round Robin DNS

• 라운드 로빈 DNS는 별도의 소프트웨어 혹은 하드웨어 로드밸런싱 장비를 사용하지 않고,
  DNS만을 이용하여 도메일 정보를 조회하는 시점에서 트래픽을 분산하는 기법이다.
• 여러 서버로 구성된 웹서버에 접속을 원하는 사용자가 주소창에 도메인 주소를 입력하면,
  DNS는 도메인 정보를 조회하고 얻은 여러 서버의 공인 IP 리스트 중에서 라운드 로빈 형태로 랜던하게 제공한다.
• 이를 통해 해당 웹서버에 접속하려는 다수의 사용자는 복수의 서버에 나뉘어 접속하게 되어 자연스럽게 서버의 부하가 분산된다.
• 지리적으로 복수의 웹서버가 멀리 떨어져 실시간으로 헬스 체크가 어려운 경우나 예산이 적은 경우에 사용된다.
• 치명적인 단점으로는, 안정적인 로드 밸런싱을 구축할 수 없다.
• 해당 방식에는 서버들의 헬스 체크 과정이 없기 때문에, 선택 받은 서버의 상태가 불가능이어도 해당 IP 정보를 제공한다.
  따라서 고가용성을 보장할 수 없다.
• 또한 IP리스트 중에서 IP 를 선택하는 것이 사용자 선택, 사용자 환경의 OS, APP 별로 다르기 때문에
  과부하 분산이 고르지 못하다는 단점도 있다.

프로세스 주소 공간

• 프로그램이 실행되면 프로세스 주소 공간이 메모리에 할당 되며 해당 공간은 3 영역으로 이루어져 있다.
• 코드 영역 ( Code Segment )
  • 프로그램의 코드가 저장되어 있음.
  • Read-Only
  • Why? 컴파일 되고나서는 코드 부분은 바뀔일이 없기 때문에, 재사용성을 위해 분리했다.
    같은 프로그램상에서 같은 프로세스를 여러개 실행하는 경우, 코드 영역을 다시 할당하지 않고,
    하나의 코드영역을 여러 프로세스가 공유하여 메모리를 절약한다.
• 데이터 영역 ( Data Segment )
  • 전역 변수, 정적 변수, 배열, 구조체 같은 데이터가 저장되어 있음.
  • Read-Write
  • 초기화 된 데이터는 .data영역에, 초기화 되지 않은 변수는 .bss 영역에 저장된다.
• 스택 영역 ( Stack Segment )
  • 함수나 지역 변수가 잠시 저장되는 임시 공간.
  • Read-Write
  • 런타임시 사이즈를 바꿀 수 없다.
• Heap 영역
  • 필요에 의해 동적으로 메모리를 할당 하고자 할 때 위치하는 동적 데이터 영역.
  • 메모리 주소 값에 의해서만 참조되고 사용됨.
• 스택과 데이터 영역이 서로 분리되어 있기 때문에 함수의 Stack 구조에서
  데이터 영역의 글로벌 변수에 접근이 가능하고 데이터도 보존될 수 있다.

DB - Index

• 인덱스란?
  • 인덱스는 검색을 원하는 데이터를 쉽고 빠르게 가져오기 위해서 해당 레코드가 저장되어 있는 주소 키 값과 데이터를 쌍으로 저장
  • 인덱스를 검색할 때 빠르게 가져오기 위해서 인덱스는 정렬된 상태로 있어야한다.
  • 따라서 인덱스를 이용하는 것은 빠른 탐색을 위해 삽입, 삭제의 시간을 희생하는 것이다.
  • 인덱스가 너무 많이 저장되어도 안 좋다.
• 인덱스 자료구조
  • B+Tree
    • 일반적으로 사용되는 인덱스 알고리즘.
    • 리프 노드를 제외하고서는 데이터의 인덱스가 저장된다.
    • 리프 노드에는 데이터가 저장되며 서로 다른 부모를 지닌 리프노드들도 리스트로 연결되었고 정렬되어 있다.
  • Hash 인덱스
    • 칼럼의 값으로 해시 값을 계산해서 인덱싱하는 알고리즘으로 빠른 검색을 지원한다.
    • 동등 연상에 대해서는 빠른 속도를 보여주지만, 값을 변형해서 인덱싱 하므로
      부분 검색, 전방 일치 검색과 같은 기능은 불가능한다.
• 인덱스의 성능과 고려 사항
  • 인덱스를 만들어 SELECT 쿼리의 성능을 향상 시켜도 INSERT, UPDATE, DELETE 쿼리문에 대해서는 성능 손실이 발생하고,
    인덱스를 설정하는 방식에 따라서도 다른 성능을 보이기 때문에 주의 깊게 설계해야한다.
  • 인덱스 설정 후 INSERT 시 인덱스에 대한 데이터도 추가하는 과정이 발생한다.
  • 인덱스 설정 후 DELETE 시 인덱스에 존재하는 값은 삭제가 아닌 사용하지 않는 다는 표시로 처리한다.
    (아마 인덱스의 정렬상태를 위해 삭제시 값의 복사과정을 안 하게 하려는 의도..?)
    이러한 과정이 반복될 시 비효율적이다.
  • 인덱스 설정 후 UPDATE 시 인덱스에 대해서도 UPDATE 및 재정렬 과정이 발생한다.
  • 인덱스에 사용되는 요소의 순서, 구성 요소에 대해서도 성능이 다 다르다.

JVM

• Java Virtual Machine 은 JAVA 프로그램과 OS 사이에서 중개자 역할을 수행하여 자바 프로그램이 사용되는  OS와 환경에
  구애 받지 않고 구동될 수 있도록 해준다.
• 위 특성 때문에 프로그램 설계자, 제공자의 환경과 사용자의 환경이 크게 달라도 JVM이 설치 되어 있으면 어디서든 재사용 가능하다.
• 또한 프로그램의 메모리 관리를 수행해주는데 대표적으로 GC ( garbage collection ) 이 있다.
• 위 특성 때문에 한정된 메모리를 효율적으로 사용하여 최고의 성능을 낼 수 있으며,
  프로그래머 입장에서도 메모리 효율성을 위해 메모리 누수를 방지하는 설계를 어렵게 하기 보다,
  웬만한 메모리 관리를 자동으로 해주기 때문에 편리하다고 할 수 있다. 
• 스택 기반의 가상 머신이다.
• 자바 프로그램의 실행 과정
  • 프로그램 실행 시 JVM 은 OS로 부터 이 프로그램이 필요로 하는 메모리를 할당 받는다.
  • javac( 자바 컴파일러 ) 가 자바 소스 코드를 읽어들여 .class( 자바 바이트코드 ) 로 변환시킨다.
  • Class Loader를 통해 class 파일들을 JVM으로 로딩한다.
  • 로딩된 class 파일들은 Execution engine 을 통해 해석된다.
  • 해석된 바이트코드는 Runtime Data Area에 배치되어 실행된다.
  • JVM 이 과정들과 프로그램 구동 중에 필요에 따라 쓰레드 동기화와 GC를 수행한다.

JVM 추가 정보 - ( asfirstalways.tistory.com/158 )