Change search
ReferencesLink to record
Permanent link

Direct link
Dynamic load balancing based on latency prediction
KTH, School of Information and Communication Technology (ICT).
2013 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Spotify is a music streaming service that offers access to a vast music catalogue; it counts more than 24 million active users in 28 different countries. Spotify's backend is made up by a constellation of independent loosely-coupled services; each service consists of a set of replicas, running on a set of servers in multiple data centers: each request to a service needs to be routed to an appropriate replica. Balancing the load across replicas is crucial to exploit available resources in the best possible way, and to provide optimal performances to clients. The main aim of this project is exploring the possibility of developing a load balancing algorithm that exploits request-reply latencies as its only load index. There are two reasons why latency is an appealing load index: in the first place it has a significant impact on the experience of Spotify users; in the second place, identifying a good load index in a distributed system presents significant challenges due to phenomena that might arise from the interaction of the different system components such as multi-bottlenecks. The use of latency as load index is even more attractive under this light, because it allows for a simple black box model where it is not necessary to model resource usage patterns and bottlenecks of every single service individually: modeling each system would be an impractical task, due both to the number of services and to the speed at which these services evolve. In this work, we justify the choice of request-reply latency as a load indicator, by presenting empirical evidence that it correlates well with known reliable load index obtained through a white box approach. In order to assess the correlation between latency and a known load index obtained through a white box approach, we present measurements from the production environment and from an ad-hoc test environment. We present the design of a novel load balancing algorithm based on a modified ' accrual failure detector that exploits request-reply latency as an indirect measure of the load on individual backends; we analyze the algorithm in detail, providing an overview of potential pitfalls and caveats; we also provide an empirical evaluation of our algorithm, compare its performances to a pure round-robin scheduling discipline and discuss which parameters can be tuned and how they affect the overall behavior of the load balancer.

Place, publisher, year, edition, pages
2013. , 121 p.
TRITA-ICT-EX, 2013:255
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-143333OAI: diva2:706244
Subject / course
Information and Software Systems
Educational program
Master of Science in Engineering - Computer Science and Technology
Available from: 2014-03-19 Created: 2014-03-19 Last updated: 2014-03-19Bibliographically approved

Open Access in DiVA

fulltext(6512 kB)240 downloads
File information
File name FULLTEXT01.pdfFile size 6512 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
School of Information and Communication Technology (ICT)
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 240 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 766 hits
ReferencesLink to record
Permanent link

Direct link