The automata-based XML stream filtration has achieved recognition as an efficient solution for processing many queries over XML streaming data simultaneously. However, Most of Automa-ta-style query are mostly implemented on hash table. They suffer from missing cache caused byfrequent random memory accesses. We focus on improving the hash tables for the automata-based XML stream filtration in this paper. We first adopt the Splash hash table which guarantees the high load factor and the constant lookup time. We also provide two optimization techniques that further improve the overall throughput of the XML stream filtration: 1) Hot Path Packing identify-ing and grouping the state transitions which frequently occur together into the same bucket and 2) Exclusive Automata Decomposition probing the exclusively decomposed automata segments into the same bucket.
Consequently, when our Exclusive Automata Decomposition is applied, cache performance, i.e. the number of cache misses could be improved approximately at 20% 17% on each data (i.e., XMark, Treebank). In addition, due to the lookup strategy of decomposed automata, our approach shows the number of data read could be reduced by about 64%, 27% as well by jumping over a conventional hash table lookup.
스트리밍(Streaming)환경에서 빠르게 지속적으로 입력되는 스트림 데이터를 처리하기 위해 질의들을 저장, 인덱싱하고 데이터에 대해서 적합한 질의를 실시간으로 찾는 스트림 처리 시스템이 등장하게 되었다. 오토마타 기반의 스트림 처리 시스템은 입력되는 스트림에 대해서 다수의 질의를 처리하는 데에 가장 효율적인 시스템으로 알려져 있다.
오토마타 기반 XML 스트림 필터링 시스템에서는 필터링에 요구되는 질의 인덱스의 구현을 위해 주로 해시 테이블을 이용하며, 해싱의 특성상 테이블에의 탐색 과정은 메모리 상의 임의 접근 패턴을 보인다. 이러한 메모리 상의 임의 접근은 데이터 스트림 처리 중에 많은 캐시 미스를 유발하여 필터링 시스템의 전체 성능을 떨어뜨리는 주요 요인이 된다. 따라서, 스트림 데이터에 대한 질의 처리의 향상을 위해서는 캐시 친화적(cache-friendly)인 질의 인덱스 구조가 요구된다.
따라서, 본 논문에서는 오토마타 기반의 XML스트림 필터링의 캐시 성능 향상을 위해 오토마타 탐색 과정의 지역성(locality)을 향상시키는 방법을 제안하였다. 우선, 오토마타를 저장하기 위한 자료구조로 Splash 테이블을 이용하였다. Splash 테이블은 연속적으로 할당된 메모리 공간을 95~99%에 이르는 높은 수준의 적재율(load factor)로 활용하며 뻐꾸기 해싱(cuckoo hashing) 전략에 의해 상수 시간의 복잡도를 갖는 탐색을 보장할 수 있게 한다.
이러한Splash 테이블의 하나의 버켓(bucket)에 다수의 슬롯을 갖는 Bucketized된 구조를 활용하여, 시간적 지역성을 향상시키는 기법을 제안하였다. 최초의 우리 접근은 스트림 필터링 과정에서 빈번하게 참조되는 전이 정보(Hot Path)와 그 인접한 전이들을 중복하여 버켓내에 저장하는 공유 빈발 전이 패턴 묶음 전략(Hot Path Packing)이다. 공유 빈발 전이 패턴 묶음은 한번 상태 전이를 위해 해시 테이블의 버켓을 참조 한 이후에는 다음 상태 전이의 검사 시 이 다음 상태 전이 정보도 동일 캐시라인 상에 이미 같이 적재되어 있을 것을 기대하고 있다. 실험결과 공유 빈발 패턴 접근을 통해 해시테이블의 데이터 읽는 횟수를 줄일 수 있음을 확인하였지만, 캐시 성능 향상으로 크게 이어지지는 못하였다. 이러한 공유 빈발 패턴에서의 관찰을 바탕으로 성능이득을 극대화하기 위하여 최종적으로 제안하는 접근은 배타적 오토마타 분할 기법(Exclusive Automata Decomposition)이다. 오토마타 분할 기법은 트리(tree)형태의 오토마타를 Bucketized된 버켓에 저장할 수 있도록 4개의 전이를 부분 오토마타로 분할하여 버켓에 저장 및 탐색하는 기법이다.
오토마타 분할 기법인 적용된 후 XML 데이터인 XMark와 Treebank를 대상으로 그 성능을 측정하였다. 각 900개의 문서 스트림을 처리할 때에 실험 데이터에서 데이터 읽기 횟수를 각각 64%, 27% 향상되었고, L1 캐시 미스 또한 각각 20%, 17% 줄어듬을 확인할 수 있었다.
