Bloom Filter

Bloom Filter

Bloom 필터를 사용해 쿼리 결과에서 Bloom 필터를 만들거나, Bloom 필터로 쿼리 결과를 필터링할 수 있는 확장 기능이에요. 확률적 데이터 구조를 활용해 집합 멤버십을 검사해요.

출처: 문서

본문

Apache Druid® Bloom 필터 확장 기능을 사용하려면 extensions load list에 druid-bloom-filter를 포함하세요. 자세한 내용은 Loading extensions를 참고하세요.

이 확장 기능은 쿼리 결과에서 Bloom 필터를 생성하고, Bloom 필터에 대한 테스트로 쿼리 결과를 필터링하는 기능을 추가해요. Bloom 필터는 집합 멤버십을 검사하는 확률적 데이터 구조예요. 명시적 필터가 불가능한 경우, 예를 들어 수백만 개 값의 집합에 대해 쿼리를 필터링하는 경우 Bloom 필터가 좋은 선택이에요.

Bloom 필터의 몇 가지 특성은 다음과 같아요:

  • Bloom 필터는 HashSet보다 훨씬 공간 효율적이에요.
  • 확률적이기 때문에 Bloom 필터에서는 거짓 양성(false positive) 결과가 가능해요. 예를 들어 test() 함수가 필터 안에 없는 요소에 대해 true를 반환할 수 있어요.
  • 거짓 음성(false negative)은 불가능해요. 요소가 있으면 test()는 항상 true를 반환해요.
  • 이 구현의 거짓 양성 확률은 5%로 고정돼 있어요. 필터가 보유할 수 있는 항목 수를 늘리면 전체 크기가 커지는 대가로 이 거짓 양성률을 낮출 수 있어요.
  • Bloom 필터는 삽입된 요소 수에 민감해요. 생성 시점에 예상 항목 수를 지정해야 해요. 삽입 수가 지정된 항목 수를 초과하면 거짓 양성 확률이 그에 따라 증가해요.

이 확장 기능은 hive-storage-api의 org.apache.hive.common.util.BloomKFilter를 기반으로 해요. 내부적으로 이 구현은 해시 알고리즘으로 Murmur3을 사용해요.

다음 Java 예제는 외부에서 BloomKFilter를 구성하는 방법을 보여줘요:

BloomKFilter bloomFilter = new BloomKFilter(1500);
bloomFilter.addString("value 1");
bloomFilter.addString("value 2");
bloomFilter.addString("value 3");
ByteArrayOutputStream byteArrayOutputStream = new ByteArrayOutputStream();
BloomKFilter.serialize(byteArrayOutputStream, bloomFilter);
String base64Serialized = Base64.encodeBase64String(byteArrayOutputStream.toByteArray());

그러면 Base64로 인코딩된 문자열을 Druid의 JSON 기반 또는 SQL 기반 쿼리에서 사용할 수 있어요.

Bloom 필터로 쿼리 필터링하기 (Filter queries with a Bloom filter)

JSON 규격 (JSON specification)

{
  "type" : "bloom",
  "dimension" : <dimension_name>,
  "bloomKFilter" : <serialized_bytes_for_BloomKFilter>,
  "extractionFn" : <extraction_fn>
}

| Property | Description | Required | | type | Filter type. Set to bloom . | Yes | | dimension | Dimension to filter over. | Yes | | bloomKFilter | Base64 encoded binary representation of org.apache.hive.common.util.BloomKFilter . | Yes | | extractionFn | Extraction function to apply to the dimension values. | No |

BloomKFilter 직렬화 형식 (Serialized format for BloomKFilter)

직렬화된 BloomKFilter 형식:

  • 해시 함수 수에 대한 1바이트.
  • bitset의 longs 수에 대한 1개의 빅엔디언 정수.
  • BloomKFilter bitset의 빅엔디언 longs.

org.apache.hive.common.util.BloomKFilter는 Bloom 필터를 outputStream으로 직렬화하는 메서드를 제공해요.

SQL 쿼리 필터링 (Filter SQL queries)

SQL WHERE 절에서 bloom_filter_test 연산자로 Bloom 필터를 사용할 수 있어요:

SELECT COUNT(*) FROM druid.foo WHERE bloom_filter_test(<expr>, '<serialized_bytes_for_BloomKFilter>')

표현식과 가상 컬럼 지원 (Expression and virtual column support)

Bloom 필터 확장 기능은 SQL 연산자와 동일한 구문을 공유하는 Bloom 필터 Druid 표현식도 추가해요.

bloom_filter_test(<expr>, '<serialized_bytes_for_BloomKFilter>')

Bloom 필터 쿼리 애그리게이터 (Bloom filter query aggregator)

bloom 애그리게이터로 Druid 쿼리에서 BloomKFilter의 입력을 만들 수 있어요. 거짓 양성률을 높이지 않고 Bloom 필터가 나타낼 수 있는 최대 고유 항목 수를 지정하려면 maxNumEntries 매개변수에 합리적인 값을 설정하세요. 이 매개변수의 값을 계산하고 쿼리에 적합한 Bloom 필터를 만들려면 고유 개수 스케치(unique count sketch) 중 하나를 사용해 쿼리를 시도해보세요.

JSON 규격 (JSON specification)

{
      "type": "bloom",
      "name": <output_field_name>,
      "maxNumEntries": <maximum_number_of_elements_for_BloomKFilter>
      "field": <dimension_spec>
    }

| Property | Description | Required | | type | Aggregator type. Set to bloom . | Yes | | name | Output field name. | Yes | | field | DimensionSpec to add to org.apache.hive.common.util.BloomKFilter . | Yes | | maxNumEntries | Maximum number of distinct values supported by org.apache.hive.common.util.BloomKFilter . Defaults to 1500 . | No |

예제 (Example)

다음 예제는 bloom 애그리게이터가 있는 timeseries 쿼리 객체를 보여줘요:

{
  "queryType": "timeseries",
  "dataSource": "wikiticker",
  "intervals": [ "2015-09-12T00:00:00.000/2015-09-13T00:00:00.000" ],
  "granularity": "day",
  "aggregations": [
    {
      "type": "bloom",
      "name": "userBloom",
      "maxNumEntries": 100000,
      "field": {
        "type":"default",
        "dimension":"user",
        "outputType": "STRING"
      }
    }
  ]
}

응답 예시:

[
  {
    "timestamp":"2015-09-12T00:00:00.000Z",
    "result":{"userBloom":"BAAAJhAAAA..."}
  }
]

결과를 Bloom 필터 애그리게이터로 정렬하는 대신 대체 집계 방식으로 정렬하는 것을 권장해요. Bloom 필터 애그리게이터로 결과를 정렬하면 리소스 집약적일 수 있는데, Druid가 설정된 비트 수를 세어 집합에 추가된 항목 수를 근사하기 위해 필터의 비용이 큰 선형 스캔을 수행하기 때문이에요.

SQL Bloom 필터 애그리게이터 (SQL Bloom filter aggregator)

SQL 표현식에서 BLOOM_FILTER 애그리게이터로 Bloom 필터를 계산할 수 있어요. 예를 들어:

SELECT BLOOM_FILTER(<expression>, <max number of entries>) FROM druid.foo WHERE dim2 = 'abc'

Druid는 SQL 응답의 Bloom 필터 결과를 Base64 문자열로 직렬화해요. 그 결과 문자열을 이후 쿼리에서 필터로 사용할 수 있어요.

더 알아보기 (Learn more)