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

소개

나는 이 보고서를 모스크바에서 열린 GopherCon Russia 2019 컨퍼런스에서 영어로, 니즈니 노브고로드에서 열린 모임에서 러시아어로 제공했습니다. 우리는 비트맵 인덱스에 대해 이야기하고 있습니다. B-트리보다 덜 일반적이지만 덜 흥미롭지는 않습니다. 나누는 기록 회의에서 영어로 된 연설과 러시아어로 된 텍스트 사본.

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

내 작품이 여러분에게 유용하고 흥미로울 수 있기를 진심으로 바랍니다. 가다!

소개

http://bit.ly/bitmapindexes
https://github.com/mkevac/gopherconrussia2019

안녕하세요 여러분! 저녁 XNUMX시인데 우리 모두 너무 피곤해요. 지루한 데이터베이스 인덱스 이론에 대해 이야기하기에 좋은 시간이죠? 걱정하지 마십시오. 여기저기에 몇 줄의 소스 코드가 있을 것입니다. 🙂

농담은 제쳐두고, 보고서는 정보로 가득 차 있어서 시간이 별로 없습니다. 그럼 시작해 보겠습니다.

오늘은 다음과 같은 내용을 이야기하겠습니다.

• 인덱스란 무엇입니까?
• 비트맵 인덱스란 무엇입니까?
• 사용되는 곳과 사용되지 않는 곳, 그리고 그 이유
• Go에서의 간단한 구현과 컴파일러와의 약간의 어려움;
• Go 어셈블러에서는 약간 덜 단순하지만 훨씬 더 생산적인 구현입니다.
• 비트맵 인덱스의 "문제";
• 기존 구현.

그렇다면 인덱스란 무엇인가?

인덱스는 주요 데이터 외에 당사가 유지 관리하고 업데이트하는 별도의 데이터 구조입니다. 검색 속도를 높이는 데 사용됩니다. 인덱스가 없으면 검색을 수행하려면 데이터를 완전히 검색해야 하며(전체 스캔이라는 프로세스) 이 프로세스는 선형 알고리즘 복잡도를 갖습니다. 그러나 데이터베이스에는 일반적으로 엄청난 양의 데이터가 포함되어 있으며 선형 복잡성이 너무 느립니다. 이상적으로는 로그 또는 상수 값을 얻습니다.

이는 미묘함과 장단점으로 가득 찬 매우 복잡한 주제입니다. 하지만 수십 년간의 데이터베이스 개발 및 연구를 살펴본 후에는 데이터베이스 인덱스 생성에 널리 사용되는 접근 방식이 몇 가지 밖에 없다고 말하고 싶습니다.

첫 번째 접근 방식은 검색 공간을 더 작은 부분으로 나누어 검색 공간을 계층적으로 줄이는 것입니다.

우리는 일반적으로 다양한 유형의 트리를 사용하여 이 작업을 수행합니다. 예를 들어 옷장에 여러 주제로 나누어진 작은 자료 상자가 들어 있는 큰 자료 상자가 있습니다. 자료가 필요하신 분들은 아마도 '쿠키'라고 적힌 상자보다는 '재료'라고 적힌 상자에서 찾으시겠죠?

두 번째 접근 방식은 원하는 요소 또는 요소 그룹을 즉시 선택하는 것입니다. 해시 맵이나 역방향 인덱스에서 이를 수행합니다. 해시 맵을 사용하는 것은 이전 예와 매우 유사하지만 상자 상자 대신 옷장에 최종 항목이 담긴 작은 상자가 많이 있습니다.

세 번째 접근 방식은 검색의 필요성을 없애는 것입니다. Bloom 필터나 Cuckoo 필터를 사용하여 이를 수행합니다. 첫 번째 답변은 즉시 답변을 제공하므로 검색할 필요가 없습니다.

마지막 접근 방식은 최신 하드웨어가 제공하는 모든 기능을 최대한 활용하는 것입니다. 이것이 바로 비트맵 인덱스에서 수행하는 작업입니다. 예, 이를 사용할 때 때때로 전체 색인을 살펴봐야 하지만 매우 효율적으로 수행합니다.

앞서 말했듯이 데이터베이스 인덱스라는 주제는 방대하고 타협으로 가득 차 있습니다. 이는 때때로 여러 접근 방식을 동시에 사용할 수 있음을 의미합니다. 검색 속도를 더욱 높여야 하거나 가능한 모든 검색 유형을 포괄해야 하는 경우입니다.

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

이 주제에 관해 나는 누구에게 말해야 합니까?

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

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

비트맵 인덱스는 이름에서 알 수 있듯이 비트맵 또는 비트 세트를 사용하여 검색 인덱스를 구현합니다. 조감도에서 볼 때 이 인덱스는 모든 엔터티(예: 사람)와 해당 속성 또는 매개변수(나이, 눈 색깔 등)를 나타내는 하나 이상의 비트맵과 비트 연산(AND, OR, NOT을 사용하는 알고리즘)으로 구성됩니다. ) 검색어에 답합니다.

비트맵 인덱스는 카디널리티가 낮은 여러 열에 걸쳐 쿼리를 결합하는 검색이 있는 경우("눈 색깔" 또는 "결혼 상태"와 "도심으로부터의 거리" 등을 비교)에 가장 적합하고 성능이 매우 높다고 들었습니다. 그러나 나중에 카디널리티가 높은 열에도 잘 작동한다는 것을 보여 드리겠습니다.

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

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

• 지하철 근처;
• 전용 주차장이 있습니다.
• 베란다(테라스가 있음)가 있습니다.
• 테이블을 예약할 수 있습니다(예약 가능).
• 채식주의자에게 적합(완전 채식주의자 친화적)
• 비싸다(비싸다).

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

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

• “채식주의자 친화적인 레스토랑을 보여주세요”;
• “테이블을 예약할 수 있는 베란다가 있고 저렴한 레스토랑을 보여주세요.”

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


두 번째 요청은 좀 더 복잡합니다. 저렴한 레스토랑 목록을 얻으려면 "비싼" 비트맵에서 NOT 비트맵을 사용한 다음 "테이블을 예약할 수 있나요?" 비트맵과 AND 결과를 "베란다가 있습니다" 비트맵과 AND 결과로 얻어야 ​​합니다. 결과 비트맵에는 모든 기준을 충족하는 시설 목록이 포함됩니다. 이 예에서는 Yunost 레스토랑만 해당됩니다.


관련된 많은 이론이 있지만 걱정하지 마십시오. 곧 코드를 보게 될 것입니다.

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

Google 비트맵 인덱스를 검색하면 답변의 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바이트 청크로 작업하도록 코드를 매우 쉽게 조정할 수 있습니다.

보시다시피, 이 작은 변화로 인해 배치 크기가 XNUMX배 증가하여 프로그램 속도가 XNUMX배 향상되었습니다. 이득은 선형적이라고 할 수 있습니다.

어셈블러로 구현

그러나 이것이 끝이 아닙니다. 우리 프로세서는 16, 32, 심지어 64바이트 단위로 작업할 수 있습니다. 이러한 "광범위한" 연산을 단일 명령어 다중 데이터(SIMD; 하나의 명령어, 많은 데이터)라고 하며, 이러한 연산을 사용하도록 코드를 변환하는 프로세스를 벡터화라고 합니다.

불행하게도 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 프로그램의 가장 간단한 예입니다. 우리는 두 개의 숫자를 더하는 것을 의미하는 Add() 함수를 정의하는 main() 함수를 가지고 있습니다. 여기에는 이름으로 매개변수를 가져오고 적합한 무료 프로세서 레지스터 중 하나를 가져오는 도우미 함수가 있습니다. ADDQ에서 볼 수 있듯이 각 프로세서 작업에는 avo에 해당 기능이 있습니다. 마지막으로 결과 값을 저장하기 위한 도우미 함수를 볼 수 있습니다.

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

• Go 어셈블러의 결과 코드로 add.s;
• stub.go에는 Go와 어셈블러라는 두 세계를 연결하는 함수 헤더가 있습니다.

이제 avo가 수행하는 작업과 방법을 살펴보았으므로 기능을 살펴보겠습니다. 저는 함수의 스칼라 버전과 벡터(SIMD) 버전을 모두 구현했습니다.

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

이전 예에서와 같이 무료이고 유효한 범용 레지스터를 요청하므로 인수에 대한 오프셋과 크기를 계산할 필요가 없습니다. avo는 우리를 위해 이 모든 작업을 수행합니다.

우리는 성능을 향상하고 Go 컴파일러를 속이기 위해 레이블과 goto(또는 점프)를 사용했지만 이제는 처음부터 이를 수행하고 있습니다. 요점은 사이클이 더 높은 수준의 개념이라는 것입니다. 어셈블러에는 레이블과 점프만 있습니다.

나머지 코드는 이미 익숙하고 이해하기 쉬워야 합니다. 레이블과 점프가 포함된 루프를 에뮬레이트하고, 두 슬라이스에서 작은 데이터 조각을 가져와서 비트 연산으로 결합한 다음(이 경우에는 아님) 결과를 결과 슬라이스에 넣습니다. 모두.

이것이 최종 어셈블러 코드의 모습입니다. 오프셋과 크기(녹색으로 강조 표시)를 계산하거나 사용된 레지스터(빨간색으로 강조 표시)를 추적할 필요가 없었습니다.

어셈블리 언어 구현의 성능과 Go에서 최상의 구현 성능을 비교해 보면 동일하다는 것을 알 수 있습니다. 그리고 이것은 예상됩니다. 결국 우리는 특별한 일을 하지 않았습니다. Go 컴파일러가 수행하는 작업을 재현했을 뿐입니다.

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

이것이 바로 어셈블리 언어의 작은 함수로 어떤 이점도 얻을 수 없는 이유입니다. 대규모 함수를 작성하거나, 새로운 math/bits 패키지를 사용하거나, 어셈블러 언어를 우회해야 합니다.

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

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

한 가지 혁신은 더 넓은 벡터 연산이 특별한 와이드 레지스터를 사용한다는 것입니다. 32바이트 청크의 경우 레지스터 앞에 Y가 붙습니다. 이것이 바로 코드에 YMM() 함수가 보이는 이유입니다. 512비트 청크와 함께 AVX-64를 사용하는 경우 접두사는 Z입니다.

두 번째 혁신은 루프 언롤링(loop unrolling)이라는 최적화를 사용하기로 결정한 것입니다. 이는 루프 시작으로 점프하기 전에 수동으로 XNUMX개의 루프 작업을 수행하는 것을 의미합니다. 이 최적화는 코드의 분기 수를 줄이고 사용 가능한 무료 레지스터 수에 따라 제한됩니다.

그렇다면 성능은 어떻습니까? 그녀는 아름답다! 우리는 최고의 Go 솔루션에 비해 약 XNUMX배의 속도 향상을 달성했습니다. 인상적이죠?

그러나 이 구현조차도 AVX-512, 프리패치 또는 쿼리 스케줄러용 JIT(Just-In-Time 컴파일러)를 사용하여 잠재적으로 가속화될 수 있습니다. 그러나 이것은 확실히 별도의 보고서 주제입니다.

비트맵 인덱스 문제

이제 우리는 Go에서 비트맵 인덱스의 간단한 구현과 어셈블리 언어에서 훨씬 더 생산적인 구현을 이미 살펴보았으므로 마지막으로 비트맵 인덱스가 거의 사용되지 않는 이유에 대해 이야기하겠습니다.

이전 논문에서는 비트맵 인덱스와 관련된 세 가지 문제를 언급했지만 최신 논문과 나는 이것이 더 이상 관련이 없다고 주장합니다. 우리는 이러한 문제 각각을 깊이 다루지는 않고 피상적으로 살펴볼 것입니다.

높은 카디널리티의 문제

따라서 비트맵 인덱스는 카디널리티가 낮은 필드, 즉 값이 거의 없는 필드(예: 성별 또는 눈 색깔)에만 적합하다고 들었습니다. 그 이유는 이러한 필드의 일반적인 표현(하나 값당 비트) 카디널리티가 높은 경우 너무 많은 공간을 차지하며 더욱이 이러한 비트맵 인덱스는 제대로 채워지지 않습니다(드물게).


때로는 숫자를 표현하는 데 사용하는 표준 표현과 같은 다른 표현을 사용할 수도 있습니다. 그러나 모든 것을 변화시킨 것은 압축 알고리즘의 출현이었습니다. 지난 수십 년 동안 과학자와 연구자들은 비트맵에 대한 수많은 압축 알고리즘을 생각해 냈습니다. 주요 장점은 비트 작업을 수행하기 위해 비트맵의 압축을 풀 필요가 없다는 것입니다. 압축된 비트맵에서 직접 비트 작업을 수행할 수 있습니다.

최근에는 비트맵과 같은 하이브리드 방식이 등장하기 시작했습니다. 그들은 비트맵에 대해 세 가지 다른 표현(비트맵 자체, 배열 및 소위 비트 실행)을 동시에 사용하고 이들 간의 균형을 유지하여 성능을 최대화하고 메모리 소비를 최소화합니다.

가장 인기 있는 응용 프로그램에서 활발한 비트맵을 찾을 수 있습니다. Go에 대한 세 가지 이상의 구현을 포함하여 이미 다양한 프로그래밍 언어에 대한 수많은 구현이 있습니다.

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

유사한 값을 1cm 이내의 그룹으로 그룹화할 수 있음이 밝혀졌습니다.

그리고 키가 50cm보다 작고 키가 250cm보다 큰 사람이 거의 없다는 사실도 알고 있다면 기본적으로 무한 카디널리티가 있는 필드를 약 200개 값의 카디널리티가 있는 필드로 바꿀 수 있습니다.

물론 필요한 경우 나중에 추가 필터링을 수행할 수도 있습니다.

고대역폭 문제

비트맵 인덱스의 다음 문제는 업데이트하는 데 비용이 매우 많이 든다는 것입니다.

데이터베이스는 잠재적으로 수백 개의 다른 쿼리가 데이터를 검색하는 동안 데이터를 업데이트할 수 있어야 합니다. 동시 데이터 액세스 또는 기타 공유 문제로 인한 문제를 방지하려면 잠금이 필요합니다. 그리고 하나의 큰 잠금이 있는 곳에는 문제가 있습니다. 즉, 이 잠금이 병목 현상을 일으키면 잠금 경합이 발생합니다.

이 문제는 샤딩을 사용하거나 버전이 지정된 인덱스를 사용하여 해결하거나 회피할 수 있습니다.

샤딩은 간단하고 잘 알려진 것입니다. 다른 데이터와 마찬가지로 비트맵 인덱스를 샤딩할 수 있습니다. 하나의 큰 잠금 대신 여러 개의 작은 잠금을 확보하여 잠금 경합을 제거합니다.

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

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

더 복잡한 쿼리

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

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

순진하고 매우 현명하지 못한 해결책은 각 달러 값에 대한 결과를 가져와 이를 비트별 OR 연산과 결합하는 것입니다.

약간 더 나은 해결책은 그룹화를 사용하는 것입니다. 예를 들어 50달러 그룹으로 구성됩니다. 이렇게 하면 프로세스 속도가 50배 빨라집니다.

그러나 이러한 유형의 요청을 위해 특별히 생성된 보기를 사용하면 문제가 쉽게 해결됩니다. 과학 논문에서는 이를 범위 인코딩 비트맵이라고 합니다.

이 표현에서는 일부 값(예: 200)에 대해 200비트만 설정하는 것이 아니라 이 값과 모든 값을 더 높게 설정합니다. 300 이상. 300:XNUMX 이상에서도 마찬가지입니다. 등등.

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

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

Ready 솔루션

제가 여러분에게 약간의 관심을 가졌기를 바라며 이제 여러분의 무기고에 또 다른 유용한 도구가 생겼기를 바랍니다. 이와 같은 작업을 수행해야 하는 경우 어떤 방법으로 봐야 할지 알게 될 것입니다.

그러나 모든 사람이 비트맵 인덱스를 처음부터 만들 수 있는 시간, 인내심 또는 리소스를 갖고 있는 것은 아닙니다. 예를 들어 SIMD를 사용하는 고급 기능은 특히 그렇습니다.

다행히도 도움이 될 수 있는 몇 가지 기성 솔루션이 있습니다.

윙윙거리는 비트맵

첫째, 제가 이미 이야기한 것과 동일한 강력한 비트맵 라이브러리가 있습니다. 여기에는 본격적인 비트맵 인덱스를 만드는 데 필요한 모든 컨테이너와 비트 작업이 포함되어 있습니다.

불행히도 현재 Go 구현 중 SIMD를 사용하는 것은 없습니다. 이는 예를 들어 Go 구현이 C 구현보다 성능이 낮다는 것을 의미합니다.

필로사

도움이 될 수 있는 또 다른 제품은 실제로 비트맵 인덱스만 있는 Pilosa DBMS입니다. 이는 비교적 새로운 솔루션이지만 빠른 속도로 마음을 사로잡고 있습니다.

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

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

이 예는 이전에 본 것과 매우 유사합니다. Pilosa 서버에 대한 클라이언트를 생성하고 인덱스와 필수 필드를 생성한 다음 확률이 있는 임의의 데이터로 필드를 채우고 마지막으로 익숙한 쿼리를 실행합니다.

그런 다음 "비싼" 필드에 NOT을 사용한 다음 결과(또는 AND)를 "테라스" 필드 및 "예약" 필드와 교차합니다. 그리고 마침내 최종 결과를 얻습니다.

가까운 미래에 이 새로운 유형의 인덱스가 MySQL 및 PostgreSQL과 같은 DBMS(비트맵 인덱스)에도 나타나기를 진심으로 바랍니다.

결론

아직 잠들지 않으셨다면, 감사합니다. 시간이 부족하여 많은 주제를 간략히 다루어야 했지만, 그 강연이 유익하고 동기부여가 되었기를 바랍니다.

비트맵 인덱스는 지금 당장 필요하지 않더라도 알아두면 좋습니다. 도구 상자의 또 다른 도구가 되도록 하십시오.

우리는 Go에 대한 다양한 성능 요령과 Go 컴파일러가 아직 잘 처리하지 못하는 것들을 살펴보았습니다. 그러나 이것은 모든 Go 프로그래머가 알아야 할 절대적으로 유용합니다.

그것이 내가 당신에게 말하고 싶은 전부입니다. 감사합니다!

출처 : habr.com