Hive LLAP (Interactive SQL) 이란?

참고 : https://cwiki.apache.org/confluence/display/Hive/LLAP

LLAP

Live Long And Process라고 Hive 2.0에서 추가된 기능이다.

Overview

Hive는 최근 수년 내에 커뮤니티의 활발한 활동의 결과(Tez와 Cost-based-optimization) 덕에 상당히 빨라질 수 있었다.  Hive가 다음 단계로 나아가기 위해서는 아래와 같은 것들을
필요했다.
 - Asynchronous spindle-aware IO
 - Pre-fetching and caching of column chunks
 - Multi-threaded JIT-friendtly operator pipelines

LLAP는 hybrid 실행 모델을 제공한다. 그 것은 HDFS Datanode와 직접적으로 통신하는 long-lived daemon과 긴말하게 통합된 DAG 기반 framework로 이뤄진다.
캐시, pre-fetching, 쿼리 프로세싱, 접근 관리와 같은 기능들이 daemon에서 수행된다. 또한 작은(짧은) 쿼리들은 대개 daemon에서 직접 수행되며, 무거운 작업은 일반적인 YARN 컨테이너를 통해 수행된다.

Persistent Daemon

캐싱과 JIT 최적화, 그리고 시작 비용을 없애기 위해, daemon이 클러스터의 worker 노드에서 돌고 있다. 해당 daemon은 I/O, 캐싱, query fragment execution을 수행한다.
 - Stateless
 - Recovery/resilency
 - Communication between nodes

Execution Engine (실행 엔진)

LLAP는 기존의 프로세스 기반의 Hive execution 모델에서 수행되므로, 기존 Hive의 확장성과 다재다능함(versatility)을 그대로 유지한다.
 - The ademons are optional. LLAP가 배포되어 동작 중인 상태에서도 Hive는 LLAP 없이 수행될 수 있다.
 - External orchestraction and execution engines. LLAP는 MapReduce나 Tez 같은 실행 엔진이 아니다. LLAP의 모든 작업 수행은 기존의 Hive 실행 엔진(Tez와 같은)에 의해 스케줄되고 관리된다. LLAP 지원 수준은 각자의 실행 엔진에 따라 다르다. 현재는 Tez를 지원하며, MapReduce는 계획에 없다.
 - Partial execution. LLAP daemon에 의해 수행 된 작업 결과는 쿼리에 따라 Hive 쿼리 결과의 일부를 구성하거나 외부 Hive 작업에 전달 될 수 있다.
- Resourece Management. 여전히 YARN이 리소스 할당 및 관리를 책임진다. JVM 메모리 설정의 한계를 피하기 위해 큰 작업(group by, joins)을 위한 버퍼나, 캐시된 데이터들은 off-heap에 저장된다. 이 방법은 작업 부하에 따라 추가적인 리소스 사용을 가능케 한다.

Query Fragment Execution

부분 실행을 위해 LLAP 노드들은 "쿼리 조각(query fragments)"들을 나누어 수행하도록 되어 있다. 여기서 쿼리 조각은 필터, projection, 데이터 변형, 부분 취합, 정렬, bucketing, hash join/semi-join 등의 작업이 될 수 있다.
 - Parallel execution. 하나의 LLAP 노드는 여러 쿼리 조각을 병렬처리 할 수 있다.
 - Interface. 유저는 LLAP 노드들에 client API를 통해 직접 접근이 가능하다.

I/O

Caching

LLAP daemon은 입력 파일의 메타 데이터 뿐 아니라, 데이터 자체도 캐시한다. 메타데이터와 인덱스 정보는 자바 객체로 프로세스에 저장되며, 캐시된 데이터는 off-heap에 저장된다.
 - Eviction policy. 캐치 교체 정책은 테이블 스캔을 통한 작업부하 분석을 통해 조정된다. 기본적으로는 LRFU와 같은 정책이 사용되며, pluggable하다.
 - Caching granularity. Column-chuck의 크기가 캐시의 데이터 단위가 된다. 이것으로 프로세싱 오버헤드와 스토리지 효율성 간의 조정이 가능하다. 파일 포맷과 실행 엔진에 따라 해당 청크의 세분성(granularity)가 정해진다.

Workload Management

YARN을 통해 작업 부하에 따른 자원을 관리한다. 실행엔진이 YARN으로부터 할당 받은 자원을 LLAP나 Hive executor를 새로 띄우기 위해 위임할 수 있다.

ACID Support

LLAP는 transactions을 인지한다. 테이블의 정상적인 상태를 위해 수행되는 델타 파일에 대한 머지가 일어난 후에 데이터 캐싱이 수행된다.
여러 버전이 가능하며 그 중에 사용될 버전을 선택하여 캐시를 요청할 수 있다. 이것으로 얻는 장점은 머지를 비동기로 수행하고 한번에 데이터를 캐시할 수 있다는 점이다.

Security

LLAP 서버는 태생적으로 파일 단위보다도 더 세분화된 레벨의 access control이 가능하다. 데몬이 처리 중인 컬럼과 레코드를 알고 있기 때문에 이런 오브젝트에 대한 정책 적용이 가능하다.

Monitoring

LLAP 모니터링에 대한 설정은 Slider가 사용하는 templates.py에 들어있다. (resources.json, appConfig.json, metainfo.xml)
LLAP Monitor Daemon은 LLAP 데몬과 마찬가지로 YARN 컨테이너에서 수행되며, 같은 port로 리슨하고 있다.
LLAP Metrics Collection Server는 모든 LLAP daemon들로부터 주기적으로 JMX metric 정보를 수집한다.

HDP 기준) Ambari Tez view를 통해 쿼리 수행 현황을 파악할 수 있다.

Web Services

) 기본적인 metrics 정보는 15002(default) 포트를 통해 web UI를 제공한다.

HIVE-9814 introduces the following web services:

JSON JMX data - /jmx
JVM Stack Traces of all threads - /stacks
XML Configuration from llap-daemon-site - /conf 

HIVE-13398 introduces the following web services:

LLAP Status - /status
LLAP Peers - /peers 

SLIDER on YARN Deployment

LLAP can be deployed via Slider, which bypasses node installation and related complexities (HIVE-9883).

참고하면 더 좋은 slideshare

https://www.slideshare.net/Hadoop_Summit/llap-longlived-execution-in-hive

Tunings

https://docs.hortonworks.com/HDPDocuments/HDP2/HDP-2.6.2/bk_hive-performance-tuning/content/ch_hive-perf-tuning-intro.html

LRFU (Least Recently/Frequently Used) 이란?

LRFU (Least Recently/Frequently Used)

Adaptive Cache Replacement Policy

캐시를 통해 데이터 처리 성능 향상의 꾀하는 경우에 캐시를 어떻게 유지하고 새로 교체해줄 것인 가에 대한 정책 중에 LRFU라는 게 있어서 찾아보는 중이다.
해당 기법을 본 건 LLAP Caching 부분을 읽다가 였다. (https://cwiki.apache.org/confluence/display/Hive/LLAP)

그 전에 알면 좋을 주요 교체 알고리즘으로 FIFO, LRU, LFU가 있다.
간단히 소개하면 아래와 같다.

FIFO (First In, First Out)
 - 가장 오래된 정보를 삭제한 자리에 새로운 정보를 저장하는 식이다.

LRU (Least Recently Used)
 - 가장 오래 사용되지 않은 정보를 교체한다.

LFU (Least Frequently Used)
 - 가장 빈도수가 적게 사용된 정보를 교체한다.

문제는 LRFU인데, 검색해보면 생각보다 나오는 내용이 없다.


먼저 wikipedia에서 Cache replacement policies를 찾아봤는데, 비슷한게 있었다.
그 내용을 살펴보면 아래와 같다.
https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_Frequent_Recently_Used_(LFRU)_[11]

LFRU (Least Frequent Recently Used)

LFU와 LRU의 장점을 합친 교체 정책으로써, 정보 중심 네트워크(Information-Centric Networking, ICN), 컨텐츠 전송 네트워크(CDN), 일반적인 형태의 분산 네트워크와 같은 캐시 어플리케이션에 적합하다. 

LFRU에서는 캐시가 2 부분으로 나눠지는데, privileged와 unprivileged 파티션으로 불린다. privileged 파티션에선 LRU를 적용하고, unprivileged 파티션에는 ALFU(거의 LFU?)를 적용한다는 것으로 예를 들면 다음과 같다. 

먼저, unprivileged에서 적은 횟수로 사용된 정보를 버리고, privileged 파티션에서 가장 오래된 정보가 unprivileged로 이동한다. 그리고 새로운 정보가 privileged의 빈자리로 들어온다.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 

위와 같은 내용이었는데, 문제는 순서가 다르다. LRFU가 아니라 LFRU인데.

그래서 조금 더 찾아봤더니 96년도에 서울대에 쓴 논문이 검색된다. 

LRFU (Least Recently/Frequently Used) Replacement Policy: A Spectrum of Block Replacement Policies (1996)

내용을 요약해보면 아래와 같다. 이 논문에서 block을 하나의 저장 및 교체 단위로 본다.

LRFU (Least Recently/Frequently Used)

LFU는 작업량의 추세를 반영할 수 없다. 예를 들면, 예전에는 자주 쓰이다가 현재는 안 쓰이는 block과 최근에 들어서야 점점 더 많이 쓰이기 시작한 block이 있을 때, 전자를 교체 대상으로 삼을 것이다. 구현 관점에서 보면, 보통 Priority queue가 사용되므로 시간 복잡도는 O(log n)을 나타낸다.
반면 LRU는 가장 최근에 남아있는 데이터에 대한 빈도만을 통해 선택을 해야 한다. 결과적으로 제대로된 빈도수 확인이 안될 수 있다. 하지만 다른 정책에 비해 패턴에 의한 변화를 줄 수 있는 형태이며 매우 효율적으로 동작한다. 하나의 연결 리스트로 구현할 수 있으므로, 시간 복잡도는 상수 O(1)이다.

두 가지의 장점을 합쳐 과거의 모든 block의 빈도(frequency)와 최신성(recency)을 둘다 보고 교체 대상을 선정할 수 있도록 하는 것을 Least Recently/Frequently Used(LRFU)라고 부를 것이다. 가중치에 따라 해당 정책은 스펙트럼의 형태로 나타나며 시간 복잡도는 O(1)과 O(log n)의 사이가 될 것이다.
LRFU 정책은 CRF(Combined Recency and Frequency)라는 값을 통해 해당 블럭의 재사용성을 판단하며, 가장 작은 값의 block이 교체 대상이 된다.

자세한 CRF 계산 과정은 논문에서 확인할 수 있다.
그 중 인상적인 부분은 CRF를 계산하기 위한 공식에서 사용되는 F(x)의 parameter인 λ의 범위를 0과 1사이에서 선택하며, 그 값에 따라 LFU와 LRU의 스펙트럼 어딘가에 위치하게 된다는 점이었다.
F(x) = (1/2) ^(λx)

또한 상관관계가 있는 기간(correlated period)을 하나로 묶어 계산할 수 있는 형태에 대한 계산 변형도 가능하다. Database 시스템에서는 data access에 대한 frequency와 recency보다는 상위 작업인 transaction 레벨에서 미래 예측이 더 용이하다고 보고, Gc(x)을 정의해서 사용할 수 있도록 한다.

CRF의 계산을 매번 가지고 있는 전체 block에 대해 수행하는 이슈는, 자료구조 heap을 통해 피해갈 수 있도록 상세한 Implementation 가이드를 포함한다. 결과적으로 Implemetation은 가중치에 따라 연결 리스트와 heap(Priority queue)로 나뉘어 계산된다고 볼 수 있다.

작업량(workload)의 특성에 따라 parameter λ와 c를 변형하여 addaptive 정책을 구성할 수도 있다.