Abstract
We model and evaluate the performance of a distributed key-value storage system that is part of the Spotify backend. Spotify is an on-demand music streaming service, offering low-latency access to a library of over 20 million tracks and serving over 20 million users currently. We first present a simplified model of the Spotify storage architecture, in order to make its analysis feasible. We then introduce an analytical model for the distribution of the response time, a key metric in the Spotify service. We parameterize and validate the model using measurements from two different testbed configurations and from the operational Spotify infrastructure. We find that the model is accurate—measurements are within 11 % of predictions—within the range of normal load patterns. In addition, we model the capacity of the Spotify storage system under different object allocation policies and find that measurements on our testbed are within 9 % of the model predictions. The model helps us justify the object allocation policy adopted for Spotify storage system.
Similar content being viewed by others
References
Kreitz, G., Niemelä, F.: Spotify—large scale, low latency, P2P music-on-demand streaming. In: Peer-to-Peer Computing, pp. 1–10. IEEE, Delft, The Netherlands (2010)
Yanggratoke, R., Kreitz, G., Goldmann, M., Stadler, R.: Predicting response times for the spotify backend. In: 2012 8th international conference on network and service management (CNSM), pp. 117–125 (2012)
Sysoev, I.: Nginx (2002). http://nginx.org/
Karger, D.R., Lehman, E., Leighton, F.T., Panigrahy, R., Levine, M.S., Lewin, D.: Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the world wide web. In: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, STOC ’97, pp. 654–663. ACM, New York, NY, USA (1997)
Kleinrock, L.: Theory, Volume 1, Queueing Systems. Wiley-Interscience, New York (1975)
Mosberger, D., Jin, T.: httperf—a tool for measuring web server performance. SIGMETRICS Perform. Eval. Rev. 26(3), 31–37 (1998)
Tarreau, W.: Haproxy. http://haproxy.1wt.eu/
Godard, S.: iostat. http://linux.die.net/man/1/iostat
Sovani, K.: Kernel korner—sleeping in the kernel. http://www.linuxjournal.com/article/8144
Jones, M.T.: Boost application performance using asynchronous i/o. http://www.ibm.com/developerworks/linux/library/l-async/
Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, Cambridge (2005)
Raab, M., Steger, A.: “Balls into Bins”—a simple and tight analysis. In: Proceedings of the Second International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM ’98, pp. 159–170. Springer, London, UK (1998)
Massey, F.J.: The Kolmogorov–Smirnov test for goodness of fit. J. Am. Stat. Assoc. 46(253), 68–78 (1951). doi:10.1080/01621459.1951.10500769
Goldstein, M., Morris, S., Yen, G.: Problems with fitting to the power-law distribution. Eur. Phys. J. B 41, 255–258 (2004). doi:10.1140/epjb/e2004-00316-5.
Zaliapin, I.V., Kagan, Y.Y., Schoenberg, F.P.: Approximating the distribution of pareto sums. Pure Appl. Geophys. 162, 1187–1228 (2005). doi:10.1007/s00024-004-2666-3
Thereska, E., Abd-El-Malek, M., Wylie, J., Narayanan, D., Ganger, G.: Informed data distribution selection in a self-predicting storage system. In: ICAC ’06. IEEE International Conference on Autonomic Computing, 2006, pp. 187–198 (2006) doi:10.1109/ICAC.2006.1662398
Gulati, A., Shanmuganathan, G., Ahmad, I., Waldspurger, C., Uysal, M.: Pesto: online storage performance management in virtualized datacenters. In: Proceedings of the 2nd ACM Symposium on Cloud Computing, SOCC ’11, pp. 19:1–19:14. ACM, New York, NY, USA (2011)
Kraft, S., Casale, G., Krishnamurthy, D., Greer, D., Kilpatrick, P.: Io performance prediction in consolidated virtualized environments. SIGSOFT Softw. Eng. Notes 36(5), 295–306 (2011)
Xiong, K., Perros, H.: Service performance and analysis in cloud computing. In: IEEE Congress on Services, pp. 693–700 (2009)
Khazaei, H., Misic, J., Misic, V.: Performance analysis of cloud computing centers using m/g/m/m+r queuing systems. IEEE Trans. Parallel Distrib. Syst. 23(5), 936–943 (2012)
Tewari, R., Mukherjee, R., Dias, D., Vin, H.: Design and performance tradeoffs in clustered video servers. In: Proceedings of the Third IEEE International Conference on Multimedia Computing and Systems, 1996, pp. 144–150 (1996). doi:10.1109/MMCS.1996.534966
Abd-El-Malek, M., Courtright II, W.V., Cranor, C., Ganger, G.R., Hendricks, J., Klosterman, A.J., Mesnier, M., Prasad, M., Salmon, B., Sambasivan, R.R., Sinnamohideen, S., Strunk, J.D., Thereska, E., Wachs, M., Wylie, J.J.: Ursa minor: versatile cluster-based storage. In: Proceedings of the 4th Conference on USENIX Conference on File and Storage Technologies—Volume 4, FAST’05, pp. 5–5. USENIX Association, Berkeley, CA, USA (2005)
DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., Sivasubramanian, S., Vosshall, P., Vogels, W.: Dynamo: amazon’s highly available key-value store. SIGOPS Oper. Syst. Rev. 41(6), 205–220 (2007)
Lakshman, A., Malik, P.: Cassandra: a decentralized structured storage system. SIGOPS Oper. Syst. Rev. 44(2), 35–40 (2010)
Schütt, T., Schintke, F., Reinefeld, A.: Scalaris: reliable transactional p2p key/value store. In: Proceedings of the 7th ACM SIGPLAN Workshop on ERLANG, ERLANG ’08, pp. 41–48. ACM, New York, NY, USA (2008)
Che, H., Tung, Y., Wang, Z.: Hierarchical web caching systems: modeling, design and experimental results. IEEE J. Sel. Areas Commun. 20(7), 1305–1314 (2002). doi:10.1109/JSAC.2002.801752
Hou, Y., Pan, J., Li, B., Tang, X., Panwar, S.: Modeling and analysis of an expiration-based hierarchical caching system. In: Global Telecommunications Conference, 2002. GLOBECOM ’02. IEEE, vol. 3, pp. 2468–2472 (2002). doi:10.1109/GLOCOM.2002.1189074
Hou, Y., Pan, J., Li, B., Panwar, S.: On expiration-based hierarchical caching systems. IEEE J. Sel. Areas Commun. 22(1), 134–150 (2004). doi:10.1109/JSAC.2003.818804
Hu, X., Zincir-Heywood, A.: Understanding the performance of cooperative web caching systems. In: Proceedings of the 3rd Annual Communication Networks and Services Research Conference, 2005, pp. 183–188 (2005). doi:10.1109/CNSR.2005.61
Fricker, C., Robert, P., Roberts, J.: A versatile and accurate approximation for lru cache performance. In: Proceedings of the 24th International Teletraffic Congress, ITC ’12, pp. 8:1–8:8. International Teletraffic Congress (2012). http://dl.acm.org/citation.cfm?id=2414276.2414286
Ho, K.M., Poon, W.F., Lo, K.T.: Investigating the performance of hierarchical video-on-demand system in heterogeneous environment. In: International Conference on Information Networking, 2008. ICOIN 2008, pp. 1–5 (2008). doi:10.1109/ICOIN.2008.4472804
Karedla, R., Love, J., Wherry, B.: Caching strategies to improve disk system performance. Computer 27(3), 38–46 (1994). doi:10.1109/2.268884
Trushkowsky, B., Bodík, P., Fox, A., Franklin, M.J., Jordan, M.I., Patterson, D.A.: The scads director: scaling a distributed storage system under stringent performance requirements. In: Proceedings of the 9th USENIX conference on File and stroage technologies, FAST’11, pp. 12–12. USENIX Association, Berkeley, CA, USA (2011). http://dl.acm.org/citation.cfm?id=1960475.1960487
Al-Shishtawy, A., Vlassov, V.: Elastman: autonomic elasticity manager for cloud-based key-value stores. Tech. Rep. 12:01, KTH, Software and Computer Systems, SCS (2012). QC 20120831
Klems, M., Silberstein, A., Chen, J., Mortazavi, M., Albert, S.A., Narayan, P., Tumbde, A., Cooper, B.: The yahoo!: cloud datastore load balancer. In: Proceedings of the Fourth International Workshop on Cloud Data Management, CloudDB ’12, pp. 33–40. ACM, New York, NY, USA (2012). doi:10.1145/2390021.2390028.
Dario, V., Cesar, M., Yacine, G.D.: Performance evaluation of an object management policy approach for p2p networks. Int. J. Digit. Multimed. Broadcast. (2012). doi:10.1155/2012/189325 http://www.hindawi.com/journals/ijdmb/2012/189325/cta/
Fujimoto, T., Endo, R., Matsumoto, K., Shigeno, H.: Video-popularity-based caching scheme for p2p video-on-demand streaming. In: IEEE International Conference on Advanced Information Networking and Applications (AINA), 2011, pp. 748–755 (2011). doi:10.1109/AINA.2011.103
Chellouche, S., Negru, D., Chen, Y., Sidibe, M.: Home-box-assisted content delivery network for internet video-on-demand services. In: IEEE Symposium on Computers and Communications (ISCC), 2012, pp. 000544–000550 (2012) doi:10.1109/ISCC.2012.6249353
Zhou, Y., Fu, T., Chiu, D.M.: Division-of-labor between server and p2p for streaming vod. In: IEEE 20th International Workshop on Quality of Service (IWQoS), 2012, pp. 1–9 (2012) doi:10.1109/IWQoS.2012.6245979
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Yanggratoke, R., Kreitz, G., Goldmann, M. et al. On the Performance of the Spotify Backend. J Netw Syst Manage 23, 210–237 (2015). https://doi.org/10.1007/s10922-013-9292-2
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10922-013-9292-2