패턴 (정규식) 기반 검색 시스템

Question

정규식과 일치하는 패턴에 대해 테라 바이트의 데이터를 검색하는 방법을 찾고 있습니다. 이 구현은 라인 데이터의 시작과 끝, 전체 TR1 지원 (POSIX 및/또는 PCRE 지원이 바람직 함) 등과 같이 정규 표현식의보다 정교한 많은 기능을 지원해야합니다. Google은 잠재적으로 민감한 정보의 저장과 관련된 정책을 테스트하기 위해이 애플리케이션을 효과적으로 사용하고 있습니다.

색인 생성 솔루션을 살펴 보았지만 상용 스위트의 대부분은 우리가 원하는 더 자세한 정규 표현식을 지원하지 않습니다 (현재까지는 복잡한 정규 표현식을 파싱 할 때 완전히 실패했습니다. 다시 사용).

이것은 우리가 가지고있는 데이터의 양과 스캐닝 작업에 투입해야하는 시스템 자원의 양 때문에 복잡한 문제입니다 (정책 준수에 대한 검사만으로는 아닙니다. 하드웨어에 대한 예산은 그다지 많지 않습니다.)

Lucene을 살펴 봤지만 정규식 배터리를 완전히 다룰 수없는 색인 시스템을 사용하는 것에 대해서는 조금 주저하고 전체 데이터 세트를 검색하면이 문제를 해결할 수 있습니다. 서버는 적어도 몇 주 동안 이러한 작업을 수행하는 데 어려움을 겪습니다.

제안 사항?

Answer 1

PowerGREP은 정규 표현식을 처리 할 수 ​​있으며 이러한 목적으로 설계되었습니다. 많은 양의 데이터를 검색하는 것이 매우 빠르다는 것을 알았지 만 테라 바이트 단위로 아직 시도하지 않았습니다. 그러나 30 일의 재판이 있기 때문에, 그럴 가치가 있습니다.

파일의 특정 부분을 검색 할 때 특히 강력합니다. 자신의 기준에 따라 파일을 구분 한 다음 해당 섹션에만 다른 검색을 적용 할 수 있습니다. 또한 매우 우수한보고 기능을 갖추고 있습니다.

Answer 2

grep 프로그램은 정규식 정규 표현식 라이브러리로 이길 수 없다는 점에서 파일에서 정규식 검색을 위해 고도로 최적화되어 있습니다. 심지어 테라 바이트를 검색하는 것은 비현실적으로 느릴 것입니다. 그래서 정규식 검색을 할 때 운이 나쁘다고 생각합니다.

가능성이있는 일치 항목을 찾기 위해 첫 번째 통과로 인덱서를 사용한 다음 각 일치 항목의 양쪽에서 일부 바이트를 추출하고 전체 정규식 일치를 실행할 수도 있습니다.

Answer 3

Apache Hadoop을 살펴볼 수 있습니다. 야후와 페이스 북과 같은 거대한 사이트는 Hadoop을 다양한 용도로 사용하며, 그 중 하나는 멀티 TB의 텍스트 로그를 처리합니다.

Hadoop 설명서에는 변환 가능한 Grep의 예가 있습니다.이 Grep은 변환 가능한 데이터 세트 크기를 처리 할 수 ​​있습니다.

솔루션을 롤업하려는 경우 Hadoop API에 SequenceFileInputFilter.RegexFilter도 있습니다.

Answer 4

높은 수준의 대답 만 제공 할 수 있습니다. Tim과 shadit의 답변을 바탕으로 EC2 또는 Azure Compute에서 MapReduce 알고리즘으로 구현 된 two-pass 접근 방식을 사용하십시오. 각 패스에서 지도은 식별자가 포함 된 데이터를 가져 와서 으로 돌아갈 수 있습니다. 일치하는 항목이 발견되면 식별자를 줄이고 그렇지 않으면 null 값을 반환합니다. 처리 시간을 줄이기 위해 필요한만큼 확장하십시오.

Answer 5

고지 사항 : 저는 검색 전문가가 아닙니다.

만약 당신이 정말로 모든 regexps의 일반성이 필요하다면 모든 데이터를 통해 트롤링하는 것보다 더 좋은 방법은 없을 것입니다.

그러나 실제로 그런 것은 아닌 것 같습니다. 그래서 가능한 한 문서를 식별하기 위해 색인을 사용할 수 있는지 먼저 확인해야합니다. 예를 들어, 모든 성냥에 단어 (모든 단어)가 포함될 것이라는 것을 안다면, 단어를 색인 할 수 있으며, 그 단어를 포함하는 (희망에 따라 작은) 문서 세트를 찾은 다음 grep 또는 동급의 단어를 사용할 수 있습니다 그 파일들에 대해서만.

예를 들어, 줄의 시작 부분에 "FoObAr"가있는 문서를 찾아야 할 수도 있습니다. "foobar"가있는 파일을 식별하고 "^ FoObAr"에 대한 grep (만)을 식별하기 위해 캐스케이드 색인으로 시작할 것입니다.

다음으로 가능한 한 빨리 grep하는 방법. 당신은 io 속도에 의해 제한 될 가능성이 큽니다. 그래서 여러 디스크를 사용하십시오 (RAID를 사용할 필요가 없습니다 - 디스크 당 하나의 스레드 만 가질 수 있습니다). 또한 압축을 고려하십시오. 당신은이 파일들에 무작위로 접근 할 필요가 없으며 만약 그들이 텍스트라면 (만약 그들이 당신을 grepping한다면), 그들은 잘 압축 할 것입니다. 그러면 읽고 (저장하는) 데 필요한 데이터의 양이 줄어 듭니다.

마지막으로 인덱스가 모든 쿼리에 대해 작동하지 않으면 사용 가치가 없을 것입니다. 당신은 한 번에 모든 표현식에 대해 "grep"을 할 수 있습니다. 그리고 값 비싼 프로세스는 grep의 세부 사항이 아닌 데이터를 읽으므로 인덱싱 할 수없는 "단 하나의"쿼리가 있더라도 스캔 할 필요가 있습니다 모든 것, 그리고 인덱스를 만들고 사용하는 것은 아마 당신의 시간을 잘 활용하지 못할 것입니다.