[논문] 고성능 다중 패턴 매칭 알고리즘에 관한 연구

카이스트 네트워크 애플리케이션을 위한 고성능 다중 패턴 매칭 알고리즘에 관한 연구 - 최병건

위의 내용의 논문을 바탕으로 글을 작성함을 알려드립니다.

항상 논문을 보다보면 아쉬운 부분이 많은데 해당 논문은 그러한 부분이 존재하지 않아서 너무 좋았습니다.

 

그런데 영어로 적혀있어서 저와 같은 영어를 잘 모르시는 분들은 보기가 조금 어렵지 않나 생각됩니다.

 

해당 논문을 알게된 배경은 Intel에 HyperScan 논문을 확인하는 과정에서 해당 논문에 대한 이야기가 나와서 확인을 하게 되었습니다. 

 

제가 작성하는 내용이 정확한 내용이 아닐수 있음을 고려하여 주셨으면 합니다.

저는 저만의 방식으로 해당 논문을 이해한 내용을 기록하고자 함입니다.

 

 

 

우선은 시작하기 앞서서 해당 논문은 네트워크 애플리케이션을 위한 이라고 명시되어 있지만 사실 고성능 다중 패턴 매칭 알고리즘에 관한 연구로 이해하시면 편리하실것 같습니다. YARA와 같은 open source는 내부적으로 aho-corasick 과 atom quality등 이러한 부분들을 이용합니다. 본 논문은 이미 대중적으로 많이 사용하는 다중 패턴 매칭 알고리즘인 aho-corasick의 성능과 관련된 연구를 이야기 합니다.

 

해당 논문의 모든 내용을 소개하기 보다는 핵심 아이디어를 이야기 할려고 합니다.

aho-corasick의 변형을 한것이던 원본이던 가지는 단점이 존재합니다. 바로 패턴을 매칭하기 위한 rule들 (tree로 표현되는데) cache 친화적이지 못하다는 부분입니다. 이는 결국 많은 수의 cache miss를 유발하며, 결국 cpu stalls로 귀결됩니다.

여기에서 key point는 cache 친화적인 데이터 구조를 바탕으로 cpu stalls를 최소화 하는것이라고 저는 생각합니다.

 

pattern들을 window(쪼개서) 각각의 DF(direct filter)에 넣는 방식을 택합니다. 이렇게 window를 수행함으로 각 단계의 size는 감소하게 되며 이는 결국 cache miss를 감소시켜 줄것입니다. 그리고 cache는 L2 cache 까지를 고려하는것으로 생각되어 집니다. L2 cache는 L3 cache대비 4~7배 정도 빠르다고 이야기 합니다.

 

그리고 size를 줄이기 위한 false positive를 일정부분 인정해주면서 verification 과정을 거쳐 false positive를 제거해주는 방식을 택하였습니다.

그리고 이제 Classifying DF, Additional DF 이 2개가 Progressive filttering이 되며, verification과정을 거치게 되고 총 2개의 stage로 구성되어 있습니다.

 

보다 자세한 구성사항들은 논문을 직접 찾아보시기 바랍니다. 사실 pattern을 쪼개고 여러과정으로 나누어서 data size(loopup table, translation table)을 cache size에 맞추어 cache miss를 줄인다는 아이디어가 저는 핵심이라고 생각되어지긴 합니다.

 

조금 아쉬운 부분은 구현과정에 대한 설명이 조금 더 자세하면 좋지 않을까 하는 생각은 들었습니다.

이제 이 논문을 확인하였으니 HyperScan을 봐야하는데 해당 논문 (DFC)에서 이야기하는 feed-forward bloom filter도 봐야할것 같습니다. (대충봐서 자세히 한번더 볼생각입니다.)