[발 번역] HBase I/O – HFile

해당 블로그는 KT UCloud의 지원을 받고 있습니다.

Introduction

아파치 HBase 는 하둡 오픈 소스 패밀리이며, 분산되고, 랜덤, 실시간 읽고/쓰기에 적합한 스토리지 매니저입니다.

엥 잠시만요? 랜덤 읽기, 실시간 읽고 쓰기가 된다구요?

어떻게 그게 가능하죠? Hadoop은 단지 연속된 읽고/쓰기만 지원하고, 배치 프로세싱을 위한 시스템 아닌가요?

예, 우리는 같은 것에 대해서 이야기를 하고 있습니다. 그리고 몇 단락 뒤에서, 어떻게 HBase가 Random I/O를 제공하는지, 데이터를 어떻게 저장하는지, HBase의 HFile format 의 변화에 대해서 설명하겠습니다.

Hadoop I/O file formats

Haddop은 Key/Value 를 추가할 수만 있는 SequenceFile[1] file format 로 시작했고, 삽인된 데이터의 변경이나, 삭제가 불가능합니다. 오직 추가 동작많이 허용되었습니다. 만약 특정한 키를 찾기를 원한다면, 키를 발견할 때 까지, 전체 파일을 읽어야 합니다.

 음, 당신도 알다시피, 순차적으로 읽고/쓰는 걸 따르도록 강제하고 있는데, 어떻게 HBase에서 랜덤하게 데이터를 만들고, 빠르게 읽고 쓸수 있는거죠?

해당 문제를 풀도록 돕기 위해서, 하둡은 MapFile 이라는 다른 파일 포맷을 가지고 있습니다. MapFile은 SequenceFile의 확장 형태이며, 실제로, 두 개의 SequenceFile을 가진 디렉토리입니다. 각각 “/data” 라는 데이터 파일과 “/index” 라는 index 파일입니다.  MapFile은 정렬된 key/value 쌍을 붙이고,  매 N개의 key들 마다(N은 설정가능한 값입니다.) index와 key와 offset이 저장됩니다. 모든 데이터를 실제로 스캔하는 대신에, 훨씬 적은 개수의 index를 먼저 살펴본 다음에, 필요한 블럭을 발견하면, 그 때, 실제 데이터로 바로 이동할 수 있습니다.

MapFile은 key/value 쌍을 빨리 찾을 수 있어서 좋지만, 두 가지 의문이 생깁니다.

  • 어떻게 key/value 쌍을 지우거나 업데이트 해야할까요?
  • 데이터의 입력이 정렬되어 있지않으면, MapFile을 사용 못할 꺼 같은데요?

HBase & MapFile

HBase Key는 row key, column family, column qualifer, timestamp 그리고 type 으로 구성되어 있습니다.

HBase Key

key/value 쌍을 지울때의 문제점을 해결하기 위한 아이디어는, “type” 속성을 삭제됨(tombstone markers)이라고 표시를 하는 것입니다.(역자 주: 보통 이것을 lazy delete 라고 부르고, 성능을 위해서, 특정 시점까지는 표시만 하고 특정 시점에, 데이터를 재구성하든가 해서 이런 부분을 삭제하는 방식을 일반적인 파일시스템이나, DB엔진에서 많이 사용합니다.), key/value 쌍을 바꾸는 문제를 해결하기 위해서, 단순히 timestamp가 뒤에 것만 가져오면 되는 문제입니다.( 즉, 여러개 가 있을 경우, 파일의 끝에 가까운데 위치한 값이 올바른 값입니다. 추가만 가능하다는 것은 파일의 끝에 가장 마지막 입력값이 있다는 것을 의미합니다.)(역자 주: 이 말은 데이터의 수정이 있을 때 마다, 실제로는 새로운 데이터가 생긴다는 것과 동일합니다. 그래서 여러 개의 같은 키와 데이터가 존재하게 되는데, 이 때, 단순히 timestamp가 마지막 것을 선택한다고 생각하시면 될 것 같습니다. 그럼 당연히 저장공간이나 속도면에서 문제가 발생할 것입니다. 이것은 뒤에 설명하는 “compaction” 이라는 것을 통해서 해결하게 됩니다.)

“정렬 되지 않은” key 문제를 해결하기 위해서, 마지막으로 추가된 key/value 쌍을 메모리에 유지합니다.  임계값에 다다랐을 때, HBase는 그것을 MapFile에 저장합니다. 이 방법으로 key/value 가 정렬된 채로 MapFile에 추가됩니다.

HBase 는 정확히 이렇게 동작합니다.[2] table.put()을 이용하여 값을 추가할 때, key/value 는 MemStore에 추가됩니다.( MemStore 는 정렬된 ConcurrentSkipListMap 입니다. ) memstore 의 임계값에 다다르거나( hbase.hregion.memstore.flush.size ), RegionServer 가 너무 많은 메모리를 memstore 에 사용하고 있으면( hbase.regionserver.global.memstore.upperLimit ) 데이터는 새로운 MapFile 로써 디스크에 저장됩니다.

각각의 flush 의 결과는 새로운 하나의 MapFile 입니다. 이것은 하나의 키를 찾고자 할 때 하나 이상의 파일을 검색해야 한다는 것을 의미합니다. 많은 리소스를 필요로 하게 되고, 잠재적으로 느려질 수 있습니다.

get이나 scan이 실행되는 시간마다, HBase는 결과를 찾기 위해서 각 파일을 스캔합니다. 너무 많은 파일을 여는 것을 피하기 위해서, 특정 개수 이상(hbase.hstore.compaction.max) 의 파일에 도달하는 것을 특정 스레드가 확인합니다. 그리고 compaction 이라고 불리는 과정을 통해서 여러 MapFile 들을 하나로 합치기를 시도합니다. file 머지의 결과로 새로운 큰 파일 하나가 생성됩니다.

HBase는 두 종류의 compaction을 가지고 있습니다.  하나는 “minor compaction”이라고 불리고, 단지 두 개 이상의 조그만 파일들을 하나로 합칩니다. 다른 하나는 “major compaction”이라고 불리며, Region 안의 모든 파일을 몇 가지 청소를 수행하며 머지합니다. major compaction 시에, 삭제되었다고 표시된 key/value를 실제로 삭제하고, 새로운 파일에는 tombstone maker도 가지지 않고, 중복된 key/value 도 제거됩니다.(replace로 인해서 발생했던)

version 0.20 까지는 HBase는데이터를 저장할 때 MapFile format을 사용하고 있지만 0.20 부터는 새로운 HBase에 특화된 MapFile 역시 포함하고 있습니다.(HBASE-61)

HFile v1

HBase 0.20 에서는 MapFile 은 HFile로 변경되었습니다. HFile은 HBase를 위해서 고안된 특별한 map file 구현입니다. 아이디어는 MapFile과 상당히 유사합니다. 그러나, 단순한 key/value 파일이 아니라 metadata의 지원이나 와 index 가 동일한 파일에 보관되는  특별한 기능을 더 추가하였습니다.

데이터 블럭은 MapFile 처럼 실제 key/value 쌍을 저장하고 있습니다. 각각의 “블럭 close 동작”은 index에 처음 key를 저장하고, index는 HFile 이 close 될 때 해당 index가 저장되게 됩니다.

HFile Format은 두 개의 “metadata” 블록 형식을 추가했습니다. Meta 와 FileInfo 가 그것입니다. 이 두 key/value 블럭은 file이 close 될 때 저장됩니다.

Meta 블럭은 다수의 데이터들의 키를 String으로 저장하기 위해서 디자인되었고, 반면 FileInfo 는 Simple Map 형태로 key와 value 들이 byte-array 형태로 작은정보를 저장합니다. RegionServer 의 StoreFile은 Meta-Block들을 Bloom Filter를 저장하기 위해서 사용하고 FileInfo는 MaxSequenceId, Major Compaction Key, Timerange info 등을 저장하기 위해서 사용합니다. 해당 정보는 키가 존재하지 않을 때, (bloom filter), 또는 만약 파일이 너무 오래되거나(Max SequenceId), 파일이 너무 새거라서(Timerange) 우리가 원하는 데이터를 담고 있지 않아서 파일을 읽는 것을 피할 때 유용합니다.(역자 주: floom filter는 일종의 캐시로, 해당 키가 존재하는지 아닌지 판별할 때 사용하게 됩니다. bloom filter의 특징은 해당 키가 존재한다고 응답이 와도, 실제로 존재하지 않을 수 있지만, 해당 키가 없다고 대답하면, 확실히 데이터가 존재하지 않는다라는 특성이 있습니다. 즉, 일반적으로 bloom filter를 메모리에 저장해두고, 키가 존재한다고 하면, 메모리나 디스크를 찾는 것이고, 없다고 하면, 아예 찾을 필요가 없어져서 디스크에 접근할 필요가 없어지는 것입니다.)

HFile v2

HBase 0.92 에는 다수의 데이터가 저장될 때, 성능 향상을 위해서  HFile Format 이 조금 변경되었습니다.(HBASE-3857) HFile v1에서의 큰 문제점 중에 하나는 모든 index들과 큰 Bloom Filter들을 메모리에 올려야 할 필요가 있을 때 였습니다. 이 문제를 해결하기 위해서 v2에서는 multi-level index와, block-level Bloom Filter를 도입하였습니다. 그 결과 HFile v2는 속도, 메모리, 캐시 사용에서 발전된 모습을 보여줍니다.

v2의 주요 기능은 “inline blocks” 입니다. 하나의 큰 Index와 Bloom Filter를 가지는 대신에, Index 와 Bloom Filter 를 블럭마다 쪼개는 것입니다. 이 방법으로 메모리에 필요한 만큼만 유지할 수 있습니다.

index 가 block level 로 변경된 후에,  multi-level index를 가지게 되었습니다. 이는 각각의 블럭마다 자기 자신의 index(leaf-index)를 가진다는 의미입니다. 각 블럭의 마지막 key는 multilevel-index 를 b+ tree 처럼 만들기 위해서 유지됩니다.(역자 주: b+ tree와 b tree를 보면 b+ tree는 range scan이 가능합니다. 해당 블럭의 마지막 데이터에서 다음 블럭 정보를 가지고 있다고 보시면 될 것 같습니다.)

블럭 헤더는 몇 가지 정보를 포함하고 있습니다. “Block Magic” 이라는 필드에서 바뀐 “Block Type” 이라는 필드는 “Data”, “Leaf-Index”, “Bloom”, “MetaData”, “Root-Index” 등등의 블럭의 내용을 표시하기 위해서 사용합니다. 또한, 압축 사이즈/원본 사이즈/이전 블럭의 위치를 가지는 세 가지 필드를 앞뒤 이동을 빠르게 하기 위해서 추가적으로 가지고 있습니다.

Data Block Encodings

key들은 정렬되고, 그래서 매우 유사합니다. 그래서 공용 목적의 알고리즘이 하는 것 보다 좀 더 좋은 압축을 하도록 디자인 하는 것이 가능합니다.

HBASE-4218 에서 해당 문제를 해결하기 위해서 시도하였고, HBase 0.94 에서는 Prefix 와 Diff Encoding 이라는 두 가지 다른 알고리즘 중에서 선택이 가능합니다.

Prefix Encoding의 주요 특징은 row 들이 정렬되고, 일반적으로 같은 이름으로 시작하면 공통적인 Prefix를 오직 한번만 저장하는 것입니다.

Diff Encoding은 해당 컨셉을 좀 더 확장했습니다. 불확실한 연속된 키 대신에, Diff Encoder는 각각의 key 를 좀 더 좋은 방법으로 압축하기 위해서 나눕니다. 이것은 하나의 column family는 한번에저장되기 때문에 가능합니다.  key 길이나, value의 길이, type 이 하나라도 같으면 해당 항목은 누락시킵니다. 또한 압축을 높이기 위해서, timestamp는 이전 값과 차이값만 저장합니다.

쓰기와 스캔작업이 느려지지만, 좀 더 데이터를 캐시하기 위해서 해당 기능은 기본적으로는 꺼져있다는 것을 기억하십시오. 해당 기능을 사용하기 위해서는 DATA_BLOCK_ENCODING = PREFIX | DIFF | FAST_DIFF 라고 table info에 설정해야 합니다.

HFile v3

압축을 높이기 위해서 HFile Layout을 재설계 하자는 제안이 HBASE-5313에 포함되었습니다.

  • 블럭의 앞부분에 모든 Key들을 한번에 묶어서 저장하고, 모든 Value들을 한번에 묶어서 block의 뒷부분에 저장합니다. 해당 방법으로, key와 value에 서로 다른 알고리즘을 key와 value에 적용할 수 있습니다.
  • timestamp의 첫번째 값을 long 대신에 VInt를 사용하고 XOR 을 이용해서 압축합니다.

또한 컬럼 형식의 포맷이나 컬럼 인코딩 방법이 연구중에 있습니다. AVRO-806 for a columnar file format by Doug Cutting 를 살펴보시기 바랍니다.

알다시피, 진화의 경향은 파일 안에 어떤 내용이 있는지 더 많이 알아야 한다는 것입니다. 좋은 압축을 하거나, 더 좋은 위치에 배치하는 것은 디스크에 적은 데이터를 읽고 쓴다는 것입니다. 적은 I/O는 더 빠른 속도를 의미합니다.

[1] http://www.cloudera.com/blog/2011/01/hadoop-io-sequence-map-set-array-bloommap-files/

[2] http://www.cloudera.com/blog/2012/06/hbase-write-path/