Go의 비트맵 인덱스: 빠른 속도로 검색

소개

저는 모스크바에서 열린 GopherCon Russia 2019 컨퍼런스에서 영어로 이 강연을 했고, 니즈니노브고로드에서 열린 미팅에서는 러시아어로 이 강연을 했습니다. 이는 B-트리만큼 흔하지는 않지만 흥미로운 비트맵 인덱스에 대한 내용입니다. 나는 공유한다 기록 영어로 된 학술대회 연설과 러시아어로 된 대본.

비트맵 인덱스가 어떻게 구성되어 있는지, 언제 비트맵 인덱스가 다른 인덱스보다 더 좋고, 언제 비트맵 인덱스가 다른 인덱스보다 더 나쁘고, 어떤 경우에 비트맵 인덱스가 다른 인덱스보다 훨씬 빠른지 살펴보겠습니다. 어떤 인기 DBMS가 이미 비트맵 인덱스를 가지고 있는지 살펴보겠습니다. Go로 우리만의 코드를 작성해 보겠습니다. 그리고 "디저트로" 우리는 기성 라이브러리를 사용하여 우리만의 초고속 전문 데이터베이스를 만들 것입니다.

제 작업이 여러분께 유용하고 흥미로울 수 있기를 진심으로 바랍니다. 갑시다!

소개

안녕하세요 여러분! 지금은 6시이고, 우리 모두 엄청 피곤해요. 지루한 데이터베이스 인덱스 이론에 대해 이야기하기엔 지금이 딱 ​​맞는 때죠? 걱정하지 마세요. 여기저기에 몇 줄의 소스 코드가 있을 거예요. 🙂

진지하게 말해서, 보고서는 정보로 넘쳐나고 있고, 우리에게는 시간이 많지 않습니다. 그럼 시작해볼까요.

오늘은 다음 내용에 대해 말씀드리겠습니다.

• 지수란 무엇인가?
• 비트맵 인덱스란 무엇입니까?
• 어디에서 사용되고 어디에서 사용되지 않는지, 그리고 그 이유는 무엇인가;
• Go에서는 간단하게 구현했지만 컴파일러는 약간 번거롭습니다.
• 조금 덜 간단하지만 Go 어셈블리로 훨씬 더 생산적인 구현입니다.
• 비트맵 인덱스의 "문제"
• 기존 구현.

그렇다면 지수란 무엇일까요?

인덱스는 기본 데이터 외에 우리가 유지 관리하고 업데이트하는 별도의 데이터 구조입니다. 이는 검색 속도를 높이는 데 사용됩니다. 인덱스가 없다면 검색을 위해 데이터 전체를 탐색해야 합니다(전체 스캔이라고 하는 프로세스). 이 프로세스는 선형 알고리즘 복잡도를 갖습니다. 하지만 데이터베이스는 일반적으로 엄청난 양의 데이터를 포함하고 있으며 선형 복잡도는 너무 느립니다. 이상적으로는 대수적이거나 상수적인 값을 얻게 될 것입니다.

이것은 광활하고 복잡한 주제이며 미묘한 차이와 상충 관계가 있습니다. 하지만 수십 년간 다양한 데이터베이스에 대한 개발과 연구를 거친 결과, 데이터베이스 인덱스를 만드는 데 널리 사용되는 접근 방식은 몇 가지에 불과하다고 말할 수 있습니다.

첫 번째 방법은 검색 공간을 계층적으로 줄여서 검색 공간을 더 작은 부분으로 나누는 것입니다.

우리는 보통 다양한 종류의 나무를 사용하여 이 작업을 수행합니다. 예를 들어 옷장에 여러 가지 주제로 구분된 작은 재료 상자가 들어 있는 큰 재료 상자가 있습니다. 만약 물품이 필요하다면, "쿠키"라고 적힌 상자보다는 "물품"이라고 적힌 상자에서 찾을 가능성이 높지 않나요?

두 번째 방법은 원하는 요소나 요소 그룹을 즉시 선택하는 것입니다. 이 작업은 해시 맵이나 역 인덱스에서 수행됩니다. 해시 맵을 사용하는 것은 이전 예와 매우 유사합니다. 다만, 상자를 담은 상자 대신 옷장에 최종 품목이 들어 있는 여러 개의 작은 상자가 있다는 점이 다릅니다.

세 번째 접근법은 검색의 필요성을 없애는 것입니다. 우리는 블룸 필터나 뻐꾸기 필터를 사용하여 이를 수행합니다. 첫 번째 방법은 즉시 답변을 제공하므로 검색하는 번거로움이 없습니다.

마지막 방법은 현대 하드웨어가 제공하는 모든 힘을 최대한 활용하는 것입니다. 비트맵 인덱스에서 정확히 이런 일을 합니다. 네, 이를 사용할 때 때로는 색인 전체를 살펴봐야 하지만, 우리는 매우 효율적으로 작업을 수행합니다.

제가 말했듯이, 데이터베이스 인덱스라는 주제는 광범위하고 타협이 많습니다. 이는 때로는 여러 가지 접근 방식을 동시에 사용할 수 있다는 것을 의미합니다. 검색 속도를 한층 더 높여야 하거나 가능한 모든 검색 유형을 다루어야 하는 경우가 그렇습니다.

오늘은 언급된 접근 방식 중 가장 잘 알려지지 않은 비트맵 인덱스에 대해 이야기해보겠습니다.

제가 이 주제에 대해 말할 자격이 있나요?

저는 Badoo에서 팀 리더로 일하고 있습니다(아마도 저희의 다른 제품인 Bumble을 더 잘 알고 계실 겁니다). 우리는 이미 전 세계적으로 400억 명이 넘는 사용자를 보유하고 있으며, 그들에게 가장 잘 맞는 것을 선택하기 위해 많은 기능을 활용하고 있습니다. 우리는 비트맵 인덱스를 포함한 맞춤형 서비스를 사용하여 이를 수행합니다.

그렇다면 비트맵 인덱스란 무엇일까요?

이름에서 알 수 있듯이 비트맵 인덱스는 비트맵이나 비트셋을 사용하여 검색 인덱스를 구현합니다. 위에서 보면 이 색인은 일부 개체(예: 사람)와 그 속성 또는 매개변수(나이, 눈 색깔 등)를 나타내는 하나 이상의 비트맵과 비트 연산(AND, OR, NOT)을 사용하여 검색 쿼리에 답하는 알고리즘으로 구성됩니다.

비트맵 인덱스는 낮은 카디널리티(예: "눈 색깔" 또는 "결혼 상태" 대비 "도심으로부터의 거리")를 갖는 여러 열에 대한 쿼리를 결합하는 검색 사례에 가장 적합하고 매우 성능이 뛰어나다고 합니다. 하지만 나중에 이것이 높은 기수 열에도 잘 작동한다는 것을 보여드리겠습니다.

비트맵 인덱스의 가장 간단한 예를 살펴보겠습니다.

다음과 같은 이진 속성을 가진 모스크바 레스토랑 목록이 있다고 가정해 보겠습니다.

• 지하철 근처
• 개인 주차장이 있습니다
• 베란다가 있습니다.
• 테이블을 예약할 수 있습니다(예약 가능);
• 채식주의자에게 적합함 (비건 친화적)
• 값비싼.

각 레스토랑에 0부터 시작하는 번호를 부여하고 6개의 비트맵(각 기능당 하나씩)에 대한 메모리를 할당해 보겠습니다. 그런 다음 레스토랑에 해당 부동산이 있는지 여부에 따라 이러한 비트맵을 채웁니다. 레스토랑 4에 베란다가 있는 경우 "베란다 있음" 비트맵의 비트 #4가 1로 설정됩니다(베란다가 없는 경우 0).

이제 가능한 가장 간단한 비트맵 인덱스가 있으며, 이를 사용하여 다음과 같은 쿼리에 답할 수 있습니다.

• "채식주의자 친화적인 레스토랑을 보여주세요"
• "베란다 있고 예약이 가능한 저렴한 레스토랑을 알려주세요."

어떻게? 한번 살펴보죠. 첫 번째 요청은 매우 간단합니다. 우리가 해야 할 일은 "채식주의 친화적" 비트맵을 가져와서 해당 비트를 표시하는 레스토랑 목록으로 바꾸는 것뿐입니다.


두 번째 질문은 조금 더 복잡합니다. "비싼" 비트맵에서 비트 NOT 연산을 사용하여 저렴한 레스토랑 목록을 구한 다음, 이를 "예약 가능" 비트맵과 AND 연산하고, 그 결과를 "베란다 가능" 비트맵과 AND 연산해야 합니다. 결과적으로 나오는 비트맵에는 모든 기준을 충족하는 시설 목록이 포함됩니다. 이 예에서는 "Youth"라는 레스토랑만 있습니다.


여기에는 많은 이론이 있지만 걱정하지 마세요. 곧 코드를 볼 수 있을 겁니다.

비트맵 인덱스는 어디에 사용되나요?

비트맵 인덱스를 구글에서 검색하면, 답변의 90%가 어떤 식으로든 Oracle DB와 관련이 있습니다. 하지만 다른 DBMS도 이 멋진 기능을 지원할 가능성이 있지 않나요? 설마.

주요 용의자 목록을 살펴보겠습니다.

MySQL은 아직 비트맵 인덱스를 지원하지 않지만 이 옵션을 추가하려는 제안이 있습니다.https://dev.mysql.com/worklog/task/?id=1524).

PostgreSQL은 비트맵 인덱스를 지원하지 않지만, 간단한 비트맵과 비트 연산을 사용하여 여러 다른 인덱스의 검색 결과를 결합합니다.

Tarantool에는 비트셋 인덱스가 있으며, 이를 통한 간단한 검색을 지원합니다.

Redis에는 간단한 비트 필드가 있습니다 (https://redis.io/commands/bitfield) 검색할 수 있는 기능이 없습니다.

MongoDB는 아직 비트맵 인덱스를 지원하지 않지만, 이 기능을 추가하려는 제안도 있습니다. https://jira.mongodb.org/browse/SERVER-1723

Elasticsearch는 내부적으로 비트맵을 사용합니다 (https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps)).

• 하지만 우리 집에는 새로운 이웃이 생겼습니다. 바로 필로사입니다. 이는 Go로 작성된 새로운 비관계형 데이터베이스입니다. 여기에는 비트맵 인덱스만 포함되어 있으며 모든 것이 이를 기반으로 합니다. 그녀에 대해서는 잠시 후에 이야기하겠습니다.

Go에서의 구현

하지만 비트맵 인덱스가 거의 사용되지 않는 이유는 무엇일까요? 이 질문에 답하기 전에 Go에서 매우 간단한 비트맵 인덱스를 구현한 예를 보여드리겠습니다.

비트맵은 본질적으로 단지 데이터 덩어리입니다. Go에서는 이를 위해 바이트 슬라이스를 사용해 보겠습니다.

레스토랑 기능당 비트맵이 하나씩 있으며, 비트맵의 각 비트는 특정 레스토랑에 해당 기능이 있는지 여부를 알려줍니다.

두 개의 도우미 함수가 필요합니다. 하나는 비트맵을 무작위 데이터로 채우는 데 사용됩니다. 무작위이지만, 레스토랑이 각 속성을 가질 확률은 일정합니다. 예를 들어, 모스크바에는 예약이 불가능한 레스토랑이 거의 없고, 그 중 약 20%는 채식주의자에게 친화적인 곳이라고 생각합니다.

두 번째 기능은 비트맵을 레스토랑 목록으로 변환합니다.


"파티오가 있고 예약이 가능한 저렴한 레스토랑을 보여주세요"라는 질의에 답하려면 NOT과 AND라는 두 개의 비트 연산이 필요합니다.

더 복잡한 AND NOT 연산을 사용하면 코드를 약간 단순화할 수 있습니다.

각 작업마다 기능이 있습니다. 둘 다 슬라이스를 살펴보고, 각 슬라이스에서 해당 요소를 가져와 비트 연산으로 결합한 다음, 결과를 결과 슬라이스에 넣습니다.

이제 우리는 비트맵과 함수를 사용해 검색어에 답할 수 있습니다.

함수가 매우 간단하고 함수가 호출될 때마다 새로운 결과 슬라이스를 반환하지 않아 많은 비용을 절감했지만 성능은 그렇게 높지 않습니다.

pprof로 약간 프로파일링을 한 후, Go 컴파일러에 매우 간단하지만 매우 중요한 최적화 기능인 함수 인라이닝이 빠졌다는 것을 알았습니다.

문제는, Go 컴파일러가 슬라이스를 통과하는 루프를 몹시 두려워하고, 그러한 루프가 포함된 함수를 인라인으로 처리하는 것을 단호히 거부한다는 것입니다.

하지만 저는 두려워하지 않고, 옛날처럼 루프 대신 goto를 사용하여 컴파일러를 속일 수 있습니다.

그리고 여러분이 볼 수 있듯이 이제 컴파일러는 우리 함수를 자동으로 인라인으로 처리합니다! 그 결과, 약 2마이크로초를 절약할 수 있었습니다. 나쁘지 않네요!

두 번째 병목 현상은 어셈블리 출력을 자세히 살펴보면 쉽게 알 수 있습니다. 컴파일러는 가장 인기 있는 루프 내부에 슬라이스 범위 검사를 추가했습니다. 문제는 Go가 안전한 언어라는 점인데, 컴파일러는 세 개의 인수(세 개의 슬라이스)의 크기가 서로 다를까 봐 걱정합니다. 그렇다면 이론적으로는 버퍼 오버플로가 발생할 가능성이 있습니다.

모든 슬라이스의 크기가 같다는 것을 보여 컴파일러를 안심시켜 보겠습니다. 함수의 시작 부분에 간단한 검사를 추가하면 됩니다.

이를 보고 컴파일러는 기꺼이 검사를 건너뛰고, 결국 우리는 500나노초를 더 절약하게 됩니다.

대량 배치

네, 우리는 간단한 구현으로 어느 정도 성능을 끌어내는 데 성공했지만, 그 결과는 현재 하드웨어로 가능한 것보다 훨씬 나빴습니다.

우리가 하는 일은 기본적인 비트 연산뿐이며, 우리의 프로세서는 이를 매우 효율적으로 수행합니다. 하지만 불행히도 우리는 프로세서에 매우 작은 작업만을 "공급"합니다. 우리의 함수는 바이트 단위로 작업을 수행합니다. UInt8 슬라이스를 사용하면 64바이트 청크로 작업할 수 있도록 코드를 매우 쉽게 조정할 수 있습니다.

보시다시피, 이 작은 변화로 배치 크기가 8배 늘어나서 프로그램 속도가 8배 빨라졌습니다. 말하자면 이득은 선형적입니다.

어셈블리 언어 구현

하지만 이것이 끝은 아닙니다. 저희의 프로세서는 16, 32, 심지어 64바이트 크기의 청크로도 작업할 수 있습니다. 이런 "광범위한" 연산을 SIMD(Single Instruction Multiple Data)라고 하며, 이런 연산을 사용할 수 있도록 코드를 변환하는 과정을 벡터화라고 합니다.

안타깝게도 Go 컴파일러는 훌륭한 벡터화기와는 거리가 멉니다. 현재 Go 코드를 벡터화하는 유일한 방법은 Go 어셈블리를 사용하여 이러한 작업을 수동으로 작성하는 것입니다.

Go 어셈블러는 이상한 짐승이다. 여러분은 어셈블리 언어가 자신이 작성하고 있는 컴퓨터의 아키텍처와 긴밀하게 연결돼 있다는 걸 알고 있을 겁니다. 하지만 Go에서는 그렇지 않습니다. Go 어셈블리는 IRL(중간 표현 언어)에 더 가깝습니다. 즉, 사실상 플랫폼에 독립적입니다. Rob Pike가 훌륭한 공연을 펼쳤습니다. 보고서 이 주제에 대해서는 몇 년 전 덴버의 GopherCon에서 다루었습니다.

또한 Go는 기존의 AT&T와 Intel 포맷과 다른 특이한 Plan 9 포맷을 사용합니다.

Go 어셈블리를 직접 작성하는 것은 그다지 재미있는 일이 아니라고 해도 과언이 아닙니다.

하지만 다행히도 Go 어셈블리를 작성하는 데 도움이 되는 두 가지 고급 도구가 이미 있습니다. 바로 PeachPy와 avo입니다. 두 유틸리티 모두 각각 Python과 Go로 작성된 상위 수준 코드에서 Go 어셈블리를 생성합니다.

이러한 유틸리티는 레지스터 할당, 루프 작성 등의 작업을 간소화하며, 전반적으로 Go에서 어셈블리 프로그래밍의 세계에 진입하는 것을 더 쉽게 만들어줍니다.

avo를 사용하므로 프로그램은 일반 Go 프로그램과 거의 비슷할 것입니다.

이것은 AVO 프로그램의 가장 단순한 예입니다. main() 함수가 있는데, 이 함수는 그 자체 내에 Add() 함수를 정의하고 있으며, 이 함수의 목적은 두 숫자를 더하는 것입니다. 여기에는 이름으로 매개변수를 가져오고 무료로 제공되는 적합한 프로세서 레지스터 중 하나를 가져오는 도우미 함수가 있습니다. ADDQ에서 볼 수 있듯이, 각 프로세서 작업에는 avo에 해당하는 함수가 있습니다. 마지막으로 결과 값을 저장하는 도우미 함수를 살펴보겠습니다.

go generate를 호출하면 avo에서 프로그램이 실행되고 그 결과 두 개의 파일이 생성됩니다.

• Go 어셈블리에서 결과 코드에 .s를 추가합니다.
• stub.go에는 Go와 어셈블리라는 두 세계를 연결하는 함수 헤더가 있습니다.

이제 avo가 무엇을 하는지, 어떻게 하는지 살펴보았으니 함수를 살펴보겠습니다. 저는 함수의 스칼라 및 벡터(SIMD) 버전을 모두 구현했습니다.

먼저 스칼라 버전을 살펴보겠습니다.

이전 예와 마찬가지로, 우리는 자유롭고 유효한 범용 레지스터를 요청하므로 인수에 대한 오프셋과 크기를 계산할 필요가 없습니다. 아보는 우리를 대신해 이 모든 일을 해줍니다.

이전에는 성능을 개선하고 Go 컴파일러를 속이기 위해 라벨과 goto(또는 점프)를 사용했지만, 이제는 처음부터 이 작업을 사용합니다. 요점은 주기가 더 높은 수준의 개념이라는 것입니다. 어셈블리에서는 라벨과 점프만 있습니다.

나머지 코드는 이제 익숙하고 이해하기 쉬울 것입니다. 우리는 라벨과 점프를 사용해 루프를 에뮬레이션하고, 두 슬라이스에서 작은 데이터 조각을 가져와 비트 연산(이 경우에는 AND NOT)으로 결합한 다음, 그 결과를 결과 슬라이스에 넣습니다. 모두.

최종 어셈블리 코드는 다음과 같습니다. 오프셋과 크기(녹색으로 강조 표시)를 계산할 필요가 없었고, 사용된 레지스터(빨간색으로 강조 표시)를 추적할 필요도 없었습니다.

어셈블리 구현의 성능을 가장 뛰어난 Go 구현의 성능과 비교해보면 동일하다는 것을 알 수 있습니다. 그리고 이는 예상된 일이었습니다. 결국, 우리는 특별한 일을 한 게 아닙니다. Go 컴파일러가 하는 일을 그대로 재현했을 뿐입니다.

안타깝게도, 어셈블리로 작성된 함수를 컴파일러에 인라인으로 적용하도록 강제할 수는 없습니다. 현재 Go 컴파일러에는 이 기능이 없지만, 꽤 오랫동안 이 기능을 추가해 달라는 요청이 있었습니다.

이것이 어셈블리에서 작은 함수를 사용해도 아무런 이점을 얻을 수 없는 이유입니다. 우리는 더 큰 함수를 작성하거나, 새로운 math/bits 패키지를 사용하거나, 어셈블리를 피해야 합니다.

이제 함수의 벡터 버전을 살펴보겠습니다.

이 예제에서는 AVX2를 사용하기로 결정했으므로 32바이트 청크에서 작동하는 작업을 사용할 것입니다. 코드 구조는 스칼라 버전과 매우 유사합니다. 매개변수 로드, 무료 일반 레지스터 요청 등입니다.

새로운 기능 중 하나는 더 넓은 벡터 연산이 특수하고 넓은 레지스터를 사용한다는 것입니다. 32바이트 청크의 경우 Y 접두사가 붙은 레지스터입니다. 그래서 코드에서 YMM() 함수를 볼 수 있는 것입니다. 512비트 청크를 사용하는 AVX-64를 사용한다면 접두사는 Z가 됩니다.

두 번째 혁신은 루프 언롤링이라는 최적화를 사용하기로 결정한 것입니다. 즉, 루프의 시작 부분으로 이동하기 전에 8개의 루프 연산을 수동으로 수행하는 것을 의미합니다. 이러한 최적화는 코드의 분기 수를 줄이고, 사용 가능한 여유 레지스터 수에 따라 제한됩니다.

그럼 성능은 어떨까요? 그녀는 아름다워요! Go의 최고 솔루션과 비교했을 때 약 7배의 속도 향상을 얻었습니다. 인상적이죠?

하지만 이러한 구현도 AVX-512, 프리페칭 또는 쿼리 플래너에 JIT(Just-In-Time) 컴파일러를 사용하면 잠재적으로 더 빨리 수행할 수 있습니다. 하지만 이는 확실히 별도의 보고서에서 다루어야 할 주제입니다.

비트맵 인덱스 문제

이제 Go에서 비트맵 인덱스를 간단하게 구현하는 방법과 어셈블리에서 훨씬 더 성능이 좋은 비트맵 인덱스 구현 방법을 다루었으니, 마지막으로 비트맵 인덱스가 거의 사용되지 않는 이유에 대해 알아보겠습니다.

이전 논문에서는 비트맵 인덱스의 세 가지 문제점을 언급했지만, 최신 논문과 저는 그 문제점들이 더 이상 적절하지 않다고 주장합니다. 우리는 이 문제들 각각에 대해 깊이 있게 다루지 않고, 피상적으로 살펴보겠습니다.

큰 기수 문제

그래서 비트맵 인덱스는 낮은 기수, 즉 값이 적은(예: 성별 또는 눈 색깔) 필드에만 적합하다고 합니다. 그 이유는 높은 기수의 경우 이러한 필드를 일반적으로(값 하나당 1비트) 표현하면 너무 많은 공간을 차지하고, 게다가 이러한 비트맵 인덱스가 드물게(드물게) 채워지기 때문입니다.


때로는 숫자를 표현하는 데 사용하는 표준적인 표현 방식과 같은 다른 표현 방식을 사용할 수도 있습니다. 하지만 모든 것을 바꾸어 놓은 것은 압축 알고리즘의 출현이었습니다. 지난 수십 년 동안 과학자와 연구자들은 비트맵을 위한 수많은 압축 알고리즘을 개발해 왔습니다. 가장 큰 장점은 비트맵 작업을 수행하기 위해 비트맵을 압축 해제할 필요가 없다는 것입니다. 즉, 압축된 비트맵에서 바로 비트맵 작업을 수행할 수 있습니다.

최근에는 비트맵과 같은 하이브리드 접근 방식도 등장하기 시작했습니다. 그들은 비트맵의 세 가지 다른 표현, 즉 비트맵 자체, 배열, 소위 비트 런을 동시에 사용하고 이를 균형 있게 조정하여 성능을 극대화하고 메모리 소비를 최소화합니다.

대부분의 인기 있는 응용프로그램에서 울부짖는 비트맵을 찾아볼 수 있습니다. 다양한 프로그래밍 언어에 대한 구현이 이미 엄청나게 많이 존재하며, Go에 대한 구현도 3개 이상 있습니다.

높은 카디널리티를 처리하는 데 도움이 되는 또 다른 접근 방식은 비닝(binning)이라고 합니다. 사람의 키를 나타내는 필드가 있다고 상상해 보세요. 키는 부동 소수점 숫자이지만 우리 인간은 키를 그런 식으로 생각하지 않습니다. 우리의 키는 185,2cm와 185,3cm 사이에 차이가 없습니다.

1cm 이내에서 비슷한 값을 갖는 그룹끼리 그룹화할 수 있는 것으로 나타났습니다.

그리고 키가 50cm보다 작고 키가 250cm보다 큰 사람이 거의 없다는 것을 알고 있다면, 본질적으로 무한한 기수를 갖는 필드를 약 200개의 값의 기수를 갖는 필드로 바꿀 수 있습니다.

물론 필요하다면 나중에 추가 필터링을 할 수도 있습니다.

고대역폭 문제

비트맵 인덱스의 또 다른 문제점은 업데이트 비용이 매우 많이 든다는 것입니다.

데이터베이스는 잠재적으로 수백 개의 다른 쿼리가 데이터를 검색하는 동안에도 데이터를 업데이트할 수 있는 기능을 제공해야 합니다. 동시 접근 문제나 기타 공유 문제를 방지하려면 잠금이 필요합니다. 그리고 큰 잠금 장치가 하나 있는 경우, 이 잠금 장치가 병목 현상을 일으킬 때 잠금 경합이라는 문제가 발생합니다.

이 문제는 샤딩이나 버전 관리된 인덱스를 사용하면 해결하거나 우회할 수 있습니다.

샤딩은 간단하고 잘 알려진 것입니다. 다른 데이터를 샤딩하는 것과 마찬가지로 비트맵 인덱스를 샤딩할 수 있습니다. 하나의 큰 잠금 대신 여러 개의 작은 잠금을 얻게 되어 잠금 경합이 없어집니다.

문제를 해결하는 두 번째 방법은 버전이 지정된 인덱스를 사용하는 것입니다. 검색이나 읽기에 사용할 색인 사본 한 부와 쓰기나 업데이트에 사용할 사본 한 부를 가질 수 있습니다. 그리고 특정 기간(예를 들어 100ms 또는 500ms)마다 한 번씩 이를 복제하고 바꿉니다. 물론, 이러한 접근 방식은 애플리케이션이 약간 지연되는 검색 인덱스를 처리할 수 있는 경우에만 적용할 수 있습니다.

이 두 가지 접근 방식은 동시에 사용할 수 있습니다. 즉, 분할된 버전 인덱스를 가질 수 있습니다.

더 복잡한 쿼리

비트맵 인덱스의 마지막 문제는 "범위" 쿼리와 같은 더 복잡한 유형의 쿼리에는 적합하지 않다는 것입니다.

사실, 생각해보면 AND, OR 등의 비트 연산은 "200박 객실 요금이 300~XNUMX달러인 호텔을 보여주세요"와 같은 쿼리에는 그다지 적합하지 않습니다.

순진하고 매우 어리석은 해결책은 각 달러 가치에 대한 결과를 가져와 비트 OR 연산으로 결합하는 것입니다.

조금 더 정확한 해결책은 그룹화를 사용하는 것입니다. 예를 들어, 50달러 단위입니다. 그렇게 되면 프로세스 속도가 50배 빨라질 겁니다.

하지만 이 문제는 이러한 유형의 쿼리에 맞춰 특별히 만든 뷰를 사용하면 쉽게 해결할 수 있습니다. 과학 논문에서는 이를 범위 인코딩된 비트맵이라고 부릅니다.

이 표현에서는 단지 한 비트만 어떤 값(예: 200)으로 설정하는 것이 아니라, 해당 값과 그 위의 모든 값을 설정합니다. 200 이상. 300도 동일: 300 이상. 등.

이 표현을 사용하면 인덱스를 두 번만 탐색하여 이러한 종류의 검색 쿼리에 답할 수 있습니다. 먼저, 객실 요금이 300달러 이하인 호텔 목록을 구한 다음, 객실 요금이 199달러 이하인 호텔 목록을 제거합니다. 준비가 된.

놀라실지 모르지만, 비트맵 인덱스를 사용하면 지오쿼리도 가능합니다. 비결은 좌표를 기하학적 모양으로 둘러싼 지리적 표현을 사용하는 것입니다. 예를 들어, Google의 S2입니다. 도형은 번호를 매길 수 있는 세 개 이상의 교차하는 선으로 표현될 수 있어야 합니다. 이런 식으로 우리는 지리 쿼리를 "간격별"(번호가 매겨진 줄을 따라)로 여러 개의 쿼리로 바꿀 수 있습니다.

Ready 솔루션

제가 여러분의 관심을 조금이라도 끌었기를 바라며, 이제 여러분의 무기고에 또 다른 유용한 도구가 생기기를 바랍니다. 이런 일이 생기면 어느 방향으로 가야 할지 알게 될 겁니다.

하지만 모든 사람이 처음부터 비트맵 인덱스를 만들 시간과 인내심, 리소스를 갖고 있는 것은 아닙니다. 특히 SIMD를 사용하는 등 더욱 진보된 방식이 그렇습니다.

다행히도 여러분을 도울 수 있는 몇 가지 기성 솔루션이 있습니다.

울부짖는 비트맵

첫째, 제가 이미 언급한 것과 같은 울부짖는 비트맵 라이브러리가 있습니다. 여기에는 본격적인 비트맵 인덱스를 만드는 데 필요한 모든 컨테이너와 비트 연산이 포함되어 있습니다.

안타깝게도 현재 Go 구현 중 어느 것도 SIMD를 사용하지 않습니다. 즉, 예를 들어 Go 구현은 C 구현보다 성능이 떨어집니다.

필로사

도움이 될 수 있는 또 다른 제품은 Pilosa DBMS인데, 이 제품은 기본적으로 비트맵 인덱스만 가지고 있습니다. 이는 비교적 새로운 솔루션이지만 놀라운 속도로 사람들의 마음을 사로잡고 있습니다.

Pilosa는 내부적으로 울부짖는 비트맵을 사용하고 이를 사용할 수 있는 기능을 제공하며, 위에서 언급한 모든 것(그룹화, 범위 인코딩 비트맵, 필드 개념 등)을 단순화하고 설명합니다.

이미 익숙한 질문에 답하기 위해 Pilosa를 사용하는 예를 잠깐 살펴보겠습니다.

이 예는 앞서 본 것과 매우 유사합니다. Pilosa 서버에 대한 클라이언트를 만들고, 인덱스와 필요한 필드를 만든 다음, 필드를 확률이 포함된 무작위 데이터로 채운 후 마지막으로 익숙한 쿼리를 실행합니다.

그런 다음 "비싼" 필드를 NOT하고, 그 결과를 "테라스" 필드와 "예약" 필드와 교차(또는 AND)합니다. 그리고 마지막으로, 우리는 최종 결과를 얻습니다.

저는 가까운 미래에 MySQL과 PostgreSQL과 같은 DBMS에도 이러한 새로운 유형의 인덱스, 즉 비트맵 인덱스가 도입되기를 바랍니다.

결론

아직 잠들지 않으셨다면 감사합니다. 제한된 시간으로 인해 많은 주제에 대해 간단히 언급해야 했지만, 제가 전한 이야기가 유익하고 심지어 동기를 부여하는 데 도움이 되었기를 바랍니다.

비트맵 인덱스는 지금 당장 필요하지 않더라도 알아두면 좋습니다. 이것을 여러분의 도구상자에 추가되는 또 다른 도구로 삼으세요.

우리는 Go의 다양한 성능 향상 기법과 Go 컴파일러가 아직 잘하지 못하는 부분을 살펴보았습니다. 이건 분명히 모든 Go 프로그래머가 알아야 할 내용이에요.

제가 말씀드리고 싶었던 것은 전부입니다. 감사합니다!

출처 : habr.com