Xảy ra vài ngày trước . Những người từ Tập đoàn JUG.ru đã mời những diễn giả trong mơ (Leslie Lamport! Cliff Click! Martin Kleppmann!) Và dành hai ngày cho các hệ thống phân tán và điện toán. Kontur là một trong ba đối tác của hội nghị. Chúng tôi đã nói chuyện tại gian hàng, nói về kho lưu trữ phân tán của chúng tôi, chơi lô tô và giải câu đố.
Đây là một bài viết với sự phân tích các nhiệm vụ tại Kontur đứng từ tác giả của văn bản của họ. Ai đã ở trên Hydra - đây là lý do để bạn nhớ lại trải nghiệm thú vị, ai không - một cơ hội để bạn căng não O lớn-ký hiệu.
Thậm chí có những người tham gia đã tháo rời bảng lật thành các slide để viết ra quyết định của họ. Tôi không nói đùa đâu - họ đã đưa xấp giấy này để xác minh:
Tổng cộng có ba nhiệm vụ:
- về việc chọn bản sao theo trọng lượng để cân bằng tải
- về sắp xếp kết quả truy vấn dựa trên cơ sở dữ liệu trong bộ nhớ
- về chuyển giao trạng thái trong một hệ thống phân tán với cấu trúc liên kết vòng
Nhiệm vụ 1. ClusterClient
Cần phải đề xuất một thuật toán để lựa chọn hiệu quả K từ N bản sao có trọng số của một hệ thống phân tán:
Nhóm của bạn được giao nhiệm vụ phát triển một thư viện máy khách cho một cụm gồm N nút được phân phối rộng rãi. Thư viện sẽ theo dõi các siêu dữ liệu khác nhau được liên kết với các nút (ví dụ: độ trễ của chúng, tốc độ phản hồi 4xx/5xx, v.v.) và gán trọng số dấu phẩy động W1..WN cho chúng. Để hỗ trợ chiến lược thực thi đồng thời, thư viện có thể chọn ngẫu nhiên K trong số N nút—cơ hội được chọn phải tỷ lệ thuận với trọng số của nút.
Đề xuất thuật toán chọn nút hiệu quả. Ước tính độ phức tạp tính toán của nó bằng ký hiệu O lớn.
Tại sao mọi thứ đều bằng tiếng Anh?
Bởi vì trong hình thức này, những người tham gia hội nghị đã chiến đấu với họ và vì tiếng Anh là ngôn ngữ chính thức của Hydra. Các nhiệm vụ trông như thế này:
Lấy giấy và bút chì, suy nghĩ, đừng vội mở spoilers ngay 🙂
Phân tích giải pháp (video)
Bắt đầu lúc 5:53, chỉ 4 phút:
Và đây là cách những người dùng bảng lật đưa ra giải pháp của họ:
Phân tích giải pháp (văn bản)
Giải pháp sau nằm trên bề mặt: tính tổng trọng số của tất cả các bản sao, tạo một số ngẫu nhiên từ 0 đến tổng của tất cả các trọng số, sau đó chọn một bản sao thứ i sao cho tổng trọng số của các bản sao từ 0 đến (i-1)th nhỏ hơn một số ngẫu nhiên và tổng trọng số bản sao từ 0 đến thứ i - nhiều hơn nó. Vì vậy, có thể chọn một bản sao và để chọn bản sao tiếp theo, bạn cần lặp lại toàn bộ quy trình mà không xem xét bản sao đã chọn. Với thuật toán như vậy, độ phức tạp khi chọn 2 bản sao là O(N), độ phức tạp khi chọn K bản sao là O(N K) ~ O(NXNUMX).
Độ phức tạp bậc hai là xấu, nhưng nó có thể được cải thiện. Để làm được điều này, chúng ta sẽ xây dựng cho tổng các trọng số. Một cây có độ sâu lg N sẽ thu được, trong các lá của chúng sẽ có trọng số bản sao và trong các nút còn lại - tổng một phần, cho đến tổng của tất cả các trọng số ở gốc của cây. Tiếp theo, chúng tôi tạo một số ngẫu nhiên từ 0 đến tổng của tất cả các trọng số, tìm bản sao thứ i, loại bỏ nó khỏi cây và lặp lại quy trình để tìm các bản sao còn lại. Với thuật toán này, độ phức tạp khi xây dựng cây là O(N), độ phức tạp khi tìm bản sao thứ i và loại bỏ nó khỏi cây là O(lg N), độ phức tạp khi chọn K bản sao là O(N + K lg N) ~ O(N lg N) .
Độ phức tạp log tuyến tính đẹp hơn độ phức tạp bậc hai, đặc biệt đối với K lớn.
Đây là thuật toán Các thư viện ClusterClient từ dự án "“. (Ở đó, cây được xây dựng trong O(N lg N), nhưng điều này không ảnh hưởng đến độ phức tạp cuối cùng của thuật toán.)
Nhiệm vụ 2. Ngựa vằn
Cần phải đề xuất một thuật toán để sắp xếp hiệu quả các tài liệu trong bộ nhớ theo một trường không được lập chỉ mục tùy ý:
Nhóm của bạn được giao nhiệm vụ phát triển cơ sở dữ liệu tài liệu trong bộ nhớ được phân mảnh. Khối lượng công việc phổ biến sẽ là chọn N tài liệu hàng đầu được sắp xếp theo trường số tùy ý (không được lập chỉ mục) từ tập hợp có kích thước M (thường là N < 100 << M). Khối lượng công việc ít phổ biến hơn một chút sẽ là chọn N hàng đầu sau khi bỏ qua các tài liệu S hàng đầu (S ~ N).
Đề xuất một thuật toán để thực hiện các truy vấn như vậy một cách hiệu quả. Ước tính độ phức tạp tính toán của nó bằng ký hiệu O lớn trong trường hợp trung bình và trường hợp xấu nhất.
Phân tích giải pháp (video)
Bắt đầu lúc 34:50, chỉ 6 phút:
Phân tích giải pháp (văn bản)
Giải pháp bề mặt: sắp xếp tất cả các tài liệu (ví dụ với ), sau đó lấy tài liệu N+S. Trong trường hợp này, độ phức tạp của việc sắp xếp trung bình là O(M lg M), tệ nhất là O(M2).
Rõ ràng là việc sắp xếp tất cả M tài liệu và sau đó chỉ lấy một phần nhỏ trong số chúng là không hiệu quả. Để không sắp xếp tất cả các tài liệu, một thuật toán phù hợp , sẽ chọn N + S các tài liệu mong muốn (chúng có thể được sắp xếp theo bất kỳ thuật toán nào). Trong trường hợp này, độ phức tạp trung bình sẽ giảm xuống O(M), trong khi trường hợp xấu nhất sẽ giữ nguyên.
Tuy nhiên, bạn có thể làm điều đó hiệu quả hơn nữa - sử dụng thuật toán . Trong trường hợp này, các tài liệu N+S đầu tiên được thêm vào vùng tối thiểu hoặc tối đa (tùy thuộc vào hướng sắp xếp), sau đó mỗi tài liệu tiếp theo được so sánh với gốc của cây chứa tài liệu tối thiểu hoặc tối đa hiện tại, và được thêm vào cây nếu cần thiết. . Trong trường hợp này, độ phức tạp trong trường hợp xấu nhất, khi bạn phải liên tục xây dựng lại cây, là O(M lg M), độ phức tạp trung bình là O(M), như với quickselect.
Tuy nhiên, truyền trực tuyến heap hóa ra hiệu quả hơn do thực tế là trong thực tế, hầu hết các tài liệu có thể bị loại bỏ mà không cần xây dựng lại heap sau một lần so sánh với phần tử gốc của nó. Việc sắp xếp như vậy được triển khai trong cơ sở dữ liệu tài liệu trong bộ nhớ Zebra được phát triển và sử dụng ở Kontur.
Nhiệm vụ 3. Hoán đổi trạng thái
Cần phải đề xuất thuật toán hiệu quả nhất để chuyển trạng thái:
Nhóm của bạn được giao nhiệm vụ phát triển một cơ chế trao đổi trạng thái ưa thích cho một cụm N nút phân tán. Trạng thái của nút thứ i sẽ được chuyển sang nút thứ (i+1), trạng thái của nút thứ N sẽ được chuyển sang nút đầu tiên. Hoạt động duy nhất được hỗ trợ là hoán đổi trạng thái khi hai nút trao đổi trạng thái nguyên tử. Được biết, một lần hoán đổi trạng thái mất M mili giây. Mọi nút đều có thể tham gia vào một lần hoán đổi trạng thái tại bất kỳ thời điểm nào.
Mất bao lâu để chuyển trạng thái của tất cả các nút trong một cụm?
Phân tích giải pháp (văn bản)
Giải pháp bề mặt: hoán đổi trạng thái của phần tử thứ nhất và phần tử thứ hai, sau đó là phần tử thứ nhất và phần tử thứ ba, sau đó là phần tử thứ nhất và phần tử thứ tư, v.v. Sau mỗi lần trao đổi, trạng thái của một phần tử sẽ ở vị trí mong muốn. Bạn phải thực hiện hoán vị O(N) và dành thời gian O(N M).
Thời gian tuyến tính dài, vì vậy bạn có thể trao đổi trạng thái của các phần tử theo cặp: phần tử thứ nhất với phần tử thứ hai, phần tử thứ ba với phần tử thứ tư, v.v. Sau mỗi lần trao đổi trạng thái, mọi phần tử thứ hai sẽ ở đúng vị trí. Bạn phải thực hiện hoán vị O(lg N) và dành thời gian O(M lg N).
Tuy nhiên, có thể làm cho sự thay đổi hiệu quả hơn nữa - không phải theo tuyến tính mà theo thời gian cố định. Để làm điều này, ở bước đầu tiên, bạn cần hoán đổi trạng thái của phần tử đầu tiên với phần tử cuối cùng, phần tử thứ hai với phần tử áp chót, v.v. Trạng thái của phần tử cuối cùng sẽ ở đúng vị trí. Và bây giờ chúng ta cần hoán đổi trạng thái của phần tử thứ hai với phần tử cuối cùng, phần tử thứ ba với phần tử áp chót, v.v. Sau vòng hoán đổi này, trạng thái của mọi nguyên tố sẽ về đúng vị trí. Tổng cộng sẽ có các hoán vị O(2M) ~ O(1).
Một giải pháp như vậy sẽ không gây ngạc nhiên cho một nhà toán học vẫn còn nhớ rằng một phép quay là một thành phần của hai phép đối xứng trục. Nhân tiện, nó được tổng quát hóa một cách tầm thường cho một sự thay đổi không phải bởi một, mà bởi K < N vị trí. (Viết chính xác như thế nào trong phần bình luận.)
Bạn có thích câu đố? Bạn có biết các giải pháp khác? Chia sẻ trong các ý kiến.
Và đây là một số liên kết hữu ích cuối cùng:
- học nhiều hơn về trong đường viền
- xem hồ sơ nội bộ về hệ thống phân tán
- xem loạt video bài giảng»
- đăng ký của chúng tôi
Nguồn: www.habr.com