Redundant Queuing – Performance and Optimization
No Thumbnail Available
Journal Title
Journal ISSN
Volume Title
Sähkötekniikan korkeakoulu |
Master's thesis
Author
Date
2018-06-18
Department
Major/Subject
Communications Engineering
Mcode
ELEC3029
Degree programme
CCIS - Master’s Programme in Computer, Communication and Information Sciences (TS2013)
Language
en
Pages
48 + 46
Series
Abstract
Large, complex and interactive systems need to heavily parallelize their operations in order to achieve low latency. This involves keeping the tail of the latency distribution short. A request is broken into tasks which need to be completed for the request to finish. Long tail latency is caused by “stragglers,” which take an unexpectedly long time to complete and are thus the last few tasks of the job. The initial solution to these “stragglers” arose from the realization that response times on even seemingly homogeneous servers can vary greatly. Redundant copies of the same task are sent to multiple servers simultaneously, and after one of them finishes, the remaining copies are flushed. This significantly reduces latency, but it also adds to the system load, and when one copy is completed there is the cost of deleting the redundant copies. This thesis analyzed this redundancy policy in a 2-server system, both analytically and through simulation. Jobs were replicated immediately and not broken into tasks. The performance of different classes of jobs, one redundant and two non-redundant, was calculated in terms of latency. The analytical results were premised on Poisson arrivals, exponential service times and the First-Come-First-Served policy. The redundancy policy was compared to JSQ (Join-Shortest-Queue-First) and Opt-Split (Optimally-Probabilistically-Splitting-Load) policy. The system was then simulated and the service time distributions were replaced by Erlang and Weibull distributions, with different variances. The system was then optimized by iteratively finding the optimal portion of the load to replicate. The results of the study demonstrated that the redundancy policy outperforms JSQ and Opt-Split in terms of latency if stability conditions apply. Moreover, redundancy has lower latency than JSQ, which has lower latency than Opt-Split. Furthermore, redundancy benefits from service time distributions with higher variance. If there are non-redundant jobs, latency is worse, with higher variance when the relative portion of redundant jobs is low, but better when the portion is high. Finally, the study found a variance threshold above which it is better for the system to be fully redundant. Below this threshold, the portion of redundant jobs needs to dynamically change according to the load.Suurien, monimutkaisten ja interaktiivisten systeemien täytyy suuressa määrin rinnakkaistaa operaatioitaan saavuttaakseen alhaisen viiveen. Tähän liittyy viiveen häntäjakauman pitäminen lyhyenä. Työ jaetaan tehtäviin, joiden kaikkien tulee valmistua. Pitkä häntäviive johtuu ”harhailijoista”, jotka ovat viimeisimpiä tehtäviä, koska niiden suorittaminen on kestänyt odottamattoman kauan. Alkuperäinen ratkaisu näihin ”harhailijoihin” löytyi siitä ymmärryksestä, että vasteajat voivat heitellä paljon, jopa näennäisen homogeenisten servereiden välillä. Saman työn redundantteja kopioita lähetetään usealle serverille yhtäaikaisesti, ja yhden valmistuttua, loput poistetaan. Tämä merkittävästi alentaa viivettä, mutta myös lisää systeemin työtaakkaa, ja redundanttien kopioien poisto myös vie aikaa. Tämä työ analysoi tätä redundanttia menettelytapaa kahden serverin systeemissä, sekä analyyttisesti että simuloiden. Työt replikoitiin välittömästi, eikä niitä jaettu tehtäviin. Eri luokan töiden suorituskyky, yksi redundatti ja kaksi ei-redundanttia, laskettiin viveenä. Analyyttiset tulokset olettivat Poisson saapumiset, eksponentiaalisesti jakautuneet palveluajat ja FCFS jonokurin. Redundanttia menettelytapaa verrattiin JSQ ja Opt-Split menettelytapoihin. Sitten systeemi simuloitiin ja palveluaikojen jakauma vaihdettiin Erlang ja Weibull jakaumiin eri variansseilla. Tämän jälkeen systeemi optimoitiin iteratiivisesti etsimällä replikoitavan osuuden koko. Tämä työ osoittaa, että redundantin menettelytavan suorituskyky ylittää JSQ ja Opt-Splitin viiveen näkökulmasta tasapainoehtojen ollessa voimassa. Lisäksi, redundassilla on alhaisempi viive kuin JSQ:lla, jolla on alhaisempi viive kuin Opt-Splitilla. Sitä paitsi, redundanssi hyötyy korkeamman varianssin palveluaika jakaumista. Korkeammalla varianssilla viive on alhaisempi, jos redundattien töiden osuus suhteessa ei-redundantteihin töihin on suuri ja päinvastoin. Lopuksi, tutkimus paljasti varianssirajan, jonka yläpuolella on kaikkien töiden parempi olla redundantteja. Tämän rajan alapuolella, redundanttien töiden suhteellista osuutta tulee dynaamisesti muuttaa työtaakan mukaisesti.Description
Supervisor
Aalto, SamuliThesis advisor
Aalto, SamuliKeywords
redundancy, queuing, JSQ, Opt-Split
