KR101595967B1 - 데드라인 부여된 작업의 분산 처리 성능 향상을 위한 맵리듀스 스케쥴링 시스템 및 방법 - Google Patents

Abstract

본 발명은 데드라인 부여된 작업의 분산 처리 성능 향상을 위한 맵리듀스 스케쥴링 시스템 및 방법에 관한 것으로서, 제출된 모든 잡(job)들을 관리하기 위한 지연 큐(delay queue)와 데드라인 관리가 필요한 잡을 다루는 긴급 큐(urgent queue)를 포함하는 스케쥴러, 가용 노드가 존재하는 경우, 시급한 잡의 존재 여부, 데이터 지역성 만족 여부, 노드의 I/O 부하 존재 여부를 고려하여 잡 태스크를 할당하고, 가용 노드가 존재하지 않는 경우, 가장 시급하지 않은 잡을 검색하고 상기 가장 시급하지 않은 잡의 태스크를 지연시켜 시급한 잡 태스크를 할당하는 태스크 할당부 및 상기 태스크 할당부에 태스크 할당을 요청하는 노드를 포함함으로써, 데드라인 부여된 작업의 분산 처리 성능을 향상시킬 수 있다.

Description

데드라인 부여된 작업의 분산 처리 성능 향상을 위한 맵리듀스 스케쥴링 시스템 및 방법{System and Method for MapReduce Scheduling to Improve the Distributed Processing Performance of Deadline Constraint Jobs}

본 발명은 맵리듀스 스케쥴링 시스템 및 방법에 관한 것으로, 더욱 상세하게는 맵리듀스에서 데드라인이 부여되지 않은 잡(job)과 데드라인이 부여된 다수의 잡들이 동시에 수행될 때 데이터 지역성과 노드의 I/O(Input/Output) 부하를 고려함으로써, 실시간으로 변화하는 노드들의 I/O 부하 상황에 따라 유연하게 잡의 태스크(task)를 할당하는 데드라인 부여된 작업의 분산 처리 성능 향상을 위한 맵리듀스 스케쥴링 시스템 및 방법에 관한 것이다.

다양한 정보 채널의 등장으로 인해 디지털 정보량이 기하급수적으로 증가함에 따라 빅데이터를 활용하기 위한 다양한 연구들이 진행되고 있다. 빅데이터는 일반적인 정보 처리 기술로는 처리가 어려우며 원하는 결과를 생성하기 위해 많은 비용이 소모된다. 이로 인해, 빅데이터를 분산 저장 및 처리하기 위한 병렬처리 시스템에 대한 많은 연구들이 진행되고 있다. 최근 이러한 연구 중 하나로서 분산처리시스템인 하둡(hadoop)이 주목받고 있다. 하둡은 대규모의 데이터를 저장 및 처리하기 위한 분산 응용 프로그램을 지원하는 오픈소스 소프트웨어 프레임워크이다.

하둡은 대용량 데이터 처리를 위해 클러스터 환경에서 동작하는 오픈 소스 프레임워크로 하둡 분산 파일 시스템(HDFS; Hadoop Distributed File System)과 맵리듀스(mapreduce)로 구성되어 있다. 맵리듀스는 클러스터에서 수행되는 분산 데이터 처리 모델과 실행 환경을 제공하며 맵(map) 단계와 리듀스(reduce) 단계로 나누어 처리된다. 잡 수행에 있어 중요한 이슈 중 하나는 수행 결과를 생성하기 위한 시간 즉, 완료 시간을 단축시키는 것이다. 이를 위해 잡 트래커(job tracker)는 잡 큐(job queue)에서 맵리듀스 작업을 수행할 잡의 우선 순위를 결정하기 위한 스케쥴링을 수행한다.

맵리듀스는 제출된 잡이 여러 개의 태스크로 분할되고, 각각의 태스크들이 노드에 분산 처리되며, 모든 잡 태스크들이 완료되면 해당 잡이 최종 완료된다. 맵리듀스는 기본 스케쥴러로서 FIFO(First In First Out) 스케쥴러를 가진다. FIFO 스케쥴러는 잡 큐에 제출된 잡들을 제출된 순서대로 하나씩 최종완료 시키는 스케쥴러이다. 따라서, 일반적인 FIFO 방식의 스케쥴링은 맵리듀스 작업이 수행되는 노드에 데이터가 존재하지 않을 경우 다른 노드로부터 데이터를 전송받아 수행하기 때문에 작업 시간이 지연된다. 또한, 공정 스케쥴링(Fair Scheduling) 기법은 각 잡을 담당하는 자원(노드)을 나누어 동시에 잡을 처리하는 기법이다. 하지만, 데이터 지역성을 고려하지 않기 때문에 작업 시간의 지연이 발생한다.

지역성을 고려한 스케쥴링은 잡 수행에 필요한 데이터가 존재할 경우 해당 노드에 잡을 할당하는 것이다. 데이터 지역성을 고려한 대표적인 스케쥴링 기법에는 지연 스케쥴링(Delay Scheduling) 기법이 제안되었다. 지연 스케쥴링은 맵리듀스의 스케쥴링을 연구하는 기법에 많은 비교 지표로 쓰이는 대표적인 스케쥴러이다. 지연 스케쥴링은 기존 제안된 공정 스케쥴링 기법에 데이터 지역성을 추가 고려한 기법이다. 맵리듀스의 기본 정책에 따라 유저가 제출한 잡이 여러 개의 태스크로 분할되면, 지연 스케쥴링은 잡 대기 큐에 태스크가 가장 적은 잡을 최우선으로 오름차순 정렬 한다. 정렬된 잡들은 태스크 하나씩 가용 노드(free node)의 가용 슬롯에 할당되며, 할당 될 때 마다 재정렬 된다. 또한, 지연 스케쥴링은 잡 큐에서 우선 순위가 가장 높은 잡의 태스크가 할당하기 전 할당하려는 가용 노드에 데이터 지역성이 성립하는지 확인한다. 만약 데이터 지역성을 만족하지 못할 경우 다음 순서의 잡에게 태스크 할당 기회를 넘겨준다. 잡 태스크 할당이 지연된 잡은 다음 가용 노드가 발생시 태스크 우선 순위가 가장 높아진다. 하지만 계속적으로 잡의 데이터 지역성이 성립되지 않으면 잡 태스크 할당이 계속 지연되어 잡의 최종 완료 시간이 비정상적으로 증가한다. 이러한 현상을 방지하기 위하여 지연 시간 제한을 단계별로 설정한다. 즉, 특정 임계치 시간제한 W를 정한다. 대기하는 시간 T가 조건 T < W1를 만족할 때 까지 노드 지역성(node locality)만을 확인하고, W1 < T < W2 까지는 랙 지역성(rack locality)까지의 성립을 확인한다. 만약 T > W2 이라면 더 이상 지연을 수행하지 않고 태스크를 오프 랙(off-rack)에 할당한다. 이처럼, 데이터 지역성을 고려한 스케쥴링 기법은 다른 노드로부터 데이터를 전송하는 시간을 감소시키기 때문에 작업 시간을 단축시킬 수 있다. 그러나, 데이터 지역성만을 고려하는 기법은 정해진 시간 내에 작업 수행을 완료하기 위해 데드라인 제약(deadline constraint)을 부여한 맵리듀스를 이용한 특정한 응용 작업 환경에서는 적용하기 어렵다. 또한, 노드의 부하를 고려하지 않기 때문에 특정 노드에서 작업 완료 시간 내에 작업이 완료되지 못하는 문제점이 있다. 실제로 맵리듀스를 이용하여 빅데이터를 다룰 때, 특성이 다른 여러가지 잡들을 동시에 처리하며 생기는 노드의 부하로 인해 하나의 잡만을 수행 할 때와 비교하여 완료시간의 차이가 큰 것을 확인 할 수 있다.

최근 데드라인이 부여된 잡을 처리하기 위해 다양한 스케쥴링 기법들이 제안되었다. Kai WANG에서는 제출된 잡들을 데드라인 내에 작업완료 시키기 위해 잡을 수행하며 기록되는 태스크들의 평균 완료 시간을 이용한다[Kai WANG, Ying WANG, and Bo YIN, "Deadline Scheduling for MapReduce Environment," Journal of Computational Information Systems, 2013]. 진행 중인 태스크 진행시간이 잡의 태스크 평균 완료시간보다 초과되면, 해당 태스크를 추론적 태스크(speculative task)로 전환한다. 추론적 태스크란 태스크 평균 완료시간을 초과하여 진행되는 태스크와 동일한 태스크를 다른 노드에서 실행시키는 것을 의미한다. 두 개의 태스크 중 먼저 완료되는 태스크 결과를 취하며, 태스크가 완료되면 나머지 태스크는 실행 취소된다. 또한, 잡의 예상 완료시간을 초과하면 잡의 우선순위를 가장 높게 조정한다. 잡의 예상 완료시간은 과거이력 속도(historical speed)를 고려하여 계산한다. 과거이력 속도란 유저에 의해 제출된 잡에 잡의 유형이 첨부되어 오면, 과거에 기록된 잡 유형에 따른 태스크 처리 속도들 중 제출된 잡의 유형과 부합하는 처리속도를 의미한다. 하지만, 이러한 기법 또한, 노드의 실시간 I/O 부하상태에 따른 스케쥴링을 고려하지 않아 과부하 상태의 노드가 많이 발생할수록 전반적인 맵리듀스의 잡 완료시간 성능이 저하된다.

이에, 본 발명에서는 맵리듀스 데드라인을 고려한 잡의 태스크 스케쥴링 기법을 제안한다. 본 발명에서 제안하는 기법은 데이터 지역성만을 고려한 기존 연구들과는 달리 데드라인 제약이 있는 특정 환경에서 데드라인을 충족시키기 위해 처리가 급한 잡들을 관리하기 위한 긴급 큐를 사용한다. 또한, 실시간으로 변화하는 노드들의 I/O 부하 상황을 고려하여 I/O 부하 상황에 따라 유연하게 잡의 태스크를 할당하는 스케쥴링 기법을 제안한다.

대한민국 등록특허공보 제10-14327510000호(등록일 2014.08.11.)

따라서, 본 발명은 상기한 종래 기술의 문제점을 해결하기 위해 이루어진 것으로서, 본 발명의 목적은 데이터 지역성 뿐만 아니라 실시간으로 변화하는 I/O 부하를 고려하여 잡 스케쥴링을 수행함으로써 데이터 지역성만을 고려한 기법보다 전반적인 맵리듀스의 잡 수행 시간을 단축시키며 데드라인이 부여된 잡들의 데드라인 실패율을 감소시키고, I/O 부하가 존재하는 노드에서 잡을 처리해야 할 경우 잡 처리에 필요한 동일 데이터를 가진 복제본 노드를 활용하여 잡 태스크 처리 속도를 향상시키며, 잡 예상 완료 시간이 데드라인을 초과했음에도 불구하고 가용 노드가 발생하지 않을 경우 가장 시급하지 않은 잡을 검색하고 해당 잡의 태스크를 지연시켜 잡의 완료 시간을 앞당길 수 있는 데드라인 부여된 작업의 분산 처리 성능 향상을 위한 맵리듀스 스케쥴링 시스템 및 방법을 제공하는데 있다.

상기와 같은 목적을 달성하기 위한 본 발명의 데드라인 부여된 작업의 분산 처리 성능 향상을 위한 맵리듀스 스케쥴링 시스템은, 제출된 모든 잡(job)들을 관리하기 위한 지연 큐(delay queue)와 데드라인 관리가 필요한 잡을 다루는 긴급 큐(urgent queue)를 포함하는 스케쥴러, 가용 노드가 존재하는 경우, 시급한 잡의 존재 여부, 데이터 지역성 만족 여부, 노드의 I/O 부하 존재 여부를 고려하여 잡 태스크를 할당하고, 가용 노드가 존재하지 않는 경우, 가장 시급하지 않은 잡을 검색하고 상기 가장 시급하지 않은 잡의 태스크를 지연시켜 시급한 잡 태스크를 할당하는 태스크 할당부 및 상기 태스크 할당부에 태스크 할당을 요청하는 노드를 포함한다.

한편, 본 발명의 데드라인 부여된 작업의 분산 처리 성능 향상을 위한 맵리듀스 스케쥴링 방법은, 가용 슬롯이 발생한 노드가 태스크 할당부에 처리할 태스크를 요청하면, 태스크 할당부가 가용 노드가 존재하는지 여부를 판단하는 단계 및 상기 판단 결과 가용 노드가 존재하는 경우, 상기 태스크 할당부가 시급한 잡의 존재 여부, 데이터 지역성 만족 여부, 노드의 I/O 부하 존재 여부를 고려하여 잡 태스크를 할당하고, 가용 노드가 존재하지 않는 경우, 상기 태스크 할당부가 가장 시급하지 않은 잡을 검색하고 상기 가장 시급하지 않은 잡의 태스크를 지연시켜 시급한 잡 태스크를 할당하는 단계를 포함한다.

상술한 바와 같이, 본 발명에 의한 데드라인 부여된 작업의 분산 처리 성능 향상을 위한 맵리듀스 스케쥴링 시스템 및 방법에 따르면, 제출된 잡들을 제한시간 내에 처리하기 위해 데이터 지역성 만족 여부를 확인하고 I/O 부하 및 데드라인 만족 여부를 고려하며, I/O 부하가 존재하는 노드에서 잡을 수행할 경우 복제본 노드의 데이터를 활용하여 잡 태스크 처리 속도를 향상시키고, 잡 예상 완료 시간이 데드라인을 초과했음에도 가용 노드가 발생하지 않을 경우 데드라인에 여유가 있는 잡의 태스크를 지연시켜 잡의 완료 시간을 단축시킬 수 있다.

도 1은 본 발명의 일 실시예에 따른 맵리듀스의 스케쥴링 시스템의 개략적인 구성을 나타내는 블록도이다.
도 2는 긴급 큐에 처리가 시급한 잡이 존재하지 않을 경우의 잡 처리 과정을 나타내는 그림이다.
도 3은 긴급 큐에 처리가 시급한 잡이 존재할 경우의 처리 과정을 나타내느 그림이다.
도 4는 도 2 및 도 3에서 제출된 잡들을 처리하기 위해 필요한 데이터 청크를 나타낸다.
도 5는 본 발명의 일 실시예에 따라 가용 노드 발생 시 태스크 할당부가 잡 태스크를 처리하는 절차를 나타내는 흐름도이다.
도 6은 가용 노드에서 가장 시급한 잡의 데이터 지역성을 만족하지만, I/O 부하가 존재하는 경우의 스케쥴링을 나타내는 그림이다.
도 7은 가용 노드 2가 데이터 지역성을 만족하지 않고 I/O 부하가 존재하며, 복제본 노드 3에 I/O 부하가 존재하지 않을 경우의 스케쥴링을 나타내는 그림이다.
도 8은 가용 노드 2가 데이터 지역성을 만족하지 않으며, 가용 노드 2와 복제본 노드 3의 I/O 부하가 존재하는 경우의 스케쥴링을 나타내는 그림이다.
도 9는 본 발명의 일 실시예에 따라 가용 노드 발생하지 않을 경우 태스크 할당부가 잡 태스크를 처리하는 절차를 나타내는 흐름도이다.
도 10은 긴급 큐에 잡이 존재하고 잡의 예상 완료 시간이 데드라인을 초과하는 즉, 처리가 가장 시급한 잡이 존재함에도 불구하고 가용 슬롯을 발생시키는 노드가 없을 경우의 스케쥴링을 나타내는 그림이다.

이하, 본 발명의 데드라인 부여된 작업의 분산 처리 성능 향상을 위한 맵리듀스 스케쥴링 시스템에 대하여 첨부된 도면을 참조하여 상세히 설명하기로 한다.

하둡(Hadoop)은 분산 처리 플랫폼을 제공하는 아파치 오픈소스 프로젝트로 신뢰성(reliability)과 확장성(scalability)을 보장하는 환경을 제공하여 현재 아마존(Amazon), 야후(Yahoo), 페이스북(Facebook) 등 많은 업체에서 사용되고 있다.

이러한 하둡을 구성하는 중요한 요소 중 하나인 맵리듀스는 구글(Google)에서 제안한 맵리듀스 프로그래밍 모델을 하둡에 맞춰 구현한 소프트웨어 프레임워크로서, 분산 환경에서 대용량 데이터를 처리하는데 있어서, 간단하고 직관적인 인터페이스를 제공한다.

도 1은 본 발명의 일 실시예에 따른 맵리듀스의 스케쥴링 시스템의 개략적인 구성을 나타내는 블록도이다.

도 1에 도시된 바와 같이, 본 발명의 맵리듀스의 스케쥴링 시스템은 지연 큐(21)와 긴급 큐(22)를 포함하는 스케쥴러(20), 스케쥴러 선택부(31)와 스케쥴링 처리부(32)를 포함하여 노드에 태스크를 할당하는 태스크 할당부(30) 및 상기 태스크 할당부에 태스크 할당을 요청하는 하나 이상의 노드들(40-1, 40-2, 40-3, ...)(총괄하여 "40")을 포함한다. 여기서, 사용자에 의해 제출된 잡(job)은 스케쥴러(20), 태스크 할당부(30)를 포함하여 스케쥴링 역할을 하는 맵리듀스의 잡 트래커(10)에 의해 처리된다.

스케쥴러(20)는 제출된 모든 잡들을 관리하기 위한 지연 큐(delay queue)(21)와 데드라인 관리가 필요한 잡을 다루는 긴급 큐(urgent queue)(22)로 구성된다. 지연 큐(21)는 일반적으로 사용자가 제출한 모든 잡들을 관리하는 큐로서, 후술하는 태스크 할당부(30)를 통해 기존 지연 스케쥴링(Delay Scheduling)에서 사용하는 잡 큐와 동일한 처리를 수행한다. 긴급 큐(22)는 데드라인 내에 잡 수행이 완료되지 못할 것으로 예상되는 처리가 시급한 잡들을 관리하는 큐로서, 데이터 지역성 만족 여부와 노드 부하 등으로 인해 지연 스케쥴러를 사용할 경우 정해진 시간 내에 작업을 완료하지 못하는 잡을 별도로 관리하며, 태스크 할당부(30)릍 통해 잡을 데드라인 내에 충족시키는 데드라인 스케쥴링을 한다. 지연 큐(21)에 제출된 잡은 데드라인 T_d와 예상 완료시간 T_p의 차이 T_th가 사용자가 정한 임계값 ε이하가 될 경우 긴급 큐(22)에 등록된다. 긴급 큐(22)에 제출된 잡들은 T_th 값에 의해 오름차순으로 정렬되어 데드라인 여유 시간이 가장 낮은 값이 가장 높은 우선 순위를 갖는다.

도 2는 긴급 큐(22)에 처리가 시급한 잡이 존재하지 않을 경우의 잡 처리 과정을 나타내는 그림이다. 도 3은 각 노드가 4 개의 태스크 슬롯을 가진다고 가정할 때 긴급 큐(22)에 처리가 시급한 잡이 존재할 경우의 처리 과정을 나타내느 그림이다. 도 4는 도 2 및 도 3에서 제출된 잡들을 처리하기 위해 필요한 데이터 청크를 나타낸다.

도 2 및 도 3과 같이 가용 노드 2가 잡 트래커(10)에게 태스크 할당을 요청할 경우 후술하는 태스크 할당부(30)는 먼저 긴급 큐(22) 내 잡의 존재 유무를 확인한다. 만약 도 2와 같이 긴급 큐(22)에 잡이 존재하지 않으면 지연 큐(21)에 있는 job 1의 태스크를 가용 노드 2에 할당한다. 만약 긴급 큐(22)에 잡이 존재한다면 도 3과 같이 해당 잡을 지연 큐로 관리되는 모든 잡들 보다 먼저 가용 슬롯에 할당한다.

태스크 할당부(30)는 크게 가용 노드가 존재하는 경우와 가용 노드가 발생하지 않는 경우로 구분하여 스케쥴링을 처리한다. 이에, 가용 노드가 존재하는 경우 태스크 할당부(30)는 시급한 잡의 존재 여부, 데이터 지역성 만족 여부, 노드의 I/O 부하 존재 여부를 고려하여 잡 태스크를 할당한다.

구체적으로, 태스크 할당부(30)는 데이터 지역성 뿐만 아니라 실시간으로 변화하는 I/O 부하를 고려하여 잡 스케쥴링을 수행함으로써 데이터 지역성만을 고려한 기법보다 전반적인 맵리듀스의 잡 수행 시간을 단축시키며 데드라인이 부여된 잡들의 데드라인 실패율을 감소시키고, I/O 부하가 존재하는 노드에서 잡을 처리해야 할 경우 잡 처리에 필요한 동일 데이터를 가진 복제본 노드를 활용하여 잡 태스크 처리 속도를 향상시키며, 잡 예상 완료 시간이 데드라인을 초과했음에도 불구하고 가용 노드가 발생하지 않을 경우 가장 시급하지 않은 잡을 검색하고 해당 잡의 태스크를 지연시켜 시급한 잡의 완료 시간을 앞당길 수 있다. 이러한 태스크 할당부(30)의 자세한 동작은 이하 도 5 내지 도 10을 참조하여 보다 상세히 설명된다.

그러면, 여기서 상기와 같이 구성된 시스템을 이용한 본 발명의 데드라인 부여된 작업의 분산 처리 성능 향상을 위한 맵리듀스 스케쥴링 방법에 대해 설명하기로 한다.

본 발명의 일 실시예에 따른 태스크 할당부(30)의 잡 태스크 할당은 상기한 바와 같이 크게 가용 노드가 존재하는 경우와 가용 노드가 발생하지 않을 경우로 구분하여 처리된다.

도 5는 본 발명의 일 실시예에 따라 가용 노드 발생 시 태스크 할당부(30)이 잡 태스크를 처리하는 절차를 나타내는 흐름도이다.

사용자로부터 맵리듀스에 다양한 잡이 제출되면, 잡 트래커(10)의 스케쥴링 정책에 따라 잡의 태스크들이 노드(40)에 할당된다. 특히, 본 발명의 태스크 할당부(30)은 맵리듀스가 잡을 처리하는 중 자신이 할당받은 잡 태스크의 처리를 완료한 각 노드(40)가 heartbeat 통신을 통해 잡 트래커(10)에게 처리할 태스크를 요청하면, 시급한 잡이 존재하는지 여부, 가용 노드가 시급한 잡의 데이터 지역성을 만족하는지 여부 뿐만 아니라 가용 노드에 I/O 부하가 존재하는지 여부를 고려함으로써, 맵리듀스에서 데드라인이 부여되지 않은 잡과 데드라인이 부여된 다수의 잡들이 동시에 수행될 때 데드라인이 부여된 작업의 분산 처리 성능을 향상시킬 수 있다.

즉, 잡 처리 시, 본 발명의 태스크 할당부(30)는 가장 먼저 제출된 잡들 중 데드라인 내에 완료되지 못하는, 처리가 시급한 잡이 존재하는지를 확인한다. 이때, 태스크 할당부(30)의 스케쥴러 선택부(31)는 제출된 잡에 데드라인이 부여된 잡과 데드라인이 부여되지 않은 일반 잡들이 혼재할 경우, 데드라인이 부여된 잡들의 잡 예상 완료 시간과 데드라인의 차이를 통해 처리가 시급한 잡인지를 판단한다. 다음으로, 태스크 할당부(30)의 스케쥴링 처리부(32)는 잡을 처리 할 수 있는 상태인 가용 노드에 잡 처리에 필요한 데이터가 존재하는지 즉, 데이터 지역성을 만족하는지 여부를 판단하여 스케쥴링한다. 마지막으로, 스케쥴링 처리부(32)는 잡 태스크를 할당 할 가용 노드에 I/O 부하가 존재하는지를 판단하여 존재 할 경우 해당 잡 태스크를 처리하는데 필요한 데이터 청크를 가지고 있는 복제본 노드를 이용하여 복제본 노드에서 청크를 수신하여 처리한다.

이제, 도 5를 참조하여 본 발명의 일 실시예에 따른 맵리듀스 스케쥴링 방법에 대하여 보다 구체적으로 살펴보자. 태스크를 수행할 수 있는 가용 슬롯이 발생한 각 노드(40)가 heartbeat 통신으로 잡 트래커(10)에 처리할 태스크를 요청하면, 스케쥴러 선택부(31)가 제출된 잡들 중 데드라인 내에 작업이 끝나기 어려운, 즉 처리가 시급한 잡들이 존재하는지 판단한다(S110). 상기한 바와 같이, 본 발명에서는 맵리듀스가 잡을 수행하는 중 처리가 시급한 잡들이 발생할 수 있고 이러한 처리가 시급한 잡들은 본 발명의 긴급 큐(22)로 관리되므로, 스케쥴러 선택부(31)는 처리가 시급한 잡이 존재하는지를 판단하기 위해 긴급 큐(22) 내의 잡 존재 유무를 확인한다.

단계 S110 판단 결과, 긴급 큐(22)에 잡이 존재하지 않는다면 스케쥴러 선택부(31)는 지연 스케쥴러를 선택하여 지연 큐(21)에서 기존 기법인 지역성을 고려한 지연 스케쥴링 기법을 수행한다(S120). 긴급 큐(22)에 잡이 존재하는 경우 스케쥴러 선택부(31)는 데드라인 스케쥴러를 선택하여 긴급 큐(22)에 존재하는 잡에 대해 사용 노드의 데이터 지역성과 노드의 I/O 부하에 따라 달리 처리하는 데드라인 기반 스케쥴링을 수행한다(S130).

긴급 큐(22)에 잡이 존재하여 데드라인 스케쥴러가 선택된 경우(S130), 스케쥴링 처리부(32)는 잡 태스크를 수행할 수 있는 상태인 가용 노드에 잡 처리에 필요한 데이터 청크가 존재하는지 즉, 데이터 지역성을 만족하는지 여부를 판단한다(S140).

단계 S140 판단 결과, 데이터 지역성을 만족한다면 스케쥴링 처리부(32)는 해당 가용 노드에 I/O 부하가 존재하는지 여부를 판단한다(S140). 데이터 지역성을 만족하지만 가용 노드의 I/O 부하가 큰 경우 처리가 시급한 잡 태스크를 할당하게 되면, 처리가 시급한 잡과 이미 할당되어 수행 중인 작업이 모두 지연되는 현상이 일어난다. 이를 해결하기 위해, 본 발명의 스케쥴링 처리부(32)는 필요한 데이터 청크를 수신할 수 있는 복제본 노드를 검색한다(S151). 그리고, 복제본 노드가 검색되면 복제본 노드에서 데이터 청크를 전송하기 위해서는 복제본 노드에서 청크를 읽어들여 전송하기 때문에, 스케쥴링 처리부(32)는 복제본 노드에 I/O 부하가 존재하는지 또한 판단해야 한다(S152). 복제본 노드에 I/O 부하가 없으면 복제본 노드에서 필요한 데이터 청크를 수신하여 가용 노드에서 잡 태스크를 처리한다(S162). 복제본 노드 또한 부하가 존재하면, 스케쥴링 처리부(32)는 가용 노드에서 이미 할당되어 있는 다른 잡 태스크들 중 데드라인에 여유가 있는 잡 태스크들을 중지시켜 가용 노드의 부하를 낮춘다(S153). 즉, 스케쥴링 처리부(32)는 이미 할당되어 있는 잡 태스크들 중 처리가 시급한 잡의 처리에 필요한 데이터 청크를 읽어 들이는데 필요한 시간만큼 정지시켜도 데드라인 내에 잡을 완료 할 수 있는 잡을 선택한다. 이때, 태스크의 중지 시간은 하나의 데이터 청크를 읽는 평균 시간으로 한다. 데드라인 여유가 있는 잡 태스크의 판별은 수학식 1과 같다. 여기서, T_d는 잡에 부여된 데드라인, T_P는 해당 잡의 예상 완료 시간, T_io는 하나의 데이터 청크를 I/O하는 평균 시간, T_th는 데드라인 여유가 있는 잡을 판단하는 기준이 되는 사용자가 정한 임계치이다. 수학식 1과 같이 데드라인(T_d)과 잡의 예상 완료시간과 데이터 청크를 I/O하는 시간을 더한 값(T_p+T_io)의 차가 임계치(T_th) 이상이라면 중지시킬 수 있는 잡으로 판단한다.

도 6은 가용 노드에서 가장 시급한 잡의 데이터 지역성을 만족하지만, I/O 부하가 존재하는 경우의 스케쥴링을 나타내는 그림이다. 제출된 잡들의 필요 데이터 청크 상태는 도 4와 같다. I/O 부하가 존재하는 노드는 노드 2, 노드 3이며, job 1에서 job 5까지의 총 5개의 잡이 사용자로 부터 제출되었다고 가정한다. job 5와 job 4, 두 개의 잡이 시급한 잡으로 판단되어 긴급 큐에 할당되었다. 먼저, 스케쥴링 처리부(32)는 시급한 잡인 job 5를 가용 노드 2에서 처리하기 위해 데이터 지역성 만족 여부를 체크한다(S140). 가용 노드 2가 데이터 지역성을 만족하지만 I/O 부하가 존재하여(S140의 예) 복제본 노드 3을 검색한다(S151). 복제본 노드 3도 I/O 부하가 존재하기 때문에 가용 노드 2에서 이미 잡 처리를 위해 할당된 태스크를 중단시킨다(S153). 가용 노드 2는 job 1과 job 3의 태스크들을 잡 5를 처리하기 위해 필요한 데이터 청크 D를 로드할 시간만큼 중단된 상태이다. job 2와 job 3는 수학식 1에 의해 선택된 잡들이다.

단계 S140 판단 결과, 가용 노드에 잡을 처리하기 위해 필요한 데이터 청크가 존재하지 않는다면 즉, 데이터 지역성을 만족하지 않는다면, 스케쥴링 처리부(32)는 필요한 데이터가 존재하지 않는 경우에도 불구하고 가용 노드에 잡 태스크를 할당할 경우 잡을 처리하기 위해 필요한 블럭을 다른 노드에서 수신해야 하므로, 데이터 지역성을 만족하는 복제본 노드를 검색한다(S160). 그리고, 필요한 블럭을 전송하는 노드의 I/O 부하가 큰 경우 필요한 데이터 청크의 I/O 뿐만 아니라 이미 할당되어 있는 잡들의 태스크 처리 속도 또한 저하되기 때문에, 복제본 노드가 검색되면 스케쥴링 처리부(32)는 복제본 노드의 I/O 부하 상태를 확인한다. 만약 복제본 노드에 I/O 부하가 존재하지 않을 경우 데이터 청크를 수신하여 가용 노드에서 처리가 시급한 잡 태스크를 처리한다(S162). 만약 만약 복제본 노드조차 I/O 부하가 존재할 경우, 스케쥴러는 복제본 노드가 가용 상태가 될 때까지 대기 후 해당 노드에서 태스크를 수행하는 것이 효율적인지, 복제본 노드에서 가용 노드로 데이터 블럭을 수신하여 태스크를 수행하는 것이 효율적인지를 판단한다(S161). 본 단계(S161)에서는 수학식 2, 수학식 3, 수학식 4를 이용하며 각 노드마다 가용 슬롯이 생성되어 가용 노드가 되는 평균 주기를 측정한다. 수학식 3은 T_wx를 계산하는 식으로서, T_wx는 필요한 데이터를 가진 노드가 가용 노드가 될 때까지 대기하여 해당 노드에서 태스크를 처리할 경우 태스크 예상 완료 시간이다. 여기서, T_p는 필요한 데이터를 가진 노드가 가용 슬롯이 생기는 평균 주기, T_io는 청크 하나를 I/O하는데 소비되는 평균 시간, T_ex는 해당 잡의 태스크를 실행하는데 소요되는 평균 시간이다. 수학식 4는 T_tx를 계산하는 식으로서, T_tx는 필요한 데이터를 복제본 노드에서 기존 가용 노드로 전송하여 수행할 경우의 태스크 예상 완료 시간이다. 이때, T_io는 청크 하나를 I/O하는데 소비되는 평균시간, T_trans는 청크 하나를 네트워크로 전송하는 평균 전송 시간이다. 네트워크 전송 시간은 하나의 데이터 청크가 같은 랙 안에서 전송되는 평균 시간과 랙 외부에서 전송되는 평균 시간으로 구분하여 계산한다. 이에, 해당 단계 S161에서 스케쥴링 처리부(32)는 수학식 2를 통해 수학식 3과 수학식 4를 비교하여 앞서 설명한 복제본 노드가 가용 상태가 될 때까지 대기 후 해당 노드에서 태스크를 수행하는 것이 효율적인지, 복제본 노드에서 가용 노드로 데이터 블럭을 수신하여 태스크를 수행하는 것이 효율적인지를 판단한다. 이에, 복제본 노드가 가용 상태가 될 때까지 대기하는 것이 효율적이라고 판단된 경우 즉, 수학식 2를 만족할 경우 단계 S151로 진행하여 가장 처리가 시급한 잡의 태스크 할당을 잠시 지연시킨 후 복제된 노드가 가용 노드 상태로 변할 때 다시 태스크를 할당을 시도한다. 만약 복제본 노드에서 가용 노드로 데이터 블록을 수신하여 태스크를 수행하는 것이 효율적이라고 판단된 경우 즉, 수학식 2를 만족하지 않을 경우 기존 가용 노드에서 태스크를 수행시킨다(S162).

도 7은 가용 노드 2가 데이터 지역성을 만족하지 않고 I/O 부하가 존재하며, 복제본 노드 3에 I/O 부하가 존재하지 않을 경우의 스케쥴링을 나타내는 그림이다. 제출된 잡들의 필요 데이터 청크 상태는 도 4와 같다. 먼저, 가용 노드 2에 가장 처리가 시급한 잡인 job 5의 처리에 필요한 데이터 청크가 존재하지 않기에 복제본 노드 3을 검색한다. 복제본 노드 3은 job 5의 처리에 필요한 데이터 청크 D를 노드 2로 전송한다. 데이터 청크를 수신하면 가용 노드 2에서 태스크를 수행한다.

도 8은 가용 노드 2가 데이터 지역성을 만족하지 않으며, 가용 노드 2와 복제본 노드 3의 I/O 부하가 존재하는 경우의 스케쥴링을 나타내는 그림이다. 복제본 노드 3조차 I/O 부하가 존재하는 상태이므로 수학식 2를 만족하는지 확인한다. 수학식 2를 만족하며 복제본 노드 3이 가용 상태가 될 때까지 대기 후 할당한다.

도 9는 본 발명의 일 실시예에 따라 가용 노드 발생하지 않을 경우 태스크 할당부(30)가 잡 태스크를 처리하는 절차를 나타내는 흐름도이다.

본 발명의 태스크 할당부(30)는 데드라인이 사용자가 정한 임계치를 초과하는 잡들 즉, 처리가 시급한 잡들이 존재함에도 불구하고 가용 노드가 발생하지 않을 경우 제출된 잡들 중 가장 시급하지 않은 잡의 태스크를 중지시키고, 중지된 노드에 처리가 시급한 태스크를 할당시켜 잡의 데드라인 실패율을 낮춘다. 이때, 가장 시급하지 않은 잡이란 사용자에 의해 제출된 잡들 중 데드라인과 예상완료시간의 차이가 가장 큰 잡을 의미한다. 가용 노드가 발생하지 않을 경우의 스케쥴링은 데드라인이 부여된 잡들 중 예상 완료 시간이 사용자가 정한 임계치 T_th이상 데드라인을 초과해 버린 잡들이 존재함에도 불구하고 가용 노드가 발생하지 않는 경우를 의미한다. 이하, 사용자가 정한 임계치 T_th이상 데드라인을 초과해 버린 잡을 데드라인을 초과하는 잡이라고 명시한다. 이 경우, 새로운 가용 노드가 발생 할 때까지 대기하게 되면 임계치를 초과한 잡 뿐만 아니라, 긴급 큐에 존재하는 처리가 시급한 잡들의 완료 시간 또한 지연된다. 이를 해결하기 위해, 본 발명의 태스크 할당부(30)는 클러스터 내의 노드들에 이미 할당되어 있는 시급하지 않은 잡 태스크들을 이용한다.

도 9를 참조하여 구체적으로 설명하면, 먼저 태스크 할당부(30)가 데드라인을 초과하는 잡을 감지하면 현재 가용 노드의 존재 여부를 판단한다. 만약 가용 노드가 존재하면, 태스크 할당부(30)는 도 5에서 설명된 바와 같이 가용 노드가 발생 할 때의 스케쥴링을 실시한다. 가용 노드가 존재하지 않다면, 태스크 할당부(30)는 데드라인을 초과하는 잡을 처리하기 위해 필요한 데이터가 존재하는 노드들을 검색한다(S210). 다음으로, 현재 클러스터 내의 노드에서 잡 태스크가 할당되어 처리되고 있는 잡들 중 가장 시급하지 않은 즉, 잡 예상 완료 시간 T_p와 데드라인 T_d와의 차가 가장 큰 잡을 검색한다(S220). 검색이 완료되어 가장 시급하지 않은 잡이 선택되면 데드라인을 초과하는 잡의 데이터 지역성을 만족하는 노드들 중에 가장 시급하지 않은 잡의 태스크가 할당되어 있는지 확인한다(S230). 데드라인을 초과하는 잡의 데이터 지역성을 만족하는 노드들 중 가장 시급하지 않은 잡의 태스크가 할당되어 있는 노드가 검색되면 해당 노드에 할당되어 있던 가장 시급하지 않은 잡의 태스크들을 잠시 중단시킨다(S240). 그 후 해당 슬롯에 데드라인을 초과하는 잡 태스크를 할당한다(S260). 만약 검색된 노드들 중 가장 시급하지 않은 잡의 태스크가 존재하지 않는 경우, 해당 잡을 제외하고(S240) 단계 S220으로 돌아가 다음으로 시급하지 않은 잡을 검색한다. 그리고, 재검색된 잡을 기준으로 다시 진행된 시간이 가장 짧은 태스크가 존재하는 노드를 찾아 태스크를 잠시 중단시킨다.

도 10은 긴급 큐에 잡이 존재하고 잡의 예상 완료 시간이 데드라인을 초과하는 즉, 처리가 가장 시급한 잡이 존재함에도 불구하고 가용 슬롯을 발생시키는 노드가 없을 경우의 스케쥴링을 나타내는 그림이다. 총 5개의 제출된 잡들 중 job 4와 job 5만이 처리가 시급한 잡이며, 그 중 job 5는 데드라인을 초과하는 잡으로 가정한다. 스케쥴링의 최우선 순위로서 job 5의 태스크가 할당되어야 하지만 모든 노드들의 슬롯이 태스크 수행을 진행 중인 상태이기 때문에 가용 노드가 발생하지 않는다. 이 경우, 시급하지 않은 잡들 중 예상 완료 시간과 데드라인의 차가 가장 큰, 즉 가장 시급하지 않은 job 2를 찾는다. 그 후, 스케쥴러는 가장 시급한 job 5의 데이터 지역성을 만족하는 노드들을 검색하고, 검색된 노드들 중 job 2의 태스크가 존재하는 노드를 검색한다. 노드 3이 선택 되었다. 만약 job 2의 태스크가 처리 진행 중인 노드가 다수 존재할 경우, 가장 진행된 시간이 짧은 태스크가 존재하는 노드를 선택한다. 선택된 노드 3에서 job 2의 태스크인 태스크 1 및 태스크 2를 잠시 중단시키고 처리가 가장 시급한 job 5의 태스크 할당을 나타낸다.

이상에서 몇 가지 실시예를 들어 본 발명을 더욱 상세하게 설명하였으나, 본 발명은 반드시 이러한 실시예로 국한되는 것이 아니고 본 발명의 기술사상을 벗어나지 않는 범위 내에서 다양하게 변형실시될 수 있다.

10 : 잡 트래커
20 : 스케쥴러
21 : 지연 큐
22 : 긴급 큐
30 : 태스크 할당부
31 : 스케쥴러 선택부
32 : 스케쥴링 처리부
40 : 노드

Claims (9)

1. 제출된 모든 잡(job)들을 관리하기 위한 지연 큐(delay queue)와 데드라인 관리가 필요한 잡을 다루는 긴급 큐(urgent queue)를 포함하는 스케쥴러,
   가용 노드가 존재하는 경우, 시급한 잡의 존재 여부, 데이터 지역성 만족 여부, 노드의 I/O 부하 존재 여부를 고려하여 잡 태스크를 할당하고, 가용 노드가 존재하지 않는 경우, 가장 시급하지 않은 잡을 검색하고 상기 가장 시급하지 않은 잡의 태스크를 지연시켜 시급한 잡 태스크를 할당하는 태스크 할당부 및
   상기 태스크 할당부에 태스크 할당을 요청하는 하나 이상의 노드들을 포함하며,
   상기 가용 노드가 존재하는 경우 잡 태스크를 할당하는 단계는, 상기 태스크 할당부가:
   ⒜ 긴급 큐에 잡이 존재하는지 판단하는 단계,
   ⒝ 상기 긴급 큐에 잡이 존재하면, 상기 가용 노드가 데이터 지역성을 만족하는지 여부를 판단하는 단계,
   ⒞ 상기 ⒝단계 판단 결과, 상기 데이터 지역성을 만족하면, 상기 가용 노드에 부하가 존재하는지 여부를 판단하는 단계 및
   ⒟ 상기 ⒝단계 판단 결과, 상기 데이터 지역성을 만족하지 않으면, 복제본 노드를 검색하여 상기 복제본 노드에 부하가 존재하는지 여부를 판단하는 단계를 포함하는 데드라인 부여된 작업의 분산 처리 성능 향상을 위한 맵리듀스 스케쥴링 시스템.
   
2. 청구항 제1항에서,
   상기 스케쥴러는, 상기 지연 큐에 제출된 잡을 데드라인 T_d와 예상 완료시간 T_p의 차이 T_th가 사용자가 정한 임계값 ε이하가 될 경우 상기 긴급 큐에 등록하는, 데드라인 부여된 작업의 분산 처리 성능 향상을 위한 맵리듀스 스케쥴링 시스템.
   
3. 청구항 제1항에서,
   상기 태스크 할당부는,
   상기 긴급 큐에 상기 데드라인 내에 잡 수행이 완료되지 못할 것으로 예상되는 처리가 시급한 잡들이 존재하는 경우, 해당 잡을 상기 지연 큐로 관리되는 모든 잡들보다 먼저 가용 슬롯에 할당하는, 데드라인 부여된 작업의 분산 처리 성능 향상을 위한 맵리듀스 스케쥴링 시스템.
   
4. 가용 슬롯이 발생한 노드가 태스크 할당부에 처리할 태스크를 요청하면, 태스크 할당부가 가용 노드가 존재하는지 여부를 판단하는 단계 및
   상기 판단 결과 가용 노드가 존재하는 경우, 상기 태스크 할당부가 시급한 잡의 존재 여부, 데이터 지역성 만족 여부, 노드의 I/O 부하 존재 여부를 고려하여 잡 태스크를 할당하고, 가용 노드가 존재하지 않는 경우, 상기 태스크 할당부가 가장 시급하지 않은 잡을 검색하고 상기 가장 시급하지 않은 잡의 태스크를 지연시켜 시급한 잡 태스크를 할당하는 단계를 포함하며,
   상기 가용 노드가 존재하는 경우 잡 태스크를 할당하는 단계는, 상기 태스크 할당부가:
   ⒜ 긴급 큐에 잡이 존재하는지 판단하는 단계,
   ⒝ 상기 긴급 큐에 잡이 존재하면, 상기 가용 노드가 데이터 지역성을 만족하는지 여부를 판단하는 단계,
   ⒞ 상기 ⒝단계 판단 결과, 상기 데이터 지역성을 만족하면, 상기 가용 노드에 부하가 존재하는지 여부를 판단하는 단계 및
   ⒟ 상기 ⒝단계 판단 결과, 상기 데이터 지역성을 만족하지 않으면, 복제본 노드를 검색하여 상기 복제본 노드에 부하가 존재하는지 여부를 판단하는 단계를 포함하는 데드라인 부여된 작업의 분산 처리 성능 향상을 위한 맵리듀스 스케쥴링 방법.
   
5. 삭제
6. 청구항 제4항에서,
   ⒠ 상기 ⒞단계 판단 결과, 상기 가용 노드에 부하가 존재하면, 복제본 노드를 검색하여 상기 복제본 노드에 부하가 존재하는지 판단하는 단계,
   ⒡ 상기 ⒠단계 판단 결과, 상기 복제본 노드에 부하가 존재하면, 상기 가용 노드의 태스크들 중 데드라인 여유가 있는 태스크들을 모두 정지하고 상기 가용 노드에 상기 긴급 큐의 잡을 할당하는 단계를 포함하는, 데드라인 부여된 작업의 분산 처리 성능 향상을 위한 맵리듀스 스케쥴링 방법.
   
7. 청구항 제6항에서,
   상기 데드라인 여유가 있는 태스크는, 하기 수식 1을 만족하는 태스크인, 데드라인 부여된 작업의 분산 처리 성능 향상을 위한 맵리듀스 스케쥴링 방법.
   (수식 1)
   

   

   
   단, T_th는 미리 결정된 임계치, T_d는 잡에 부여된 데드라인, T_P는 잡의 예상 완료 시간, T_io는 하나의 데이터 청크를 I/O(Input/Output)하는 평균 시간이다.
   
8. 청구항 제4항에서,
   ⒢ 상기 ⒟단계 판단 결과, 상기 복제본 노드에 부하가 존재하지 않으면, 상기 복제본 노드에서 잡을 처리하고, 상기 복제본 노드에 부하가 존재하면, 상기 복제본 노드가 가용 상태가 될 때까지 대기할 것인지 여부를 판단하는 단계,
   ⒣ 상기 ⒢단계 판단 결과, 상기 복제본 노드가 가용 상태가 될 때까지 대기하지 않을 것으로 판단되면, 상기 복제본 노드에서 잡을 처리하고, 상기 복제본 노드가 가용 상태가 될 때까지 대기할 것으로 판단되면, 상기 ⒞단계로 진행하는 단계를 포함하는, 데드라인 부여된 작업의 분산 처리 성능 향상을 위한 맵리듀스 스케쥴링 방법.
   
9. 청구항 제8항에서,
   상기 복제본 노드가 가용 상태가 될 때까지 대기할 것이지 여부는,
   하기 수식 2, 수식 3, 수식 4를 이용하여 수식 2를 만족하는 경우, 상기 복제본 노드가 가용 상태가 될 때까지 대기할 것으로 판단하고, 수식 2를 불만족하는 경우, 상기 복제본 노드가 가용 상태가 될 때까지 대기하지 않을 것으로 판단하는, 데드라인 부여된 작업의 분산 처리 성능 향상을 위한 맵리듀스 스케쥴링 방법.
   (수식 2)
   

   

   
   (수식 3)
   

   

   
   (수식 4)
   

   

   
   단, T_wx는 필요한 데이터를 가진 노드가 가용 노드가 될 때까지 대기하여 해당 노드에서 태스크를 처리할 경우 태스크 예상 완료 시간, T_p는 필요한 데이터를 가진 노드가 가용 슬롯이 생기는 평균 주기, T_io는 청크 하나를 I/O하는데 소비되는 평균 시간, T_ex는 해당 잡의 태스크를 실행하는데 소요되는 평균 시간, T_tx는 필요한 데이터를 복제본 노드에서 기존 가용 노드로 전송하여 수행할 경우의 태스크 예상 완료 시간, T_trans는 청크 하나를 네트워크로 전송하는 평균 전송 시간이다.

Images