며칠 전에 일어난 일 히드라 회의. JUG.ru 그룹의 사람들은 꿈의 연사(Leslie Lamport! Cliff Click! Martin Kleppmann!)를 초대하고 분산 시스템과 컴퓨팅에 이틀을 바쳤습니다. Kontur는 회의의 세 파트너 중 하나였습니다. 우리는 부스에서 이야기를 나누고 분산 저장 장치에 대해 이야기하고 빙고 게임을 하고 퍼즐을 풀었습니다.

이것은 텍스트 작성자가 Kontur 스탠드에서 작업을 분석한 게시물입니다. Hydra에 있었던 사람 - 이것은 즐거운 경험을 기억하는 이유입니다. 그렇지 않은 사람은 뇌를 스트레칭할 기회입니다. 큰 O-표기법.

플립차트를 분해하여 슬라이드로 만들어 자신의 결정을 적는 참가자도 있었습니다. 농담이 아닙니다. 그들은 확인을 위해 이 종이 뭉치를 건네주었습니다.

총 세 가지 작업이 있었습니다.

• 로드 밸런싱을 위해 가중치로 복제본 선택 정보
• 메모리 내 데이터베이스에 대한 쿼리 결과 정렬 정보
• 링 토폴로지가 있는 분산 시스템의 상태 전송 시

작업 1. ClusterClient

분산 시스템의 N개의 가중 복제본에서 K를 효율적으로 선택하기 위한 알고리즘을 제안하는 것이 필요했습니다.

귀하의 팀은 N 노드의 대규모 분산 클러스터를 위한 클라이언트 라이브러리를 개발하는 임무를 맡고 있습니다. 라이브러리는 노드와 관련된 다양한 메타데이터(예: 대기 시간, 4xx/5xx 응답 속도 등)를 추적하고 부동 소수점 가중치 W1..WN을 할당합니다. 동시 실행 전략을 지원하기 위해 라이브러리는 N/N 노드 중 K를 무작위로 선택할 수 있어야 합니다. 선택될 확률은 노드의 가중치에 비례해야 합니다.

노드를 효율적으로 선택하는 알고리즘을 제안합니다. Big O 표기법을 사용하여 계산 복잡도를 추정합니다.

왜 모든 것이 영어로 되어 있습니까?

이 형태로 회의 참가자들이 그들과 싸웠고 영어가 Hydra의 공식 언어 였기 때문입니다. 작업은 다음과 같이 생겼습니다.

종이와 연필을 가지고 생각하고 스포일러를 즉시 열지 마십시오 🙂

솔루션 분석(비디오)

5분 53초부터 단 4분만:

다음은 플립 차트를 가진 사람들이 해결책을 제시한 방법입니다.

솔루션 분석(텍스트)

다음 솔루션은 표면에 있습니다. 모든 복제본의 가중치를 합산하고, 0에서 모든 가중치의 합까지 난수를 생성한 다음, 복제본 가중치의 합이 0에서 (i-1)번째가 되도록 i-레플리카를 선택합니다. 임의의 숫자보다 작고 0에서 i번째까지 복제본 가중치의 합이 그보다 큽니다. 따라서 하나의 복제본을 선택하고 다음 복제본을 선택하려면 선택한 복제본을 고려하지 않고 전체 절차를 반복해야 합니다. 이러한 알고리즘에서 하나의 복제본을 선택하는 복잡도는 O(N)이고 K개 복제본을 선택하는 복잡도는 O(N·K) ~ O(N2)입니다.

XNUMX차 복잡도는 좋지 않지만 개선할 수 있습니다. 이를 위해 우리는 구축할 것입니다. 세그먼트 트리 가중치의 합계. 깊이 lg N의 트리가 얻어지며 리프에는 복제 가중치가 있고 나머지 노드에는 트리 루트의 모든 가중치 합계까지 부분 합계가 있습니다. 다음으로 0부터 모든 가중치의 합까지 임의의 숫자를 생성하고 i번째 복제본을 찾아 트리에서 제거하고 나머지 복제본을 찾는 절차를 반복합니다. 이 알고리즘에서 트리를 구축하는 복잡도는 O(N), i번째 복제본을 찾아 트리에서 제거하는 복잡도는 O(lg N), K개 복제본을 선택하는 복잡도는 O(N + K lg N) ~ O(N lg N) .

특히 큰 K의 경우 선형 로그 복잡도가 XNUMX차 복잡도보다 좋습니다.

바로 이 알고리즘이다 코드로 구현 프로젝트의 ClusterClient 라이브러리 "Восток". (여기서 트리는 O(N lg N)로 구성되지만 알고리즘의 최종 복잡도에는 영향을 미치지 않습니다.)

작업 2. 얼룩말

임의의 색인화되지 않은 필드로 메모리의 문서를 효율적으로 정렬하기 위한 알고리즘을 제안해야 했습니다.

귀하의 팀은 샤딩된 메모리 내 문서 데이터베이스를 개발하는 임무를 맡고 있습니다. 일반적인 워크로드는 크기 M(보통 N < 100 << M)의 컬렉션에서 임의의(인덱싱되지 않은) 숫자 필드로 정렬된 상위 N개의 문서를 선택하는 것입니다. 약간 덜 일반적인 워크로드는 상위 S 문서(S ~ N)를 건너뛴 후 상위 N을 선택하는 것입니다.

이러한 쿼리를 효율적으로 실행하는 알고리즘을 제안하십시오. 평균적인 경우와 최악의 경우 시나리오에서 Big O 표기법을 사용하여 계산 복잡도를 추정합니다.

솔루션 분석(비디오)

34:50부터 단 6분:

솔루션 분석(텍스트)

표면 솔루션: 모든 문서 정렬(예: 퀵 정렬) 그런 다음 N+S 문서를 가져옵니다. 이 경우 정렬의 복잡성은 평균 O(M lg M), 최악의 경우 O(M2)입니다.

모든 M 문서를 정렬한 다음 그 중 일부만 가져오는 것은 비효율적임이 분명합니다. 모든 문서를 정렬하지 않으려면 알고리즘이 적합합니다. 빠른 선택, 원하는 문서의 N + S를 선택합니다(알고리즘으로 정렬할 수 있음). 이 경우 복잡도는 평균적으로 O(M)으로 감소하지만 최악의 경우는 동일하게 유지됩니다.

그러나 훨씬 더 효율적으로 수행할 수 있습니다. 알고리즘을 사용하십시오. 바이너리 힙 스트리밍. 이 경우 첫 번째 N+S 문서는 최소 또는 최대 힙(정렬 방향에 따라 다름)에 추가된 다음 각 후속 문서는 현재 최소 또는 최대 문서를 포함하는 트리의 루트와 비교됩니다. 필요한 경우 트리에 추가됩니다. . 이 경우 트리를 지속적으로 재구성해야 하는 최악의 경우 복잡도는 O(M lg M)이며, quickselect와 마찬가지로 평균 복잡도는 O(M)입니다.

그러나 힙 스트리밍은 실제로 루트 요소와 한 번 비교한 후 힙을 다시 빌드하지 않고 대부분의 문서를 버릴 수 있기 때문에 더 효율적인 것으로 판명되었습니다. 이러한 정렬은 Kontur에서 개발 및 사용되는 Zebra 인메모리 문서 데이터베이스에서 구현됩니다.

과제 3. 상태 교환

상태 이동을 위한 가장 효율적인 알고리즘을 제안하는 것이 필요했습니다.

귀하의 팀은 N 노드의 분산 클러스터를 위한 멋진 상태 교환 메커니즘을 개발하는 임무를 맡고 있습니다. i번째 노드의 상태는 (i+1)번째 노드로, N번째 노드의 상태는 첫번째 노드로 전달되어야 합니다. 유일하게 지원되는 작업은 두 노드가 원자적으로 상태를 교환할 때 상태 교환입니다. 상태 교환에는 M밀리초가 소요되는 것으로 알려져 있습니다. 모든 노드는 주어진 순간에 단일 상태 교환에 참여할 수 있습니다.

클러스터에 있는 모든 노드의 상태를 전송하는 데 얼마나 걸립니까?

솔루션 분석(텍스트)

표면 솔루션: 첫 번째와 두 번째 요소의 상태를 교환한 다음 첫 번째와 세 번째, 첫 번째와 네 번째 등의 상태를 교환합니다. 각각의 교환 후 한 요소의 상태는 원하는 위치에 있게 됩니다. O(N) 순열을 만들고 O(N M) 시간을 소비해야 합니다.

선형 시간은 길기 때문에 첫 번째와 두 번째, 세 번째와 네 번째 등 쌍으로 요소의 상태를 교환할 수 있습니다. 각 상태 교환 후 모든 두 번째 요소가 올바른 위치에 있게 됩니다. O(lg N) 순열을 만들고 O(M lg N) 시간을 보내야 합니다.

그러나 선형이 아니라 일정한 시간에 훨씬 더 효율적으로 변속을 할 수 있습니다. 이렇게하려면 첫 번째 단계에서 첫 번째 요소의 상태를 마지막 요소로, 두 번째 요소를 끝에서 두 번째 요소로 교환해야 합니다. 마지막 요소의 상태는 올바른 위치에 있게 됩니다. 이제 두 번째 요소의 상태를 마지막 요소와 교환하고 세 번째 요소를 두 번째 요소와 교환해야 합니다. 이 교환 라운드 후에 모든 요소의 상태가 올바른 위치에 있게 됩니다. 총 O(2M) ~ O(1) 순열이 있습니다.

그러한 해결책은 회전이 두 개의 축 대칭의 구성이라는 것을 여전히 기억하는 수학자에게는 전혀 놀라운 일이 아닙니다. 그건 그렇고, 그것은 하나가 아니라 K < N 위치로 이동하는 것에 대해 사소하게 일반화됩니다. (정확히 댓글에 적어주세요.)

퍼즐을 좋아했습니까? 다른 솔루션을 알고 계십니까? 의견에 공유하십시오.

마지막으로 몇 가지 유용한 링크가 있습니다.

• 자세히 알아보기 인프라 개발 윤곽선
• 내부 기록 참조 보고서가 있는 전단지 분산 시스템 정보
• 비디오 강의 시리즈 보기평범한 사람들을 위한 특이한 알고리즘»
• 우리의 구독 전보의 채널

출처 : habr.com