បានកើតឡើងពីរបីថ្ងៃមុន។ សន្និសីទ Hydra. បុរសមកពី JUG.ru Group បានអញ្ជើញវាគ្មិនក្នុងសុបិន (Leslie Lamport! Cliff Click! Martin Kleppmann!) ហើយបានចំណាយពេលពីរថ្ងៃដើម្បីប្រព័ន្ធចែកចាយ និងកុំព្យូទ័រ។ Kontur គឺជាដៃគូមួយក្នុងចំណោមដៃគូទាំងបីនៃសន្និសីទនេះ។ យើងបាននិយាយនៅស្តង់ និយាយអំពីកន្លែងផ្ទុកចែកចាយរបស់យើង លេងប៊ីងហ្គោ និងដោះស្រាយល្បែងផ្គុំរូប។

នេះ​គឺ​ជា​ការ​ប្រកាស​ជាមួយ​នឹង​ការ​វិភាគ​នៃ​ភារកិច្ច​នៅ Kontur ឈរ​ពី​អ្នក​និពន្ធ​នៃ​អត្ថបទ​របស់​ពួក​គេ​។ តើអ្នកណានៅលើ Hydra - នេះគឺជាហេតុផលរបស់អ្នកក្នុងការចងចាំបទពិសោធន៍រីករាយដែលមិនមែនជា - ឱកាសដើម្បីពង្រីកខួរក្បាលរបស់អ្នក។ ធំអូ- ចំណាំ។

មាន​សូម្បី​តែ​អ្នក​ចូលរួម​ដែល​បាន​រុះរើ​តារាង​ត្រឡប់​ជា​ស្លាយ​ដើម្បី​សរសេរ​ការ​សម្រេច​ចិត្ត​របស់​ពួកគេ។ ខ្ញុំមិននិយាយលេងទេ ពួកគេបានប្រគល់ក្រដាសមួយដុំនេះសម្រាប់ផ្ទៀងផ្ទាត់៖

សរុបមានកិច្ចការចំនួនបី៖

• អំពីការជ្រើសរើសការចម្លងតាមទម្ងន់សម្រាប់តុល្យភាពបន្ទុក
• អំពីការតម្រៀបលទ្ធផលសំណួរប្រឆាំងនឹងមូលដ្ឋានទិន្នន័យក្នុងអង្គចងចាំ
• នៅលើការផ្ទេររដ្ឋនៅក្នុងប្រព័ន្ធចែកចាយជាមួយ topology ចិញ្ចៀនមួយ។

កិច្ចការ 1. ClusterClient

វាចាំបាច់ក្នុងការស្នើក្បួនដោះស្រាយសម្រាប់ការជ្រើសរើសប្រកបដោយប្រសិទ្ធភាពនៃ K ពី N ទម្ងន់ចម្លងនៃប្រព័ន្ធចែកចាយ៖

ក្រុមរបស់អ្នកមានភារកិច្ចបង្កើតបណ្ណាល័យអតិថិជនសម្រាប់ចង្កោម N ដែលត្រូវបានចែកចាយយ៉ាងច្រើន។ បណ្ណាល័យនឹងតាមដានទិន្នន័យមេតាជាច្រើនដែលទាក់ទងនឹងថ្នាំង (ឧ. ភាពយឺតយ៉ាវរបស់ពួកគេ អត្រាឆ្លើយតប 4xx/5xx ។ ដើម្បីគាំទ្រយុទ្ធសាស្ត្រប្រតិបត្តិស្របគ្នា បណ្ណាល័យគួរតែអាចជ្រើសរើស K នៃ N nodes ដោយចៃដន្យ—ឱកាសនៃការជ្រើសរើសគួរតែសមាមាត្រទៅនឹងទម្ងន់របស់ថ្នាំងមួយ។

ស្នើក្បួនដោះស្រាយដើម្បីជ្រើសរើសថ្នាំងប្រកបដោយប្រសិទ្ធភាព។ ប៉ាន់ស្មានភាពស្មុគស្មាញនៃការគណនារបស់វាដោយប្រើសញ្ញា O ធំ។

ហេតុអ្វីបានជាអ្វីៗទាំងអស់ជាភាសាអង់គ្លេស?

ដោយសារតែនៅក្នុងទម្រង់នេះ អ្នកចូលរួមសន្និសីទបានប្រយុទ្ធជាមួយពួកគេ ហើយដោយសារតែភាសាអង់គ្លេសគឺជាភាសាផ្លូវការរបស់ Hydra ។ ភារកិច្ចមើលទៅដូចនេះ៖

យកក្រដាស និងខ្មៅដៃមកគិត កុំប្រញាប់បើក spoiler ភ្លាមៗ🙂

ការវិភាគដំណោះស្រាយ (វីដេអូ)

ចាប់ផ្តើមនៅម៉ោង 5:53 ត្រឹមតែ 4 នាទីប៉ុណ្ណោះ៖

ហើយ​នេះ​ជា​របៀប​ដែល​បុរស​ដែល​មាន​តារាង​បំប្លែង​បាន​ដាក់​ដំណោះស្រាយ​របស់​ពួកគេ៖

ការវិភាគនៃដំណោះស្រាយ (អត្ថបទ)

ដំណោះស្រាយខាងក្រោមស្ថិតនៅលើផ្ទៃ៖ បូកទម្ងន់នៃការចម្លងទាំងអស់ បង្កើតលេខចៃដន្យពី 0 ទៅផលបូកនៃទម្ងន់ទាំងអស់ បន្ទាប់មកជ្រើសរើស i-replica ដែលផលបូកនៃទម្ងន់ចម្លងពី 0 ទៅ (i-1)th គឺតិចជាងចំនួនចៃដន្យ ហើយផលបូកនៃទម្ងន់ចម្លងពី 0 ដល់ i-th - ច្រើនជាងវា។ ដូច្នេះវានឹងអាចជ្រើសរើសការចម្លងមួយបាន ហើយដើម្បីជ្រើសរើសមួយបន្ទាប់ អ្នកត្រូវធ្វើបែបបទទាំងមូលឡើងវិញដោយមិនគិតពីការចម្លងដែលបានជ្រើសរើស។ ជាមួយនឹងក្បួនដោះស្រាយបែបនេះ ភាពស្មុគស្មាញនៃការជ្រើសរើសការចម្លងមួយគឺ O(N) ភាពស្មុគស្មាញនៃការជ្រើសរើស K ចម្លងគឺ O(N K) ~ O(N2) ។

ភាពស្មុគស្មាញបួនជ្រុងគឺមិនល្អទេ ប៉ុន្តែវាអាចត្រូវបានកែលម្អ។ ដើម្បីធ្វើដូចនេះយើងនឹងសាងសង់ មែកធាងផ្នែក សម្រាប់ផលបូកនៃទម្ងន់។ មែកធាងនៃជម្រៅ lg N នឹងត្រូវបានទទួលនៅក្នុងស្លឹកដែលនឹងមានទម្ងន់ចម្លងហើយនៅក្នុងថ្នាំងដែលនៅសល់ - ផលបូកមួយផ្នែករហូតដល់ផលបូកនៃទំងន់ទាំងអស់នៅឫសនៃដើមឈើ។ បន្ទាប់មក យើងបង្កើតលេខចៃដន្យពី 0 ដល់ផលបូកនៃទម្ងន់ទាំងអស់ ស្វែងរកការចម្លង i-th យកវាចេញពីមែកធាង ហើយធ្វើបែបបទម្តងទៀតដើម្បីស្វែងរកការចម្លងដែលនៅសល់។ ជាមួយនឹងក្បួនដោះស្រាយនេះ ភាពស្មុគស្មាញនៃការសាងសង់មែកធាងគឺ O(N) ភាពស្មុគស្មាញនៃការស្វែងរកការចម្លង i-th និងការយកវាចេញពីដើមឈើគឺ O(lg N) ភាពស្មុគស្មាញនៃការជ្រើសរើស K ចម្លងគឺ O(N + K lg N) ~ O(N lg N) ។

ភាពស្មុគស្មាញនៃកំណត់ហេតុលីនេអ៊ែរគឺល្អជាងភាពស្មុគស្មាញបួនជ្រុង ជាពិសេសសម្រាប់ K ធំ។

វាគឺជាក្បួនដោះស្រាយនេះ។ បានអនុវត្តនៅក្នុងកូដ បណ្ណាល័យ ClusterClient ពីគម្រោង "ខាងកើត"។ (នៅទីនោះ ដើមឈើត្រូវបានសាងសង់ក្នុង O(N lg N) ប៉ុន្តែវាមិនប៉ះពាល់ដល់ភាពស្មុគស្មាញចុងក្រោយនៃក្បួនដោះស្រាយនោះទេ។)

កិច្ចការទី 2. សេះបង្កង់

វាចាំបាច់ក្នុងការស្នើរក្បួនដោះស្រាយសម្រាប់ការតម្រៀបឯកសារក្នុងអង្គចងចាំប្រកបដោយប្រសិទ្ធភាពដោយវាលដែលមិនមានលិបិក្រមបំពាន៖

ក្រុមរបស់អ្នកមានភារកិច្ចបង្កើតមូលដ្ឋានទិន្នន័យឯកសារដែលបំបែកនៅក្នុងអង្គចងចាំ។ បន្ទុកការងារទូទៅគឺដើម្បីជ្រើសរើសឯកសារ N កំពូលដែលតម្រៀបតាមវាលលេខដែលបំពាន (មិនធ្វើលិបិក្រម) ពីបណ្តុំនៃទំហំ M (ជាធម្មតា N < 100 << M) ។ បន្ទុកការងារធម្មតាតិចជាងបន្តិចគឺជ្រើសរើសកំពូល N បន្ទាប់ពីរំលងឯកសារ S កំពូល (S ~ N) ។

ស្នើក្បួនដោះស្រាយដើម្បីប្រតិបត្តិសំណួរបែបនេះប្រកបដោយប្រសិទ្ធភាព។ ប៉ាន់ស្មានភាពស្មុគស្មាញនៃការគណនារបស់វាដោយប្រើសញ្ញា O ធំនៅក្នុងករណីមធ្យម និងសេណារីយ៉ូករណីអាក្រក់បំផុត។

ការវិភាគដំណោះស្រាយ (វីដេអូ)

ចាប់ផ្តើមនៅម៉ោង 34:50 ត្រឹមតែ 6 នាទី:

ការវិភាគនៃដំណោះស្រាយ (អត្ថបទ)

ដំណោះស្រាយលើផ្ទៃ៖ តម្រៀបឯកសារទាំងអស់ (ឧទាហរណ៍ជាមួយ រហ័ស) បន្ទាប់មកយកឯកសារ N+S ។ ក្នុងករណីនេះភាពស្មុគស្មាញនៃការតម្រៀបគឺជាមធ្យម O (M lg M) អាក្រក់បំផុត O (M2) ។

វាច្បាស់ណាស់ថាការតម្រៀបឯកសារ M ទាំងអស់ហើយបន្ទាប់មកយកតែផ្នែកតូចមួយនៃពួកវាគឺមិនមានប្រសិទ្ធភាពទេ។ ដើម្បីមិនតម្រៀបឯកសារទាំងអស់ ក្បួនដោះស្រាយគឺសមរម្យ ជ្រើសរើសរហ័សដែលនឹងជ្រើសរើស N + S នៃឯកសារដែលចង់បាន (ពួកវាអាចត្រូវបានតម្រៀបតាមក្បួនដោះស្រាយណាមួយ) ។ ក្នុងករណីនេះ ភាពស្មុគស្មាញនឹងថយចុះមកត្រឹម O(M) ជាមធ្យម ខណៈពេលដែលករណីអាក្រក់បំផុតនឹងនៅដដែល។

ទោះជាយ៉ាងណាក៏ដោយអ្នកអាចធ្វើវាកាន់តែមានប្រសិទ្ធភាព - ប្រើក្បួនដោះស្រាយ ការស្ទ្រីម binary heap. ក្នុងករណីនេះ ឯកសារ N+S ដំបូងត្រូវបានបន្ថែមទៅ min- ឬ max-heap (អាស្រ័យលើទិសដៅតម្រៀប) ហើយបន្ទាប់មកឯកសារបន្ទាប់នីមួយៗត្រូវបានប្រៀបធៀបទៅនឹងឫសនៃមែកធាង ដែលមានឯកសារអប្បបរមា ឬអតិបរមាបច្ចុប្បន្ន។ ហើយត្រូវបានបន្ថែមទៅដើមឈើបើចាំបាច់។ ក្នុងករណីនេះភាពស្មុគស្មាញនៅក្នុងករណីដ៏អាក្រក់បំផុត នៅពេលដែលអ្នកត្រូវសាងសង់ដើមឈើឡើងវិញជានិច្ចគឺ O(M lg M) ភាពស្មុគស្មាញជាមធ្យមគឺ O(M) ដូចនឹងការជ្រើសរើសរហ័សដែរ។

ទោះជាយ៉ាងណាក៏ដោយ ការស្ទ្រីម heap ប្រែជាមានប្រសិទ្ធភាពជាងមុន ដោយសារតែការពិតដែលថានៅក្នុងការអនុវត្តជាក់ស្តែង ឯកសារភាគច្រើនអាចត្រូវបានលុបចោលដោយមិនចាំបាច់សាងសង់ឡើងវិញនូវ heap បន្ទាប់ពីការប្រៀបធៀបតែមួយជាមួយធាតុ root របស់វា។ ការ​តម្រៀប​បែប​នេះ​ត្រូវ​បាន​អនុវត្ត​នៅ​ក្នុង​មូលដ្ឋាន​ទិន្នន័យ​ឯកសារ​ក្នុង​អង្គ​ចងចាំ Zebra ដែល​បាន​បង្កើត និង​ប្រើ​នៅ​ក្នុង Kontur ។

កិច្ចការទី 3. ការផ្លាស់ប្តូររដ្ឋ

វាចាំបាច់ក្នុងការស្នើក្បួនដោះស្រាយដ៏មានប្រសិទ្ធភាពបំផុតសម្រាប់ការផ្លាស់ប្តូររដ្ឋ៖

ក្រុមរបស់អ្នកមានភារកិច្ចបង្កើតយន្តការផ្លាស់ប្តូររដ្ឋដ៏ប្រណិតមួយសម្រាប់ចង្កោម N ដែលចែកចាយ។ ស្ថានភាពរបស់ថ្នាំង i-th គួរតែត្រូវបានផ្ទេរទៅថ្នាំង (i+1)-th ស្ថានភាពរបស់ថ្នាំង N គួរតែត្រូវបានផ្ទេរទៅថ្នាំងទីមួយ។ ប្រតិបត្តិការ​ដែល​បាន​គាំទ្រ​តែ​មួយ​គត់​គឺ​ការ​ស្វប​រដ្ឋ​នៅ​ពេល​ថ្នាំង​ពីរ​ប្តូរ​រដ្ឋ​របស់​វា​ជា​អាតូម។ វាត្រូវបានគេដឹងថាការផ្លាស់ប្តូររដ្ឋចំណាយពេល M មិល្លីវិនាទី។ ថ្នាំងនីមួយៗអាចចូលរួមក្នុងការស្វបរដ្ឋតែមួយនៅគ្រប់ពេលវេលា។

តើ​ត្រូវ​ចំណាយ​ពេល​ប៉ុន្មាន​ដើម្បី​ផ្ទេរ​រដ្ឋ​នៃ​ថ្នាំង​ទាំងអស់​ក្នុង​ចង្កោម​មួយ?

ការវិភាគនៃដំណោះស្រាយ (អត្ថបទ)

ដំណោះស្រាយលើផ្ទៃ៖ ផ្លាស់ប្តូរស្ថានភាពនៃធាតុទីមួយ និងទីពីរ បន្ទាប់មក ទីមួយ និងទីបី បន្ទាប់មក ទីមួយ និងទី បួន ហើយដូច្នេះនៅលើ។ បន្ទាប់ពីការផ្លាស់ប្តូរនីមួយៗស្ថានភាពនៃធាតុមួយនឹងស្ថិតនៅក្នុងទីតាំងដែលចង់បាន។ អ្នកត្រូវតែធ្វើការផ្លាស់ប្តូរ O(N) ហើយចំណាយពេល O(N M) ។

ពេលវេលាលីនេអ៊ែរគឺវែង ដូច្នេះអ្នកអាចផ្លាស់ប្តូរស្ថានភាពនៃធាតុជាគូ៖ ទីមួយជាមួយទីពីរ ទីបីជាមួយទីបួន ហើយដូច្នេះនៅលើ។ បន្ទាប់ពីការផ្លាស់ប្តូររដ្ឋនីមួយៗ រាល់ធាតុទីពីរនឹងស្ថិតនៅក្នុងទីតាំងត្រឹមត្រូវ។ អ្នកត្រូវតែធ្វើការផ្លាស់ប្តូរ O(lg N) ហើយចំណាយពេល O(M lg N)។

ទោះយ៉ាងណាក៏ដោយ វាអាចធ្វើទៅបានដើម្បីធ្វើឱ្យការផ្លាស់ប្តូរកាន់តែមានប្រសិទ្ធភាព - មិនមែននៅក្នុងលីនេអ៊ែរទេប៉ុន្តែនៅក្នុងពេលវេលាថេរ។ ដើម្បីធ្វើដូចនេះនៅជំហានដំបូងអ្នកត្រូវផ្លាស់ប្តូរស្ថានភាពនៃធាតុទីមួយជាមួយនឹងធាតុចុងក្រោយទីពីរជាមួយ penultimate ហើយដូច្នេះនៅលើ។ ស្ថានភាពនៃធាតុចុងក្រោយនឹងស្ថិតនៅក្នុងទីតាំងត្រឹមត្រូវ។ ហើយឥឡូវនេះយើងត្រូវផ្លាស់ប្តូរស្ថានភាពនៃធាតុទីពីរជាមួយនឹងធាតុចុងក្រោយទីបីជាមួយ penultimate ហើយដូច្នេះនៅលើ។ បន្ទាប់ពីការផ្លាស់ប្តូរជុំនេះ រដ្ឋនៃធាតុទាំងអស់នឹងស្ថិតនៅក្នុងទីតាំងត្រឹមត្រូវ។ វានឹងមានការផ្លាស់ប្តូរ O(2M) ~ O(1) សរុប។

ដំណោះស្រាយបែបនេះនឹងមិនភ្ញាក់ផ្អើលទាល់តែសោះ គណិតវិទូដែលនៅតែចាំថា ការបង្វិលគឺជាសមាសធាតុនៃស៊ីមេទ្រីអ័ក្សពីរ។ ដោយវិធីនេះ វាត្រូវបានសង្ខេបជាទូទៅសម្រាប់ការផ្លាស់ប្តូរមិនមែនដោយមួយ ប៉ុន្តែដោយមុខតំណែង K<N ។ (សរសេរក្នុង comment ថាយ៉ាងម៉េចដែរ)

តើអ្នកចូលចិត្តល្បែងផ្គុំរូបទេ? តើអ្នកដឹងពីដំណោះស្រាយផ្សេងទៀតទេ? ចែករំលែកនៅក្នុងមតិយោបល់។

ហើយនេះគឺជាតំណភ្ជាប់ដែលមានប្រយោជន៍មួយចំនួននៅចុងបញ្ចប់៖

• ស្វែងយល់បន្ថែមអំពី ការអភិវឌ្ឍន៍ហេដ្ឋារចនាសម្ព័ន្ធ នៅក្នុងវណ្ឌវង្ក
• មើលកំណត់ត្រាផ្ទៃក្នុង ខិត្តប័ណ្ណជាមួយរបាយការណ៍ អំពីប្រព័ន្ធចែកចាយ
• មើលស៊េរីនៃការបង្រៀនវីដេអូក្បួនដោះស្រាយមិនធម្មតាសម្រាប់មនុស្សធម្មតា។»
• ជាវប្រចាំរបស់យើង។ ឆានែលក្នុង Telegram

ប្រភព: www.habr.com