Terjadi beberapa hari yang lalu Konferensi Hidra. Orang-orang dari Grup JUG.ru mengundang pembicara impian (Leslie Lamport! Cliff Click! Martin Kleppmann!) dan mengabdikan dua hari untuk sistem terdistribusi dan komputasi. Kontur adalah salah satu dari tiga mitra konferensi. Kami berbicara di stan, berbicara tentang penyimpanan kami yang didistribusikan, bermain bingo, dan memecahkan teka-teki.

Ini adalah postingan dengan analisis tugas di stand Kontur dari penulis teksnya. Siapa yang berada di Hydra - inilah alasan Anda untuk mengingat pengalaman menyenangkan, siapa yang tidak - kesempatan untuk meregangkan otak Anda besar O-notasi.

Bahkan ada peserta yang membongkar flipchart menjadi slide untuk menuliskan keputusannya. Saya tidak bercanda - mereka menyerahkan setumpuk kertas ini untuk verifikasi:

Ada tiga tugas secara total:

• tentang memilih replika berdasarkan bobot untuk penyeimbangan muatan
• tentang menyortir hasil kueri terhadap basis data dalam memori
• pada transfer negara dalam sistem terdistribusi dengan topologi ring

Tugas 1. ClusterClient

Itu perlu untuk mengusulkan sebuah algoritma untuk pemilihan K yang efisien dari replika berbobot N dari sistem terdistribusi:

Tim Anda ditugaskan untuk mengembangkan pustaka klien untuk sekelompok N node yang terdistribusi secara masif. Pustaka akan melacak berbagai metadata yang terkait dengan node (misalnya, latensinya, tingkat respons 4xx/5xx, dll.) dan menetapkan bobot floating point W1..WN untuk node tersebut. Untuk mendukung strategi eksekusi bersamaan, perpustakaan harus dapat memilih K dari N node secara acak—kemungkinan terpilih harus sebanding dengan bobot node.

Usulkan sebuah algoritma untuk memilih node secara efisien. Perkirakan kompleksitas komputasinya menggunakan notasi O besar.

Mengapa semuanya dalam bahasa Inggris?

Karena dalam bentuk ini peserta konferensi bertarung dengan mereka dan karena bahasa Inggris adalah bahasa resmi Hydra. Tugasnya terlihat seperti ini:

Ambil kertas dan pensil, pikir, jangan buru-buru buka spoiler 🙂

Analisis solusi (video)

Mulai 5:53, hanya 4 menit:

Dan inilah cara orang-orang dengan flipchart mengajukan solusi mereka:

Analisis solusi (teks)

Solusi berikut ada di permukaan: jumlahkan bobot semua replika, buat angka acak dari 0 hingga jumlah semua bobot, lalu pilih replika-i sehingga jumlah bobot replika dari 0 hingga (i-1)th kurang dari angka acak, dan jumlah bobot replika dari 0 hingga ke-i - lebih dari itu. Jadi dimungkinkan untuk memilih satu replika, dan untuk memilih replika berikutnya, Anda perlu mengulangi seluruh prosedur tanpa mempertimbangkan replika yang dipilih. Dengan algoritma seperti itu, kompleksitas memilih satu replika adalah O(N), kompleksitas memilih K replika adalah O(N K) ~ O(N2).

Kompleksitas kuadrat itu buruk, tetapi bisa diperbaiki. Untuk melakukan ini, kami akan membangun pohon segmen untuk jumlah bobot. Pohon dengan kedalaman lg N akan diperoleh, di daunnya akan ada bobot replika, dan di simpul yang tersisa - jumlah parsial, hingga jumlah semua bobot di akar pohon. Selanjutnya, kami membuat angka acak dari 0 hingga jumlah semua bobot, temukan replika ke-i, hapus dari pohon, dan ulangi prosedur untuk menemukan replika yang tersisa. Dengan algoritma ini, kompleksitas membangun pohon adalah O(N), kompleksitas menemukan replika ke-i dan menghapusnya dari pohon adalah O(lg N), kompleksitas memilih K replika adalah O(N + K lg N) ~ O(N lg N) .

Kompleksitas linear-log lebih bagus daripada kompleksitas kuadrat, terutama untuk K besar.

Ini adalah algoritma ini diimplementasikan dalam kode Pustaka ClusterClient dari proyek "Timur". (Di sana, pohon dibangun di O(N lg N), tetapi ini tidak memengaruhi kompleksitas akhir algoritme.)

Tugas 2. Zebra

Itu perlu untuk mengusulkan suatu algoritma untuk penyortiran dokumen yang efisien dalam memori oleh bidang non-indeks yang sewenang-wenang:

Tim Anda ditugaskan untuk mengembangkan database dokumen dalam memori yang di-shard. Beban kerja yang umum adalah memilih dokumen N teratas yang diurutkan berdasarkan bidang numerik arbitrer (tidak diindeks) dari kumpulan ukuran M (biasanya N <100 << M). Beban kerja yang sedikit kurang umum adalah memilih N teratas setelah melewatkan dokumen S teratas (S ~ N).

Usulkan algoritme untuk menjalankan kueri tersebut secara efisien. Perkirakan kompleksitas komputasinya menggunakan notasi O besar dalam kasus rata-rata dan skenario kasus terburuk.

Analisis solusi (video)

Mulai pukul 34:50, hanya 6 menit:

Analisis solusi (teks)

Solusi permukaan: urutkan semua dokumen (misalnya dengan sortir cepat), lalu ambil dokumen N+S. Dalam hal ini, kompleksitas penyortiran rata-rata O(M lg M), paling buruk O(M2).

Jelas bahwa menyortir semua dokumen M dan kemudian hanya mengambil sebagian kecil saja tidak efisien. Agar tidak mengurutkan semua dokumen, algoritme cocok pilih cepat, yang akan memilih N + S dari dokumen yang diinginkan (dapat diurutkan berdasarkan algoritme apa pun). Dalam hal ini, kompleksitas akan berkurang menjadi rata-rata O(M), sedangkan kasus terburuk akan tetap sama.

Namun, Anda dapat melakukannya dengan lebih efisien - gunakan algoritme streaming tumpukan biner. Dalam hal ini, dokumen N+S pertama ditambahkan ke min- atau max-heap (bergantung pada arah pengurutan), dan kemudian setiap dokumen berikutnya dibandingkan dengan akar pohon, yang berisi dokumen minimum atau maksimum saat ini, dan ditambahkan ke pohon jika perlu. . Dalam hal ini, kompleksitas dalam kasus terburuk, ketika Anda harus membangun kembali pohon secara konstan, adalah O(M lg M), kompleksitas rata-rata adalah O(M), seperti pemilihan cepat.

Namun, streaming heap ternyata lebih efisien karena dalam praktiknya sebagian besar dokumen dapat dibuang tanpa membangun kembali heap setelah satu perbandingan dengan elemen root-nya. Penyortiran tersebut diimplementasikan dalam basis data dokumen dalam memori Zebra yang dikembangkan dan digunakan di Kontur.

Tugas 3. Pertukaran status

Itu perlu untuk mengusulkan algoritma yang paling efisien untuk mengubah status:

Tim Anda ditugaskan untuk mengembangkan mekanisme pertukaran negara yang mewah untuk sekelompok N node yang terdistribusi. Status node ke-i harus ditransfer ke node ke-(i+1), status node ke-N harus ditransfer ke node pertama. Satu-satunya operasi yang didukung adalah pertukaran status ketika dua node menukar statusnya secara atomik. Diketahui bahwa pertukaran status membutuhkan M milidetik. Setiap node dapat berpartisipasi dalam satu state swap pada saat tertentu.

Berapa lama waktu yang dibutuhkan untuk mentransfer status semua node dalam sebuah cluster?

Analisis solusi (teks)

Solusi permukaan: tukar status elemen pertama dan kedua, lalu elemen pertama dan ketiga, lalu elemen pertama dan keempat, dan seterusnya. Setelah setiap pertukaran, keadaan satu elemen akan berada pada posisi yang diinginkan. Anda harus membuat permutasi O(N) dan menghabiskan waktu O(N M).

Waktu linier panjang, jadi Anda dapat menukar keadaan elemen secara berpasangan: yang pertama dengan yang kedua, yang ketiga dengan yang keempat, dan seterusnya. Setelah setiap pertukaran negara, setiap elemen kedua akan berada di posisi yang tepat. Anda harus membuat permutasi O(lg N) dan menghabiskan waktu O(M lg N).

Namun, adalah mungkin untuk membuat perpindahan menjadi lebih efisien - tidak secara linier, tetapi dalam waktu yang konstan. Untuk melakukan ini, pada langkah pertama, Anda perlu menukar status elemen pertama dengan yang terakhir, yang kedua dengan yang kedua dari belakang, dan seterusnya. Keadaan elemen terakhir akan berada pada posisi yang benar. Dan sekarang kita perlu menukar keadaan elemen kedua dengan yang terakhir, yang ketiga dengan yang kedua dari belakang, dan seterusnya. Setelah putaran pertukaran ini, status semua elemen akan berada di posisi yang tepat. Akan ada O(2M) ~ O(1) permutasi secara total.

Solusi seperti itu sama sekali tidak akan mengejutkan seorang matematikawan yang masih ingat bahwa rotasi adalah komposisi dari dua simetri aksial. Omong-omong, ini digeneralisasikan secara sepele untuk pergeseran bukan oleh satu, tetapi oleh posisi K < N. (Tulis di komentar bagaimana tepatnya.)

Apakah Anda suka teka-teki? Apakah Anda tahu solusi lain? Bagikan di komentar.

Dan inilah beberapa tautan yang bermanfaat pada akhirnya:

• belajar lebih tentang pembangunan infrastruktur dalam kontur
• lihat catatan internal selebaran dengan laporan tentang sistem terdistribusi
• saksikan rangkaian video ceramahnyaAlgoritme yang tidak biasa untuk orang biasa»
• berlangganan kami saluran di Telegram

Sumber: www.habr.com