Course All lectures for KO purposes - Lecture: 샤딩: 뒷면

2.1 어떻게 샤딩하고 N번 느리게 하는가?

다음과 같이 정확히 N번 샤딩하고 속도를 늦출 수 있습니다.

docs00...docs15 요청을 병렬 이 아닌 순차적으로 보냅니다.
간단한 쿼리에서는 키가 아닌 WHERE something=234 로 선택합니다 .

이 경우 직렬화된 부분(serial)은 1%도 아니고 5%도 아닌 현대 데이터베이스에서 20% 정도를 차지한다. 매우 효율적인 바이너리 프로토콜을 사용하여 데이터베이스에 액세스하거나 동적 라이브러리로 Python 스크립트에 연결하면 직렬화된 부분의 50%를 얻을 수도 있습니다.

단순 요청의 나머지 처리 시간은 요청 구문 분석, 계획 준비 등 병렬화할 수 없는 작업에 사용됩니다. 즉, 레코드를 읽지 않으면 속도가 느려집니다.

데이터를 16개의 테이블로 나누고 순차적으로 실행하면 예를 들어 PHP 프로그래밍 언어에서 관례적인 것처럼(비동기 프로세스를 시작하는 데 그다지 좋지 않음) 16배 느려집니다. 그리고 네트워크 왕복도 추가될 것이기 때문에 아마도 훨씬 더 많을 것입니다.

갑자기 샤딩할 때 프로그래밍 언어의 선택이 중요합니다.

프로그래밍 언어 선택에 대해 기억하세요. 쿼리를 데이터베이스(또는 검색 서버)에 순차적으로 보내면 가속화는 어디에서 오는가? 오히려 속도가 느려질 것입니다.

2.2 반자동에 대하여

장소에서는 정보 기술의 정교함이 chthonic 공포를 불러일으킵니다. 예를 들어, MySQL은 기본적으로 특정 버전에 샤딩을 구현하지 않았지만 전투에서 사용되는 데이터베이스의 크기가 부적절한 값으로 커집니다.

개별 DBA 앞에서 고통받는 인류는 수년 동안 괴로워했으며 아무것도 기반으로 여러 가지 나쁜 샤딩 솔루션을 작성합니다. 그 후 ProxySQL(MariaDB/Spider, PG/pg_shard/Citus, ...)이라는 괜찮은 샤딩 솔루션이 작성됩니다. 이것은 바로 이 얼룩의 잘 알려진 예입니다.

ProxySQL은 물론 오픈 소스, 라우팅 등을 위한 완전한 엔터프라이즈급 솔루션입니다. 그러나 해결해야 할 과제 중 하나는 데이터베이스 자체에 대한 샤딩인데, 데이터베이스 자체는 인간의 방식으로 샤딩할 수 없습니다. 알다시피, "shards = 16" 스위치가 없습니다. 응용 프로그램의 각 요청을 다시 작성해야 하고 많은 요청이 제자리에 있거나 응용 프로그램과 데이터베이스 사이에 다음과 같이 보이는 중간 계층을 배치해야 합니다. ... SELECT * 문서에서? 예, 16개의 작은 SELECT * FROM server1.document1, SELECT * FROM server2.document2로 나누어야 합니다. 이러한 로그인/비밀번호가 있는 이 서버로, 다른 서버로 이 서버로. 대답하지 않으면 ... "등 정확히 이것은 중간 얼룩에 의해 수행될 수 있습니다. 모든 데이터베이스보다 약간 적습니다. PostgreSQL의 경우 내가 이해하는 한

각 특정 패치를 구성하는 것은 하나의 보고서에 맞지 않는 별도의 거대한 주제이므로 기본 개념에 대해서만 설명합니다. 버즈 이론에 대해 조금 이야기합시다.

2.3 절대 완벽한 자동화?

이 문자 F() 에서 샤딩의 경우 높아지는 전체 이론 , 기본 원칙은 대략 항상 동일합니다: shard_id = F(객체).

샤딩 - 그게 다 뭐야? 20억 개의 레코드(또는 64개)가 있습니다. 우리는 그것들을 여러 조각으로 나누고 싶습니다. 예기치 않은 질문이 발생합니다. 어떻게? 어떤 원칙에 따라 20억 개의 레코드(또는 64개)를 사용 가능한 16개의 서버에 분산시켜야 합니까?

우리 안에 잠재된 수학자는 결국 각 문서(객체, 선 등)에 대해 어떤 조각에 넣을 것인지를 결정하는 마법 함수가 항상 존재한다고 제안해야 합니다.

수학에 더 깊이 들어가면 이 함수는 항상 개체 자체(행 자체)뿐만 아니라 총 샤드 수와 같은 외부 설정에도 의존합니다. 각 개체에 대해 어디에 두어야 하는지 알려주는 함수는 시스템에 있는 서버보다 더 많은 값을 반환할 수 없습니다. 그리고 기능은 약간 다릅니다.

shard_func = F1(object); 
shard_id = F2(shard_func, ...); 
shard_id = F2(F1(object), current_num_shards, ...).

그러나 더 나아가 이러한 개별 함수의 야생을 파헤치지 않고 마법 함수 F()가 무엇인지에 대해서만 이야기할 것입니다.

2.4 F()란?

그들은 다양하고 다양한 구현 메커니즘을 제시할 수 있습니다. 샘플 요약:

F = rand() % nums_shards
F = somehash(object.id) % num_shards
F = object.date % num_shards
F = object.user_id % num_shards
...
F = shard_table [ somehash() |… object.date |… ]

흥미로운 사실은 모든 데이터를 자연스럽게 무작위로 분산시킬 수 있다는 것입니다. 우리는 임의의 서버, 임의의 코어, 임의의 테이블에 다음 레코드를 던집니다. 이것에 큰 행복은 없지만 효과가 있습니다.

재현 가능하거나 일관된 해시 함수로 샤딩하거나 일부 속성으로 샤딩하는 약간 더 지능적인 방법이 있습니다. 각 방법을 살펴보겠습니다.

F = 랜드()

주위에 흩어지는 것은 그다지 올바른 방법이 아닙니다. 한 가지 문제: 우리는 20억 개의 레코드를 천 대의 서버에 무작위로 분산시켰는데 레코드가 어디에 있는지 모릅니다. user_1을 꺼내야 하는데 어디에 있는지 모릅니다. 우리는 수천 대의 서버로 가서 모든 것을 분류합니다. 이것은 비효율적입니다.

F = 썸해시()

성인 방식으로 사용자를 분산시키자. user_id에서 재현 가능한 해시 함수를 계산하고 나머지를 서버 수로 나눈 다음 원하는 서버에 즉시 연락하십시오.

왜 이러는 거지? 그런 다음 로드가 많고 하나의 서버에 맞는 것이 없습니다. 그것이 맞다면 인생은 너무 단순 할 것입니다.

좋아요, 상황은 이미 개선되었습니다. 하나의 레코드를 얻으려면 미리 알려진 서버로 이동합니다. 그러나 키 범위가 있는 경우 이 전체 범위에서 키의 모든 값을 살펴보고 범위 내 키가 있는 만큼의 샤드로 이동하거나 심지어 각 서버. 물론 상황은 개선되었지만 모든 요청에 대해 그런 것은 아닙니다. 일부 쿼리가 영향을 받았습니다.

자연 샤딩(F = object.date % num_shards)

때때로, 즉 종종 트래픽의 95%와 부하의 95%가 일종의 자연적인 샤딩이 있는 요청입니다. 예를 들어 조건부 소셜 분석 쿼리의 95%는 지난 1일, 3일, 7일 동안의 데이터에만 영향을 미치고 나머지 5%는 지난 몇 년을 참조합니다. 그러나 요청의 95%는 자연스럽게 날짜별로 샤딩되므로 시스템 사용자의 관심은 지난 며칠에 집중됩니다.

이 경우 예를 들어 하루와 같이 날짜별로 데이터를 나누고 어떤 날에 대한 보고서 요청 또는 오늘부터 이 샤드까지 개체에 대한 응답을 따라 이동할 수 있습니다.

삶이 개선되고 있습니다. 이제 우리는 특정 물체의 위치를 알 뿐만 아니라 범위도 알고 있습니다. 날짜 범위가 아니라 다른 열 범위에 대한 요청을 받으면 당연히 모든 샤드를 살펴봐야 합니다. 그러나 게임의 규칙에 따라 그러한 요청은 5%에 불과합니다.

우리는 모든 것에 대한 이상적인 해결책을 제시한 것 같지만 두 가지 문제가 있습니다.

이 솔루션은 요청의 95%가 마지막 주에만 관련되는 특정 사례에 맞게 조정됩니다.
요청의 95%가 지난 주에 닿기 때문에 지난 주에 서비스를 제공하는 하나의 샤드에 모두 해당됩니다. 이 시간 동안 다른 모든 조각이 유휴 상태인 동안 이 조각은 녹을 것입니다. 동시에 버릴 수 없으며 아카이브 데이터도 저장해야 합니다.

이것이 나쁜 샤딩 체계라는 것은 말할 것도 없습니다. 그럼에도 불구하고 우리는 핫 데이터를 차단하지만 가장 핫한 샤드로 무언가를 수행해야 합니다.

문제는 장난, 점프 및 찜질, 즉 불타는 현재 날짜의 복제본 수가 증가한 다음 오늘이 과거가되어 아카이브로 들어가면 복제본 수가 점진적으로 감소하여 해결됩니다. "잘못된 방식으로 매직 해시 함수를 사용하여 클러스터 전체에 데이터를 분산하면 됩니다"라는 이상적인 솔루션은 없습니다.

2.5 지불할 가격

공식적으로 우리는 이제 "모든 것"을 알고 있음을 압니다. 사실, 우리는 하나의 큰 두통과 두 개의 작은 두통을 모릅니다.

1. 단순 통증: 심하게 번짐

이것은 전투에서 거의 발생하지 않지만 갑자기 발생하는 교과서의 예입니다.

예를 들어 날짜가 있고 날짜가 없는 경우에만!
의도하지 않은 고르지 않은 (인지할 수 있는) 배포.

샤딩 메커니즘을 선택했거나 데이터가 변경되었으며, 물론 PM이 요구 사항을 전달하지 않았고(코드에 오류가 없으며 PM이 항상 요구 사항을 보고하지 않음) 배포가 엄청나게 고르지 않게되었습니다. 즉, 그들은 기준을 놓쳤습니다.

잡으려면 파편의 크기를 봐야 합니다. 샤드 중 하나가 과열되거나 다른 샤드보다 100배 커지는 순간 문제를 분명히 보게 될 것입니다. 키나 샤딩 기능을 교체하여 간단하게 고칠 수 있습니다.

이것은 간단한 문제입니다. 솔직히 말해서 적어도 백 명 중 한 명은 인생에서 이것에 부딪칠 것이라고 생각하지 않지만 갑자기 적어도 누군가를 도울 것입니다.

2. "천하무적" 고통: 집계, 조인

다른 테이블의 10억 개의 레코드에 대해 한 테이블의 10억 개의 레코드를 결합하는 선택을 만드는 방법은 무엇입니까?

"빠르게" 계산하는 방법... randcol이 aaa와 bbb 사이에 있습니까?
"현명하게" 수행하는 방법... users_32shards JOIN posts_1024 shards?

짧은 대답: 안 돼요, 고생하세요!

첫 번째 테이블의 1000개 서버에 10억 개의 레코드를 배포하여 더 빠르게 작업하고 두 번째 테이블에서도 동일한 작업을 수행했다면 자연스럽게 1000~1000개의 서버가 쌍으로 서로 통신해야 합니다. 백만 개의 연결은 제대로 작동하지 않습니다. 샤딩과 잘 맞지 않는 데이터베이스(검색, 스토리지, 문서 저장소 또는 분산 파일 시스템)에 대한 요청을 하면 이러한 요청이 크게 느려집니다.

중요한 점은 일부 요청은 항상 성공적이지 못하고 속도가 느려진다는 것 입니다 . 비율을 최소화하는 것이 중요합니다. 결과적으로 10억 x 10억 레코드로 거대한 조인을 만들 필요가 없습니다. 거대한 공유 테이블에 조인하는 작은 테이블을 모든 노드에 복제하는 것이 가능하다면 그렇게 해야 합니다. 조인이 어떤 식으로든 실제로 로컬인 경우 예를 들어 사용자와 그의 게시물을 나란히 배치하고 동일한 방식으로 분할하고 동일한 시스템 내에서 모든 조인을 수행할 수 있습니다. 그렇게 해야 합니다. .

이것은 3 일 동안의 별도 강의이므로 마지막 지옥 같은 고통과 그것을 다루는 다른 알고리즘으로 넘어 갑시다.

2.6. 복잡하고 긴 고통: 리샤딩

준비하세요. 생애 처음으로 데이터를 샤딩했다면 평균적으로 데이터를 5번 더 샤딩하게 됩니다.

구성하는 클러스터 수에 관계없이 여전히 리샤딩해야 합니다.

매우 똑똑하고 운이 좋다면 적어도 한 번은 오버샤딩을 하십시오. 그러나 일단 확실해지면 사용자에게 10단위가 충분하다고 생각하는 순간 누군가가 30단위에 대한 요청을 작성하고 100단위의 알 수 없는 리소스에 대한 요청을 계획하고 있기 때문입니다. 샤드만으로는 충분하지 않습니다. 어쨌든 첫 번째 샤딩 체계를 사용하면 놓칠 것입니다. 항상 추가할 서버 수를 늘리거나 다른 작업을 수행해야 합니다. 일반적으로 어떻게든 데이터를 다시 패키징해야 합니다.

좋은 2의 거듭제곱이 있으면 좋습니다. 16개의 서버 샤드가 있었는데 이제 32입니다. 17이면 더 재미있고 23은 2개의 vasimally 소수입니다. 데이터베이스는 어떻게 작동합니까? 아마도 내부에 어떤 종류의 마법이 있습니까?

정답은 다음과 같습니다. 아니요, 내부에는 마법이 없으며 내부에는 지옥이 있습니다.

다음으로 "손으로" 수행할 수 있는 작업을 고려할 것입니다. 아마도 "자동 기계"로 이해하게 될 것입니다.

이마에 #1. 모든 것을 재배치

모든 객체에 대해 NewF(객체)를 고려하고 새 샤드로 이동합니다.

NewF()=OldF() 매칭의 기회는 낮습니다.

거의 모든 것을 다루겠습니다.

오.

오래된 조각에서 새 조각으로 20억 개의 기록을 모두 옮기는 지옥은 없기를 바랍니다. 순진한 접근 방식은 이해할 수 있습니다. 17개의 시스템이 있고 6개의 시스템이 클러스터에 추가되었으며 20억 개의 레코드가 분류되었으며 17개의 시스템에서 23개의 시스템으로 이동되었습니다. 10년에 한 번, 아마 할 수도 있습니다. 그러나 전반적으로 그것은 나쁜 움직임입니다.

이마에 #2. 절반 재배치

다음 순진한 개선 사항(그런 어리석은 계획을 버리자)은 17대의 자동차가 23대로 리샤딩되는 것을 금지하고 항상 16대의 자동차를 32대의 자동차로 리샤딩할 것입니다! 그런 다음 이론에 따르면 데이터의 정확히 절반을 이동해야 하며 실제로는 이렇게 할 수도 있습니다.

모든 객체에 대해 NewF(객체)를 고려하고 새 샤드로 이동합니다.

엄격하게 2^N이었으나 이제는 엄격하게 2^(N+1) 샤드입니다.

NewF()=OldF()와 일치할 확률은 0.5입니다.

데이터의 약 50%를 전송합시다.

최적이지만 2의 거듭제곱에 대해서만 작동합니다.

원칙적으로 자동차 수 측면에서 2의 거듭 제곱에 대한 구속력을 제외하고는 모든 것이 좋습니다. 이상하게도 이 순진한 접근 방식은 효과가 있습니다.

이 경우 클러스터를 2의 거듭제곱으로 추가 분할하는 것도 최적입니다. 어쨌든 16대의 클러스터에 16대의 시스템을 추가하면 데이터의 절반, 즉 정확히 절반과 시프트를 이동해야 합니다.

좋아, 하지만 인류가 정말로 다른 어떤 것도 발명하지 않았는가? 질문은 호기심 많은 마음에서 나온다.

더 재미있는 #3. 일관된 해싱

물론 여기에는 일관된 해싱에 대한 원이 있는 그림이 필요합니다.

Google에서 "일관된 해싱"을 검색하면 원이 확실히 나오고 모든 결과가 원으로 채워집니다.

아이디어: 원에 샤드 식별자(해시)를 그리고 그 위에 해시된 서버 식별자를 표시해 봅시다. 서버를 추가해야 할 때 원에 새 지점을 배치하고 그 지점에 가까운 것으로 판명된 지점(가까운 지점만)을 재배치합니다.

샤드를 추가할 때 모든 것을 살펴보지 않고 2개의 "이웃"만 살펴보고 평균 1/n씩 이동합니다.

샤드를 삭제할 때: 삭제되는 샤드만 보고 이동합니다. 최적의 종류.

샤드 추가시 트래픽 최소화 측면에서 매우 효과적이며 정상적인 데이터 밸런싱 측면에서 절대적으로 역겹습니다. 많은 수의 컴퓨터에 배포하는 이러한 모든 개체를 해시할 때 상대적으로 고르지 않게 수행하기 때문입니다. 원 주변의 포인트 간격이 고르지 않고 각 특정 노드의 로드가 나머지 노드와 매우 다를 수 있습니다.

이 문제는 가상 노드의 마지막 줄에 의해 해결됩니다. 원의 각 노드, 각 서버는 하나 이상의 점으로 표시됩니다. 서버, 샤드 등을 추가하여 몇 가지 포인트를 추가하고 있습니다. 무언가를 제거할 때마다 그에 따라 몇 개의 포인트를 제거하고 데이터의 작은 부분을 이동합니다.

예를 들어 그러한 계획이 Cassandra 내부에 있기 때문에 나는이 공간에 대해 원으로 이야기하고 있습니다. 즉, 그녀가 노드 사이에서 레코드를 쫓기 시작했을 때 서클이 당신을 보고 있고 아마도 승인하지 않을 것임을 알고 있습니다.

그러나 첫 번째 방법에 비해 수명이 향상되었습니다. 샤드를 추가 / 제거 할 때 이미 모든 레코드가 아니라 일부만 살펴보고 일부만 이동합니다.

주의, 질문은 다음과 같습니다. 더 개선할 수 있습니까? 또한 샤드 로딩의 균일성을 개선합니까? 가능하다고 하네요!

더 재미있는 #4. 랑데부/HRW

다음 간단한 아이디어(자료가 교육적이므로 복잡하지 않음): shard_id = arg max hash(object_id, shard_id).

Rendezvous 해싱이라고 하는 이유는 모르겠지만 Highest Random Weight라고 하는 이유는 알고 있습니다. 다음과 같이 시각화하는 것은 매우 쉽습니다.

예를 들어 16개의 샤드가 있습니다. 어딘가에 넣어야 하는 각 개체(문자열)에 대해 샤드 번호의 개체에 따라 16개의 해시를 계산합니다. 가장 높은 해시 값을 가진 사람이 이깁니다.

이것은 소위 HRW-해싱, 일명 Rendezvous 해싱입니다. 막대기처럼 멍청한 조각의 수를 계산하는 체계는 먼저 원보다 눈에 더 쉽고 균일한 부하를 제공합니다.

유일한 부정적인 점은 새 샤드를 추가하는 것이 우리에게 더 나빠졌다는 것입니다. 새 샤드를 추가할 때 변경될 일부 해시가 남아 있어 모든 것을 검토해야 할 위험이 있습니다. 샤드 제거 기술은 크게 변경되지 않았습니다.

또 다른 문제는 샤드 수가 많아 연산량이 많다는 것입니다.

더 재미있는 #5. 더 많은 기술

흥미롭게도 연구는 멈추지 않고 Google은 매년 몇 가지 새로운 우주 기술을 발표합니다.

점프 해시 - Google '2014.
다중 프로브 - Google '2015.
자기부상-구글 '2016.

주제에 관심이 있다면 많은 논문을 읽을 수 있습니다. 나는 이 데이터를 제시하여 문제가 해결되지 않았으며 모든 데이터베이스에서 구현될 수 있는 슈퍼 솔루션이 없다는 것을 분명히 하기 위해 제시합니다. 지금까지 사람들은 논문을 옹호했습니다.

결론

Gallius Julius Caesar의 이름을 따서 명명된 샤딩이라는 중요한 기본 기술이 있습니다. 데이터가 하나의 서버에 맞지 않으면 20개의 서버로 분할해야 합니다.

이 모든 것을 배운 후에는 샤딩하지 않는 것이 더 낫다는 인상을 받아야 합니다. 샤딩하지 않는 것이 낫다고 판단했다면 이것이 올바른 느낌입니다. 100달러에 서버에 메모리를 추가하고 아무것도 샤딩하지 않을 수 있다면 그렇게 해야 합니다. 샤딩을 하면 복잡한 분산 시스템이 나타나 데이터를 앞뒤로 전송하고 아무도 모르는 곳에 데이터를 쌓습니다. 피할 수 있다면 피해야 한다.

손으로 하지 않는 것이 더 낫습니다. "기반"(검색, DFS, ...)이 자체적으로 샤딩할 수 있는 것이 좋습니다. 어쨌든 조만간 고부하가 발생하고 어떻게든 데이터를 분할해야 합니다. 기지가 스스로 할 수 있어도 문제가 발생하지 않는다는 것은 사실이 아닙니다. 알고리즘 근본주의에 대해 기억하십시오. 모든 것이 내부에서 어떻게 작동하는지 이해해야 합니다.

샤딩을 처음 설정하는 경우 F()를 신중하게 선택하고 요청, 네트워크 등을 고려하십시오. 그러나 준비하십시오. 아마도 2 번 선택해야하고 적어도 한 번은 모든 것을 다시 실행해야 할 것입니다.