IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v27y2024i2d10.1007_s10951-023-00803-8.html
   My bibliography  Save this article

A scheduling framework for distributed key-value stores and its application to tail latency minimization

Author

Listed:
  • Sonia Ben Mokhtar

    (LIRIS)

  • Louis-Claude Canon

    (Université de Franche-Comté)

  • Anthony Dugois

    (Université de Franche-Comté
    École Normale Supérieure de Lyon, CNRS & Inria)

  • Loris Marchal

    (École Normale Supérieure de Lyon, CNRS & Inria)

  • Etienne Rivière

    (UCLouvain)

Abstract

Distributed key-value stores employ replication for high availability. Yet, they do not always efficiently take advantage of the availability of multiple replicas for each value and read operations often exhibit high tail latencies. Various replica selection strategies have been proposed to address this problem, together with local request scheduling policies. It is difficult, however, to determine what is the absolute performance gain each of these strategies can achieve. We present a formal framework allowing the systematic study of request scheduling strategies in key-value stores. We contribute a definition of the optimization problem related to reducing tail latency in a replicated key-value store as a minimization problem with respect to the maximum weighted flow criterion. By using scheduling theory, we show the difficulty of this problem and therefore the need to develop performance guarantees. We also study the behavior of heuristic methods using simulations that highlight which properties enable limiting tail latency: for instance, the EarliestFinishTime strategy—which uses the earliest next available time of servers—exhibits a tail latency that is less than half that of state-of-the-art strategies, often matching the lower bound. Our study also emphasizes the importance of metrics such as the stretch to properly evaluate replica selection and local execution policies.

Suggested Citation

  • Sonia Ben Mokhtar & Louis-Claude Canon & Anthony Dugois & Loris Marchal & Etienne Rivière, 2024. "A scheduling framework for distributed key-value stores and its application to tail latency minimization," Journal of Scheduling, Springer, vol. 27(2), pages 183-202, April.
  • Handle: RePEc:spr:jsched:v:27:y:2024:i:2:d:10.1007_s10951-023-00803-8
    DOI: 10.1007/s10951-023-00803-8
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-023-00803-8
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10951-023-00803-8?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Leung, Joseph Y.-T. & Li, Chung-Lun, 2016. "Scheduling with processing set restrictions: A literature update," International Journal of Production Economics, Elsevier, vol. 175(C), pages 1-11.
    2. Peter Brucker & Bernd Jurisch & Andreas Krämer, 1997. "Complexity of scheduling problems with multi-purpose machines," Annals of Operations Research, Springer, vol. 70(0), pages 57-73, April.
    3. Leung, Joseph Y.-T. & Li, Chung-Lun, 2008. "Scheduling with processing set restrictions: A survey," International Journal of Production Economics, Elsevier, vol. 116(2), pages 251-262, December.
    4. Jinwen Ou & Joseph Y.‐T. Leung & Chung‐Lun Li, 2008. "Scheduling parallel machines with inclusive processing set restrictions," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(4), pages 328-338, June.
    5. Kangbok Lee & Joseph Leung & Michael Pinedo, 2013. "Makespan minimization in online scheduling with machine eligibility," Annals of Operations Research, Springer, vol. 204(1), pages 189-222, April.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Huiqiao Su & Michael Pinedo & Guohua Wan, 2017. "Parallel machine scheduling with eligibility constraints: A composite dispatching rule to minimize total weighted tardiness," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(3), pages 249-267, April.
    2. Ferreira, Cristiane & Figueira, Gonçalo & Amorim, Pedro, 2021. "Scheduling Human-Robot Teams in collaborative working cells," International Journal of Production Economics, Elsevier, vol. 235(C).
    3. Li, Shuguang, 2017. "Parallel batch scheduling with inclusive processing set restrictions and non-identical capacities to minimize makespan," European Journal of Operational Research, Elsevier, vol. 260(1), pages 12-20.
    4. Xianglai Qi & Jinjiang Yuan, 2017. "Semi-online hierarchical scheduling for $$l_p$$ l p -norm load balancing with buffer or rearrangements," 4OR, Springer, vol. 15(3), pages 265-276, September.
    5. André Rossi & Alexis Aubry & Mireille Jacomino, 2011. "A sensitivity analysis to assess the completion time deviation for multi-purpose machines facing demand uncertainty," Annals of Operations Research, Springer, vol. 191(1), pages 219-249, November.
    6. Xianglai Qi & Jinjiang Yuan, 2019. "Semi-Online Hierarchical Scheduling on Two Machines for lp-Norm Load Balancing," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 36(01), pages 1-16, February.
    7. Jinwen Ou & Xueling Zhong & Xiangtong Qi, 2016. "Scheduling parallel machines with inclusive processing set restrictions and job rejection," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(8), pages 667-681, December.
    8. Juntaek Hong & Kangbok Lee & Michael L. Pinedo, 2020. "Scheduling equal length jobs with eligibility restrictions," Annals of Operations Research, Springer, vol. 285(1), pages 295-314, February.
    9. Chuleeporn Kusoncum & Kanchana Sethanan & Richard F. Hartl & Thitipong Jamrus, 2022. "Modified differential evolution and heuristic algorithms for dump tippler machine allocation in a typical sugar mill in Thailand," Operational Research, Springer, vol. 22(5), pages 5863-5895, November.
    10. Leung, Joseph Y.-T. & Li, Chung-Lun, 2016. "Scheduling with processing set restrictions: A literature update," International Journal of Production Economics, Elsevier, vol. 175(C), pages 1-11.
    11. Claire Hanen & Alix Munier Kordon, 2024. "Fixed-parameter tractability of scheduling dependent typed tasks subject to release times and deadlines," Journal of Scheduling, Springer, vol. 27(2), pages 119-133, April.
    12. Leung, Joseph Y-T. & Ng, C.T., 2017. "Fast approximation algorithms for uniform machine scheduling with processing set restrictions," European Journal of Operational Research, Elsevier, vol. 260(2), pages 507-513.
    13. Giorgi Tadumadze & Simon Emde & Heiko Diefenbach, 2020. "Exact and heuristic algorithms for scheduling jobs with time windows on unrelated parallel machines," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(2), pages 461-497, June.
    14. Li, Weidong & Ou, Jinwen, 2024. "Approximation algorithms for scheduling parallel machines with an energy constraint in green manufacturing," European Journal of Operational Research, Elsevier, vol. 314(3), pages 882-893.
    15. Kangbok Lee & Joseph Leung & Michael Pinedo, 2013. "Makespan minimization in online scheduling with machine eligibility," Annals of Operations Research, Springer, vol. 204(1), pages 189-222, April.
    16. Hans Kellerer & Joseph Y.‐T. Leung & Chung‐Lun Li, 2011. "Multiple subset sum with inclusive assignment set restrictions," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(6), pages 546-563, September.
    17. Dominik Kress & Sebastian Meiswinkel & Erwin Pesch, 2018. "Mechanism design for machine scheduling problems: classification and literature overview," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(3), pages 583-611, July.
    18. Li, Shuguang, 2017. "Approximation algorithms for scheduling jobs with release times and arbitrary sizes on batch machines with non-identical capacities," European Journal of Operational Research, Elsevier, vol. 263(3), pages 815-826.
    19. Feifeng Zheng & Yuhong Chen & Ming Liu & Yinfeng Xu, 2022. "Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 1060-1076, September.
    20. Lin-Hui Sun & Kai Cui & Ju-Hong Chen & Jun Wang & Xian-Chen He, 2013. "Research on permutation flow shop scheduling problems with general position-dependent learning effects," Annals of Operations Research, Springer, vol. 211(1), pages 473-480, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jsched:v:27:y:2024:i:2:d:10.1007_s10951-023-00803-8. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.