Journal Archive

빅데이터는 인공지능, IoT(사물인터넷), 생명공학 기술 등 정보통신기술(ICT)의 융합으로 이루어지는 차세대 산업혁명인 4차 산업혁명의 핵심 기반 기술이다. 스마트 팩토리, 스마트 팜, 웹서버 로그 등 다양한 센서들로부터 발생되는 방대한 양의 빅데이터를 효과적으로 처리/분석하여 자동화 또는 개인화 서비스를 하기 위해서는 실시간 빅데이터 처리 및 분석이 필수적이다. 방대한 양의 빅데이터를 하나의 서버를 증설하는 방식(Scale-up)으로 처리 용량을 증설하는 것은 비용적인 면이나 확장성 측면에서 한계가 존재하므로, 대부분의 빅데이터 처리 기술은 분산 시스템을 기반으로 한다. 빅데이터 초창기에는 맵-리듀스(Map-Reduce)와 하둡 분산 파일 시스템(HDFS)으로 구성된 하둡(Hadoop)[1] 분산 시스템을 중심으로 발전하였다. 하지만 디스크 기반 처리로 인한 느린 성능과 단일 네임노드로 인한 SPOF (Single Point Of Failure) 등의 문제들로 인해, 최근에는 Apache Spark[2], Storm[3], BigStream[4] 등 실시간 빅데이터 분석을 위한 메모리 기반의 분산 시스템들이 더 활발히 개발되고 연구되고 있다.

블룸 필터(Bloom Filter)[5]는 원소가 집합에 속하는지 여부를 검사하는데 사용되는 확률적 자료 구조로써, 데이터베이스 연산 최적화[6][7], 네트워크 라우팅 최적화[8][9], 침입 탐지[10][11] 등 많은 분야에서 탐색 공간 최소화를 통한 성능 개선을 위하여 많이 활용되었다. 원소들이 집합에 속해있는지 여부를 저장하는 비트테이블이 존재하고, 해쉬 함수를 이용하여 원소의 값에 대항하는 비트를 1로 갱신한다. 블룸 필터는 집합 내 원소의 개수(카디널리티), 긍정오류율, 해시 함수의 개수, 비트테이블의 크기가 서로 영향을 미친다. 데이터의 카디널리티와 긍정오류율이 주어지면, 주어진 긍정오류율 이하를 보장하기 위하여 비트테이블의 크기와 해시 함수의 개수가 정해진다. 하지만 데이터의 특성을 미리 알 수 없거나 센서 스트림과 같이 데이터가 계속해서 발생되는 응용분야에서는 긍정오류율 보장이 어렵다. 왜냐하면 처음에 설정된 카디널리티보다 실제 데이터의 카디널리티가 더 크게 되면 긍정오류율을 만족시키기 위해서는 비트테이블의 크기를 확장해야하기 때문이다. 비트 테이블의 확장 연산은 기존의 모든 데이터들을 대상으로 재구성 연산을 수행하여야 하므로 연산 비용이 매우 크다. 이러한 단점을 개선하기 위하여 동적 블룸 필터(DBF, Dynamic Bloom Filter)[12]는 긍정오류율의 조건을 만족시키면서 동적으로 블룸 필터를 확장시키는 방법을 제안한다. 실제 데이터의 카디널리티가 주어진 카디널리티 값보다 커지면 블룸 필터를 재구성하는 대신, 기존의 1차원 비트테이블을 N차원의 비트테이블로 표현함으로써, 블룸 필터를 동적으로 확장하는 방식이다. 하지만 DBF[12]는 데이터 적재와 탐색 비용이 O(N×k)이므로, O(k)인 정적 블룸 필터(SBF, Static Bloom Filter)[5]에 비해 데이터 삽입 및 탐색 비용이 많이 드는 단점이 존재한다.

스마트 팩토리, 스마트 팜, 스마트 그리드와 같은 IoT 분야나 대용량 로그 분석 등 빅데이터의 주요 응용 분야에서 발생하는 데이터들은 데이터의 특성(카디널리티, 데이터 분포)을 미리 알 수 없으며, 한 번 발생된 데이터는 변경되지 않으며, 발생 시간의 순서대로 데이터가 적재된다. 본 논문은 이와 같은 빅데이터 응용 분야의 특성들을 고려하여 DBF 기반의 효율적인 블룸 필터 방법을 제안한다. 기존의 빅데이터 처리 플랫폼[13][14]에서도 탐색 공간 최소화를 통한 성능 향상을 위하여 블룸 필터를 활용하지만 SBF[5]를 활용하여 긍정오류율을 최소화하는 것이 주목적이다. 하지만 빅데이터 분야에서는 긍정오류율보다 실시간으로 발생되는 방대한 양의 데이터를 지연 없이 적재해야 하며, Spark[2], Storm[3]과 같은 인-메모리 처리 엔진의 경우에는 저장 공간 또한 효율적으로 활용하여야 하므로, 적재 성능과 저장 효율성이 고려되어야 한다. 하지만 적재 성능과 저장 효율성은 trade-off 관계이므로 본 논문에서는 적재 성능 중심의 블룸 필터 방식(b-DBF)과 저장 효율성 중심의 블룸 필터 방식(s-DBF)을 제안한다. 많은 빅데이터 분석 플랫폼[2]-[4][13][14]에서 데이터의 효율적인 저장과 처리를 위하여 이미 블룸 필터 기법들을 활용 중이므로 본 연구 결과를 기존 플랫폼에 쉽게 적용할 수 있다. 이를 통해 빅데이터 플랫폼의 성능 향상에 많은 영향을 끼칠 수 있을 것으로 기대한다.

SBF[5]는 그림 1(a)와 같이 집합 = {x₁, x₂, ...x_n}의 항목들의 소속 여부를 m 비트로 이루어진 비트테이블에 저장하고, 항목의 집합 소속 여부를 검사하는데 사용되는 확률적 자료 구조이다. 비트테이블은 초기에는 모두 0으로 표기되며, X의 각각의 항목에 대해 해시의 결과값이 {1,2,...,m }인 k개의 해시 함수(h₁, h₂, h_k)를 적용하여 해당하는 비트테이블의 비트를 1로 갱신한다. 예를 들어, 크기가 10인 비트테이블이 존재하면, 어떤 원소의 값을 해싱 함수를 통해서 1~10까지의 값으로 변환한 후, 해당 자리의 비트를 1로 설정한다. 이를 통해 어떤 원소가 주어졌을 때, 해당 원소가 집합에 속해 있는지 여부를 판단할 수 있다. 블룸 필터에 의해 어떤 원소가 속해 있지 않은데, 속해있다고 판단하는 긍정오류(False Positive Error)[5]는 존재하지만, 반대로 어떤 원소가 속해있는데 속해있지 않다고 판단하는 부정 오류(False Negative Error)는 존재하지 않는다. 블룸 필터는 집합 내의 항목의 개수(카디널리티, n), 긍정오류율(p), 해쉬 함수의 개수(k), 비트테이블의 크기(m)들을 모두 정의가능하며, 집합 내 원소의 숫자가 증가할수록, 비트테이블의 크기가 작을수록, 해시 함수의 개수가 작을수록, 긍정오류율도 증가한다. 긍정오류율(p)은 아래와 같이 계산될 수 있다[5].

Fig. 1. 
Static bloom filter and counting bloom filter

카운팅 블룸 필터[15]는 원소 삭제가 불가능한 블룸 필터의 문제점을 보완하기 위해서 고안되었다. 블룸 필터는 원소의 소속 여부를 1 비트로 표현하므로, 해당 원소가 몇 개가 속해있는지를 알 수 없어 데이터 삭제가 불가능한 반면, 카운팅 블룸 필터는 그림 1(b)와 같이 X 비트를 사용하여 원소의 개수도 표현함으로써 원소의 삭제가 가능한 반면, [5]에 비해 더 많은 저장 공간이 필요하다.

SBF는 집합 내 원소의 개수(카디널리티), 긍정오류율 등 정해진 설정값에 따라 비트테이블의 크기가 정해진다.

처음에 정의된 카디널리티와 실제 카디널리티의 차이가 발생하면 긍정오류율의 조건을 만족시키기 위해서는 비트테이블의 크기를 확장해야 하며, 이는 기존의 모든 데이터들을 대상으로 재구성 연산을 수행해야 하므로 연산 비용이 매우 크다. 그러므로 데이터의 특성을 미리 알 수 없는 응용분야에서도 블룸 필터를 효과적으로 활용할 수 있도록 DBF[12]가 제안되었다. DBF는 기존의 1개의 1차원 비트테이블 대신 N개의 비트테이블로 표현함으로써, 블룸 필터를 동적으로 확장하는 방식이다. 블룸 필터를 갱신하면서 현재까지 저장된 데이터들의 카디널리티를 함께 갱신한다. 갱신된 카디널리티가 한계치(Threshold)를 넘어서면 신규 블룸 필터를 생성하는 방식으로 비트테이블을 N개로 확장한다. 각 블룸 필터는 카운팅 블룸 필터[15]를 기반으로 구현되어 있다.

최근 많은 분야에서 빅데이터의 실시간 처리 및 분석을 위하여 블룸 필터를 많이 활용하지만 시스템 요구사항이나 빅데이터의 특성들을 잘 반영하지 못하고 있다. 빅데이터를 위한 블룸 필터는 방대한 탐색 공간을 최소화하기 위하여 사용되지만, 그보다 실시간으로 발생되는 방대한 양의 데이터를 지연 없이 적재해야 하며, 인-메모리 처리 엔진[2][3]의 경우에는 저장 공간 또한 효율적으로 활용하여야 한다. 그러므로 본 논문에서는 블룸 필터의 삽입 비용과 저장 비용을 고려한 DBF 기법들을 제안한다. 방대한 양의 데이터가 계속적으로 발생되고 카디널리티와 같은 데이터의 특성을 미리 규정지을 수 없는 특성을 고려하여, DBF로 구현하였다. 기존의 DBF[12]는 데이터의 삭제를 위하여 CBF[15]를 기반으로 구현되었지만, 데이터의 삭제가 변경이 거의 발생하지 않는 빅데이터의 특성을 고려하여 본 논문은 SBF[5] 기반으로 구현하여 [12]에 비해 저장 효율성 측면에서 우세하다. 많은 빅데이터 분석 플랫폼[2]-[4][3][4]에서 데이터의 효율적인 저장과 처리를 위하여 이미 블룸 필터 기법을 활용 중이므로 본 연구 결과를 기존 플랫폼에 쉽게 적용할 수 있으며, 이를 통해 빅데이터 분석 플랫폼의 성능 향상에 많은 영향을 끼칠 수 있을 것으로 기대한다.