Va passar fa uns dies . Els nois del grup JUG.ru van convidar a ponents de somni (Leslie Lamport! Cliff Click! Martin Kleppmann!) i van dedicar dos dies als sistemes distribuïts i la informàtica. Kontur va ser un dels tres socis de la conferència. Vam parlar a l'estand, vam parlar del nostre emmagatzematge distribuït, vam jugar al bingo i vam resoldre problemes.
Aquest és un post amb una anàlisi de les tasques a l'estand de Kontur a partir de l'autor del seu text. Per a aquells que han estat a Hydra, aquesta és la vostra oportunitat de recordar experiències agradables; per a aquells que no ho han fet, aquesta és una oportunitat per estirar el cervell. gran O- notació.
Fins i tot hi va haver participants que van desmuntar el rotafolio en diapositives per escriure la seva solució. No estic de broma: van enviar aquesta pila de papers per a la inspecció:
Hi havia tres tasques en total:
- sobre la selecció de rèpliques per pesos per a l'equilibri de càrrega
- sobre ordenar els resultats d'una consulta a una base de dades en memòria
- sobre la transferència d'estat en un sistema distribuït amb una topologia en anell
Tasca 1. ClusterClient
Va ser necessari proposar un algorisme per seleccionar de manera eficient K entre N rèpliques ponderades d'un sistema distribuït:
El vostre equip té l'encàrrec de desenvolupar una biblioteca de client per a un clúster distribuït massivament de N nodes. La biblioteca faria un seguiment de diverses metadades associades als nodes (p. ex., les seves latències, taxes de resposta 4xx/5xx, etc.) i els assignaria pesos de coma flotant W1..WN. Per tal de donar suport a l'estratègia d'execució simultània, la biblioteca hauria de poder escollir K de N nodes aleatòriament; la possibilitat de ser seleccionada hauria de ser proporcional al pes d'un node.
Proposar un algorisme per seleccionar nodes de manera eficient. Estimar la seva complexitat computacional utilitzant la notació O gran.
Per què està tot en anglès?
Perquè així els van lluitar els participants de la conferència i perquè l'anglès era la llengua oficial d'Hydra. Els problemes tenien aquest aspecte:
Agafa paper i llapis, pensa, no t'afanyes a obrir spoilers de seguida :)
Anàlisi de la solució (vídeo)
Comença a les 5:53, només 4 minuts:
I així és com aquests mateixos nois amb el rotafolio van presentar la seva solució:
Anàlisi de la solució (text)
La solució següent es troba a la superfície: sumeu els pesos de totes les rèpliques, genereu un nombre aleatori de 0 a la suma de tots els pesos i, a continuació, seleccioneu una rèplica i de manera que la suma dels pesos de les rèpliques de 0 a ( i-1)th és menor que el nombre aleatori i la suma dels pesos de les rèpliques de 0 a i-th - més que això. D'aquesta manera podeu seleccionar una rèplica, i per seleccionar la següent, heu de repetir tot el procediment sense tenir en compte la rèplica seleccionada. Amb aquest algorisme, la complexitat d'escollir una rèplica és O(N), la complexitat d'escollir K rèpliques és O(N·K) ~ O(N2).
La complexitat quadràtica és dolenta, però es pot millorar. Per això construirem per a sumes de pesos. El resultat és un arbre de profunditat lg N, les fulles del qual contindran els pesos de les rèpliques, i els nodes restants contindran sumes parcials, fins a la suma de tots els pesos a l'arrel de l'arbre. A continuació, generem un nombre aleatori des de 0 fins a la suma de tots els pesos, trobem la rèplica i-è, l'eliminem de l'arbre i repetim el procediment per trobar les rèpliques restants. Amb aquest algorisme, la complexitat de construir un arbre és O(N), la complexitat de trobar la rèplica i-è i eliminar-la de l'arbre és O(lg N), la complexitat de triar K rèpliques és O(N + K lg N) ~ O(N lg N) .
La complexitat lineal-logarítmica és més agradable que la complexitat quadràtica, especialment per a K gran.
És aquest algorisme Biblioteques ClusterClient del projecte "" (Allà l'arbre està construït en O(N lg N), però això no afecta la complexitat final de l'algorisme.)
Problema 2. Zebra
Calia proposar un algorisme per ordenar eficaçment els documents a la memòria mitjançant un camp arbitrari no indexat:
El vostre equip té l'encàrrec de desenvolupar una base de dades de documents fragmentats a la memòria. Una càrrega de treball habitual seria seleccionar els N documents principals ordenats per un camp numèric arbitrari (no indexat) d'una col·lecció de mida M (normalment N < 100 << M). Una càrrega de treball una mica menys habitual seria seleccionar la N superior després de saltar-se els documents S a la part superior (S ~ N).
Proposeu un algorisme per executar aquestes consultes de manera eficient. Estimar la seva complexitat computacional utilitzant la notació O gran en el cas mitjà i en els pitjors escenaris.
Anàlisi de la solució (vídeo)
Comença a les 34:50, només 6 minuts:
Anàlisi de la solució (text)
Solució a la superfície: ordena tots els documents (per exemple, utilitzant ), després prengui documents N+S. En aquest cas, la complexitat de la classificació de mitjana és O(M lg M), en el pitjor és O(M2).
Òbviament, ordenar tots els documents M i després agafar-ne només una petita part és ineficient. Per no ordenar tots els documents, servirà un algorisme , que seleccionarà N+S documents necessaris (es poden ordenar per qualsevol algorisme). En aquest cas, la complexitat es reduirà a O(M) de mitjana, i el pitjor dels casos es mantindrà igual.
Tanmateix, podeu fer-ho de manera encara més eficient: utilitzeu l'algoritme . En aquest cas, els primers documents N+S s'afegeixen a un munt mínim o màxim (segons la direcció d'ordenació) i després es compara cada document posterior amb l'arrel de l'arbre, que conté el document mínim o màxim actual. , i, si cal, s'afegeix a l'arbre . En aquest cas, la complexitat en el pitjor dels casos, quan has de reconstruir l'arbre constantment, és O(M lg M), la complexitat de mitjana és O(M), com quan s'utilitza la selecció ràpida.
No obstant això, la transmissió de l'emmagatzematge dinàmic resulta més eficient a causa del fet que a la pràctica la majoria dels documents es poden descartar sense reconstruir l'emmagatzematge dinàmic, després d'una única comparació amb el seu element arrel. Aquesta ordenació s'implementa a la base de dades de documents en memòria de Zebra, desenvolupada i utilitzada a Kontur.
Problema 3. Canvis d'estats
Va ser necessari proposar l'algoritme més eficient per al canvi d'estats:
El vostre equip té l'encàrrec de desenvolupar un mecanisme d'intercanvi d'estats fantàstic per a un clúster distribuït de N nodes. L'estat del node i s'ha de transferir al node (i+1)-è, l'estat del node N-è s'ha de transferir al primer node. L'única operació admesa és l'intercanvi d'estats quan dos nodes intercanvien els seus estats atòmicament. Se sap que un intercanvi d'estat triga M mil·lisegons. Cada node pot participar en un sol intercanvi d'estats en un moment donat.
Quant de temps es triga a transferir els estats de tots els nodes d'un clúster?
Anàlisi de la solució (text)
La solució a la superfície: intercanviar els estats del primer i segon element, després el primer i el tercer, després el primer i el quart, etc. Després de cada intercanvi, l'estat d'un element estarà a la posició desitjada. Haureu de fer permutacions O(N) i passar temps O(N·M).
El temps lineal és llarg, de manera que podeu intercanviar els estats dels elements per parelles: el primer amb el segon, el tercer amb el quart, etc. Després de cada intercanvi d'estat, cada segon element estarà a la posició desitjada. Haureu de fer permutacions O(lg N) i passar temps O(M lg N).
Tanmateix, podeu fer que el canvi sigui encara més eficient, no de manera lineal, sinó en temps constant. Per fer-ho, en el primer pas cal intercanviar l'estat del primer element amb l'últim, el segon amb el penúltim, etc. L'estat de l'últim element estarà a la posició desitjada. I ara hem d'intercanviar l'estat del segon element amb l'últim, el tercer amb el penúltim, etc. Després d'aquesta ronda d'intercanvis, els estats de tots els elements estaran a la posició desitjada. En total, es faran permutacions O(2M) ~ O(1).
Aquesta solució no sorprendrà gens a un matemàtic, que encara recorda que la rotació és una composició de dues simetries axials. Per cert, es generalitza trivialment el desplaçament no d'una, sinó de K < N posicions. (Escriu als comentaris exactament com.)
T'han agradat els puzles? Coneixes altres solucions? Comparteix en els comentaris.
Aquí teniu alguns enllaços útils finals:
- obtenir més informació sobre en Kontur
- mirar els registres interns sobre sistemes distribuïts
- mireu la sèrie de videoconferències "»
- subscriu-te al nostre
Font: www.habr.com