Exploiting Temporal-Spatial Characteristics for Function Scheduling in Serverless Computing

Jin Xin; Wu Bingyang; Liu Fangyue; Zhang Zili; Jia Yunshan

doi:10.7544/issn1000-1239.202330410

Journal of Computer Research and Development > 2023 > 60(9): 2000-2014. > DOI: 10.7544/issn1000-1239.202330410

Jin Xin, Wu Bingyang, Liu Fangyue, Zhang Zili, Jia Yunshan. Exploiting Temporal-Spatial Characteristics for Function Scheduling in Serverless Computing[J]. Journal of Computer Research and Development, 2023, 60(9): 2000-2014. DOI: 10.7544/issn1000-1239.202330410

Citation:

PDF (2045 KB)

Exploiting Temporal-Spatial Characteristics for Function Scheduling in Serverless Computing

School of Computer Science, Peking University, Beijing 100871
Key Laboratory of High Confidence Software Technologies(Peking University), Ministry of Education, Beijing 100871

Funds: This work was supported by the National Key Research and Development Program of China (2022YFB4500700).

More Information

Author Bio:
Jin Xin: born in 1989. PhD, associate professor. Senior member of CCF. His main research interests include systems software, computer networks, and cloud computing

Wu Bingyang: born in 2000. PhD candidate. Student member of CCF. His main research interests include machine learning systems, video conferencing, and cloud computing

Liu Fangyue: born in 2002. Undergraduate. His main research interests include cloud computing and machine learning systems

Zhang Zili: born in 2000. Undergraduate. His main research interests include machine learning systems and cloud computing

Jia Yunshan: born in 1999. PhD candidate. Student member of CCF. Her main research interests include wireless networks and cloud computing
Received Date: May 29, 2023
Revised Date: July 20, 2023
Available Online: July 31, 2023

Graphical Abstract

Abstract

Abstract

Serverless computing is an emerging function-centric cloud computing paradigm. It exposes a high-level function abstraction for users to write and deploy applications on cloud computing platforms. Serverless computing allocates resources based on the granulation of functions. Function scheduling is critical to function performance. It faces two difficulties, which are large problem space and high dynamism. Existing schedulers for serverless computing use a first-come-first-serve (FCFS) algorithm, which has head-of-line blocking and results in long function completion time. In order to highly utilize system resources and reduce function completion time, it is important to study the problem of function scheduling in serverless computing. First, we analyze the problem of function scheduling in serverless computing, and identify two factors that affect function completion time, which are queueing time, start time and execution time. Based on the analysis, we propose a mathematical model to formalize the problem of function scheduling in serverless computing. Second, we propose a scheduling algorithm, called FuncSched, based on temporal-spatial characterstics for serverless computing. The algorithm considers function execution time and function start time in the time dimension, and function resource consumption in the space dimension. Finally, we implement a system prototype, and evaluate it with real-world serverless computing workload datasets. Experimental results show that the proposed algorithm can effectively reduce average function completion time, thus effectively improving function execution efficiency in serverless computing.
- serverless computing,
- function scheduling,
- temporal-spatial characteristics,
- cold start,
- cloud computing

FullText(HTML)

References (43)

References

[1]	Schleier-Smith J, Sreekanti V, Khandelwal A, et al. What serverless computing is and should become: The next phase of cloud computing[J]. Communications of the ACM, 2021, 64(5): 76−84 doi: 10.1145/3406011
[2]	OpenWhisk. Open Source Serverless Cloud Platform [EB/OL]. (2022-06-08)[2023-05-24].https://openwhisk.apache.org
[3]	Shahrad M, Fonseca R, Goiri Í, et al. Serverless in the Wild: Characterizing and optimizing the serverless workload at a large cloud provider[C]//Proc of the USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2020: 205−218
[4]	Fuerst A, Sharma P. FaasCache: Keeping serverless computing alive with greedy-dual caching[C]//Proc of the ACM Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: Association for Computing Machinery, 2021: 386−400
[5]	Oakes E, Yang L, Zhou D, et al. SOCK: Rapid task provisioning with serverless-optimized containers[C]//Proc of the USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2018: 57−70
[6]	Roy R, Patel T, Tiwari D. IceBreaker: Warming serverless functions better with heterogeneity[C]//Proc of the ACM Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: Association for Computing Machinery, 2022: 753−767
[7]	Harter T, Salmon B, Liu R, et al. Slacker: Fast distribution with lazy docker containers[C]//Proc of the USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2016: 181−195
[8]	Zheng Chao, Rupprecht L, Tarasov V, et al. Wharf: Sharing docker images in a distributed file system[C]//Proc of the ACM Symp on Cloud Computing. New York: Association for Computing Machinery, 2018: 174−185
[9]	Liu Haifeng, Ding Wei, Chen Yuan, et al. CFS: A distributed file system for large scale container platforms[C]//Proc of the Int Conf on Management of Data. New York: Association for Computing Machinery, 2019: 1729−1742
[10]	Li Huiba, Yuan Yifan, Du Rui, et al. DADI: Block-level image service for agile and elastic application deployment[C]//Proc of the USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2020: 727−740
[11]	Zhang Zhaoning, Li Ziyang, Wu Kui, et al. VMThunder: Fast provisioning of large-scale virtual machine clusters[J]. IEEE Transations on Parallel and Distributed Systems, 2014, 25(12): 3328−3338 doi: 10.1109/TPDS.2014.7
[12]	Wang Ao, Chang Shuai, Tian Huangshi, et al. FaaSNet: Scalable and fast provisioning of custom serverless container runtimes at Alibaba cloud function compute[C]// Proc of the USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2021: 443–457
[13]	Cadden J, Unger T, Awad Y, et al. SEUSS: Skip redundant paths to make serverless fast[C]//Proc of the European Conf on Computer Systems. New York: Association for Computing Machinery, 2020: 1−15
[14]	Madhavapeddy A, Mortier R, Rotsos C, et al. Unikernels: Library operating systems for the cloud[C]//Proc of the Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: Association for Computing Machinery, 2013: 461−472
[15]	Wang K A, Ho R, Wu Peng. Replayable execution optimized for page sharing for a managed runtime environment[C]//Proc of the European Conf on Computer Systems. New York: Association for Computing Machinery, 2019: 1−16
[16]	Shin W A, Kim W H, Min C. Fireworks: A fast, efficient, and safe serverless framework using VM-level post-JIT snapshot[C]//Proc of the European Conf on Computer Systems. New York: Association for Computing Machinery, 2022: 663−677
[17]	Du Dong, Yu Tianyi, Xia Yubin, et al. Catalyzer: Sub-millisecond startup for serverless computing with initialization-less booting[C]//Proc of the Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: Association for Computing Machinery, 2020: 467−481
[18]	Bornstein D. Dalvik Virtual Machine Internals, Talk at Google I/O [EB/OL]. (2023-05-11)[2023-05-24].https://sites.google.com/site/io/dalvik-vm-internals
[19]	Li Zijun, Guo Linsong, Chen Quan, et al. Help rather than recycle: Alleviating cold startup in serverless computing through inter-function container sharing[C]//Proc of the USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2022: 69−84
[20]	AWS. AWS Lambda [EB/OL]. (2023-05-12)[2023-05-24].https://aws.amazon.com/lambda/
[21]	Ggailey. Getting started with Azure functions [EB/OL]. (2023-05-24)[2023-05-24].https://learn.microsoft.com/en-us/azure/azure-functions/functions-get-started
[22]	Google Cloud. Cloud functions [EB/OL]. (2023-05-24)[2023-05-24].https://cloud.google.com/functions?hl=zh-cn
[23]	Box G, Pierce D. Distribution of residual autocorrelations in autoregressive-integrated moving average time series models[J]. Journal of the American Statistical Association, 1970, 65(332): 1509−1526 doi: 10.1080/01621459.1970.10481180
[24]	Yang Yanan, Zhao Laiping, Li Yiming, et al. INFless: A native serverless system for low-latency, high-throughput inference[C]//Proc of the ACM Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: Association for Computing Machinery, 2022: 768−781
[25]	Zhou Zhuangzhuang, Zhang Yanqi, Delimitrou C. AQUATOPE: QoS-and-uncertainty-aware resource management for multi-stage serverless workflows[C]//Proc of the ACM Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: Association for Computing Machinery, 2022: 1−14
[26]	Cherkasova L. Improving WWW Proxies Performance with Greedy-Dual-Size-Frequency Caching Policy[M]. Palo Alto, CA: Hewlett-Packard Laboratories, 1998
[27]	Agache A, Brooker M, Iordache A, et al. Firecracker: Lightweight virtualization for serverless applications[C]//Proc of the USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2020: 419−434
[28]	Li Zijun, Cheng Jiagan, Chen Quan, et al. RunD: A lightweight secure container runtime for high-density deployment and high-concurrency startup in serverless computing[C]//Proc of the USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2022: 53−68
[29]	Arpaci-Dusseau R, Arpaci-Dusseau A. Operating Systems: Three Easy Pieces[M]. North Charleston, SC: CreateSpace Independent Publishing Platform, 2014
[30]	Tanenbaum A, Bos H. Modern Operating Systems[M]. One Lake Street Upper Saddle River, NJ: Prentice Hall Press, 2015
[31]	Aalto S, Ayesta U, Righter R. On the Gittins index in the m/g/1 queue[J]. Queueing Systems, 2009, 63: 437−458 doi: 10.1007/s11134-009-9141-x
[32]	Chowdhury M, Stoica I. Efficient coflow scheduling without prior knowledge[J]. ACM SIGCOMM Computer Communication Review, 2015, 45(4): 393−406 doi: 10.1145/2829988.2787480
[33]	Nuyens M, Wierman A. The foreground–background queue: A survey[J]. Performance Evaluation, 2008, 65(3-4): 286-307 doi: 10.1016/j.peva.2007.06.028
[34]	Gu Juncheng, Chowdhury M, Shin K, et al. Tiresias: A GPU cluster manager for distributed deep learning[C]//Proc of the USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2019: 485−500
[35]	Kaffes K, Chong T, Humphries J, et al. Shinjuku: Preemptive scheduling for μsecond-scale tail latency[C]//Proc of the USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2019: 345−360
[36]	Demoulin H, Fried J, Pedisich I, et al. When idling is ideal: Optimizing tail-latency for heavy-tailed datacenter workloads with perséphone[C]//Proc of the ACM SIGOPS Symp on Operating Systems Principles. New York: Association for Computing Machinery, 2021: 621−637
[37]	Delgado P, Dinu F, Kermarrec A, et al. Hawk: Hybrid datacenter scheduling[C]//Proc of the USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2015: 499−510
[38]	Karanasos K, Rao S, Curino C, et al. Mercury: Hybrid centralized and distributed scheduling in large shared clusters[C]//Proc of the USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2015: 485−497
[39]	Ousterhout A, Fried J, Behrens J, et al. Shenango: Achieving high CPU efficiency for latency-sensitive datacenter workloads[C]//Proc of the USENIX Symp on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2019: 361−378
[40]	Fried J, Ruan Z, Ousterhout A, et al. Caladan: Mitigating interference at microsecond timescales[C]//Proc of the USENIX Conf on Operating Systems Design and Implementation. Berkeley, CA: USENIX Association, 2020: 281−297
[41]	Duda K, Cheriton D. Borrowed-virtual-time (BVT) scheduling: Supporting latency-sensitive threads in a general-purpose scheduler[J]. ACM SIGOPS Operating Systems Review, 1999, 33(5): 261−276 doi: 10.1145/319344.319169
[42]	Curino C, Difallah D, Douglas C, et al. Reservation-based scheduling: If you’re late don’t blame us![C]//Proc of the ACM Symp on Cloud Computing. New York: Association for Computing Machinery, 2014: 1−14
[43]	吕方, 崔慧敏, 霍玮, 等. 面向并发性能下降的调度策略的综述[J]. 计算机研究与发展, 2014, 51(1): 17−30 Lü Fang, Cui Huimin, Huo Wei, et al. Survey of scheduling policies for co-run degradation[J]. Journal of Computer Research and Development, 2014, 51(1): 17−30 (in Chinese)

[1]	Zheng Jieyu, Song Zhenyu, Zhu Haoliang, Zhao Yunlei, Lin Jingqiang, Fan jin. Efficient Software Implementations of NTRU Lattice-Based Key Encapsulation Mechanisms[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202440478
[2]	Wei Hongru, Huang Jingyi. SOTS: A Hash Function-Based Shorter Post-Quantum Digital Signature Scheme[J]. Journal of Computer Research and Development, 2021, 58(10): 2300-2309. DOI: 10.7544/issn1000-1239.2021.20210619
[3]	Wang Yongli, Xu Qiuliang. Principle and Research Progress of Quantum Computation and Quantum Cryptography[J]. Journal of Computer Research and Development, 2020, 57(10): 2015-2026. DOI: 10.7544/issn1000-1239.2020.20200615
[4]	Li Zichen, Xie Ting, Zhang Juanmei, Xu Ronghua. Post Quantum Authenticated Key Exchange Protocol Based on Ring Learning with Errors Problem[J]. Journal of Computer Research and Development, 2019, 56(12): 2694-2701. DOI: 10.7544/issn1000-1239.2019.20180874
[5]	Zhang Pingyuan, Jiang Han, Cai Jie, Wang Chenguang, Zheng Zhihua, Xu Qiuliang. Recent Advances in Lattice-Based Cryptography[J]. Journal of Computer Research and Development, 2017, 54(10): 2121-2129. DOI: 10.7544/issn1000-1239.2017.20170628
[6]	Zhang Junwei, Ma Zhuo, Ma Jianfeng, and Ji Wenjiang. UC Security Model of Position-Based Key Exchange[J]. Journal of Computer Research and Development, 2014, 51(2): 353-359.
[7]	Lai Xin, Huang Xiaofang, He Dake. An ID-Based Efficient Signcryption Key Encapsulation Scheme[J]. Journal of Computer Research and Development, 2009, 46(5): 857-863.
[8]	Liu Yongliang, Gao Wen, Yao Hongxun, Huang Tiejun. Security on Aydos et al's Elliptic Curve Cryptography Based Wireless Authentication Protocol[J]. Journal of Computer Research and Development, 2006, 43(12): 2076-2081.
[9]	Tian Ye, Zhang Yujun, Li Zhongcheng. A Survey of Identity-Based Cryptography Using Pairing[J]. Journal of Computer Research and Development, 2006, 43(10): 1810-1819.
[10]	Zheng Ji. An MDP Public-Key Digital Signature Scheme[J]. Journal of Computer Research and Development, 2005, 42(2).