{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T23:42:18Z","timestamp":1740181338490,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,5,23]],"date-time":"2022-05-23T00:00:00Z","timestamp":1653264000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,23]],"date-time":"2022-05-23T00:00:00Z","timestamp":1653264000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"The National Key Research and Development Program of China","award":["2019YFB1804502"],"award-info":[{"award-number":["2019YFB1804502"]}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61872392"],"award-info":[{"award-number":["61872392"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["61832020"],"award-info":[{"award-number":["61832020"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"the Major Program of Guangdong Basic and Applied Research","award":["2019B030302002"],"award-info":[{"award-number":["2019B030302002"]}]},{"name":"the Program for Guangdong Introducing Innovative and Entrepreneurial Teams under Grant","award":["2016ZT06D211"],"award-info":[{"award-number":["2016ZT06D211"]}]},{"DOI":"10.13039\/501100003453","name":"Guangdong Natural Science Foundation","doi-asserted-by":"crossref","award":["2018B030312002"],"award-info":[{"award-number":["2018B030312002"]}],"id":[{"id":"10.13039\/501100003453","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["CCF Trans. HPC"],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Cloud storage is a fundamental component of the cloud computing system, which significantly affects the overall performance and quality of service of the cloud. Cloud storage servers face the challenge of imbalanced workloads. According to our observations on the time series generated by cloud storage, we found that the imbalance workloads will dramatically increase the tail latency of data access in the multi-tenant scenario. The intuitive solution is to periodicity detect the imbalance storage nodes and re-balance the loads. However, there are four challenges to accurately detect load of storage in the cloud with multiple tenants since the load may change frequently in cloud. This paper proposes PrecisePeriod, a precise periodicity detection algorithm customized for multi-tenant cloud storage. It removes outliers through data preprocessing, employs the discrete wavelet transform to remove high-frequency noise while keeping frequency domain information, computes the candidate periodicity queue using the autocorrelation function, and determines precise period through periodicity verification. Then, we design a cloud storage load balancing scheduling strategy based on PrecisePeriod, and the evaluation shows that the PrecisePeriod scheduling significantly reduces tail latency while only bringing<jats:inline-formula><jats:alternatives><jats:tex-math>$$1-2\\%$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mn>1<\/mml:mn><mml:mo>-<\/mml:mo><mml:mn>2<\/mml:mn><mml:mo>%<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>overhead.<\/jats:p>","DOI":"10.1007\/s42514-022-00099-8","type":"journal-article","created":{"date-parts":[[2022,5,23]],"date-time":"2022-05-23T10:26:01Z","timestamp":1653301561000},"page":"321-338","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A tail-tolerant cloud storage scheduling based on precise periodicity detection"],"prefix":"10.1007","volume":"4","author":[{"given":"Yuxiao","family":"Han","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jia","family":"Ma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fei","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yubo","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nong","family":"Xiao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yutong","family":"Lu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhiguang","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,5,23]]},"reference":[{"key":"99_CR1","doi-asserted-by":"publisher","unstructured":"Almasri, A.: A new approach for testing periodicity. Commun. Statist. 40(7), 1196\u20131217 (2011) https:\/\/doi.org\/10.1080\/03610920903564743","DOI":"10.1080\/03610920903564743"},{"key":"99_CR2","unstructured":"Berthold, MR., H\u00f6ppner, F.: On clustering time series using euclidean distance and pearson correlation. In: arXiv preprint arXiv:1601.02213 (2016)"},{"key":"99_CR3","unstructured":"Box, G.E.P.: Time series analysis: forecasting and control, John Wiley & Sons, Hoboken (2015)"},{"volume-title":"Introduction to time series and forecasting","year":"2002","key":"99_CR4","unstructured":"Brockwell, P.J., Davis, R.A. (eds.): Introduction to time series and forecasting. Springer, New York (2002)"},{"key":"99_CR5","doi-asserted-by":"crossref","unstructured":"Cai, C., Harrington, P.d.B.: Different discrete wavelet transforms applied to denoising analytical data. J. Chem. Inform. Model. 38(6), 1161\u20131170. 10.1021\/ci980210j (1998)","DOI":"10.1021\/ci980210j"},{"key":"99_CR6","doi-asserted-by":"crossref","unstructured":"Cooper, RB.: Queueing theory. In: Pro-ceedings of the ACM \u201981 Conference. New York, NY, USA: Association for Computing Machinery, 119\u2013122. 10.1145\/800175 (1981)","DOI":"10.1145\/800175.809851"},{"key":"99_CR7","doi-asserted-by":"crossref","unstructured":"Daubechies, I.: Ten lectures on wavelets. SIAM (1992)","DOI":"10.1137\/1.9781611970104"},{"key":"99_CR8","unstructured":"Didona, D., Zwaenepoel, W.: Sizeaware sharding for improving tail latencies in inmemory key-value stores. In: 16th fUSENIXg Symposium on Networked Systems Design and Implementation (fNSDIg 19), pp. 79\u201394 (2019)"},{"key":"99_CR9","doi-asserted-by":"crossref","unstructured":"Elfeky, M.G., Aref, W.G., Elmagarmid, A.K.: Periodicity detection in time series databases. IEEE Transact.Knowledge Data Eng. 17(7), 875\u2013887 (2005)","DOI":"10.1109\/TKDE.2005.114"},{"key":"99_CR10","doi-asserted-by":"crossref","unstructured":"Eltabakh, M.Y., et al.: CoHadoop: exible data placement and its exploitation in Hadoop. In: Proceedings of the VLDB Endowment 4(9), 575\u2013585 (2011)","DOI":"10.14778\/2002938.2002943"},{"key":"99_CR11","doi-asserted-by":"crossref","unstructured":"Elyasi, N., et al.: (2017). Exploiting intra-request slack to improve SSD performance. In: Proceedings of the Twenty-Second International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 375\u2013388","DOI":"10.1145\/3037697.3037728"},{"key":"99_CR12","unstructured":"Hyndman, R.J., Athanasopoulos, G.: Forecasting: principles and practice. OTexts (2018)"},{"key":"99_CR13","unstructured":"Kim, J., et al.: Alleviating garbage collection interference through spatial separation in all ash arrays. In: 2019 fUSENIXg Annual Technical Conference (fUSENIXg fATCg 19), pp. 799-812 (2019)"},{"key":"99_CR14","doi-asserted-by":"crossref","unstructured":"Kumar, M., Patel, N.R., Woo, J.: Clustering seasonality patterns in the presence of errors. In: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 557\u2013563 (2002)","DOI":"10.1145\/775047.775129"},{"key":"99_CR15","unstructured":"Lange, H., Brunton, S.L., Kutz, J.N.: From Fourier to Koopman: spectral methods for long-term time series prediction. J. Mach. Learn. Res. 22(41), 1\u201338 (2021)"},{"key":"99_CR16","doi-asserted-by":"crossref","unstructured":"Lee, L-W., Scheuermann, P., Vingralek, R.: File assignment in parallel I\/O systems with minimal variance of service time. IEEE Transact. Comput. 49(2), 127\u2013140 (2000)","DOI":"10.1109\/12.833109"},{"key":"99_CR17","doi-asserted-by":"crossref","unstructured":"Madathil, D.K., et\u00a0al.: A static data placement strategy towards perfect load-balancing for distributed storage clusters. In: 2008 IEEE International Symposium on Parallel and Distributed Processing. IEEE, pp. 1\u20138 (2008)","DOI":"10.1109\/IPDPS.2008.4536489"},{"key":"99_CR18","doi-asserted-by":"crossref","unstructured":"Mezic, I., Surana, A.: Koopman mode decomposition for periodic\/quasi-periodic time dependence. IFAC-PapersOnLine 49(18), 690\u2013697 (2016)","DOI":"10.1016\/j.ifacol.2016.10.246"},{"key":"99_CR19","doi-asserted-by":"publisher","DOI":"10.1201\/9781420089776","volume-title":"Temporal data mining","author":"Theophano Mitsa","year":"2010","unstructured":"Mitsa, T.: Temporal data mining. CRC Press, Boca Raton (2010)"},{"key":"99_CR20","doi-asserted-by":"crossref","unstructured":"Percival, D.B., Walden, A.T.: Wavelet methods for time series analysis. Vol. 4. Cambridge university press, Cambridge (2000)","DOI":"10.1017\/CBO9780511841040"},{"key":"99_CR21","doi-asserted-by":"crossref","unstructured":"Rasheed, F., Alhajj, R.: A framework for periodic outlier pattern detection in time-series sequences. IEEE Transact. Cybern. 44(5), 569\u2013582 (2013)","DOI":"10.1109\/TSMCC.2013.2261984"},{"key":"99_CR22","doi-asserted-by":"publisher","unstructured":"Sellami, M., et al.: Clustering-based data placement in cloud computing: a predictive approach. Cluster Comput., pp. 1\u201326. https:\/\/doi.org\/10.1007\/s10586-021-03332-1(2021)","DOI":"10.1007\/s10586-021-03332-1"},{"key":"99_CR23","doi-asserted-by":"publisher","first-page":"814","DOI":"10.1016\/j.future.2017.08.034","volume":"105","author":"Yuliang Shi","year":"2020","unstructured":"Shi, Y., et al.: AdaptScale: an adaptive data scaling controller for improving the multiple performance requirements in Clouds. Future Gener. Comput. Syst. 105, 814\u2013823 (2020). https:\/\/doi.org\/10.1016\/j.future.2017.08.034","journal-title":"Future Generation Computer Systems"},{"key":"99_CR24","doi-asserted-by":"publisher","unstructured":"Skarlatos, D., Kim, N.S., Torrellas, J.: Pageforge: a near-memory content-aware page-merging architecture. In: Proceedings of the 50th Annual IEEE\/ACM International Symposium on Microarchitecture. MICRO-50 \u201917. Association for Computing Machinery, 302-314. https:\/\/doi.org\/10.1145\/3123939.3124540(2017)","DOI":"10.1145\/3123939.3124540"},{"key":"99_CR25","doi-asserted-by":"publisher","unstructured":"Sriraman, A., Dhanotia, A., Wenisch, T.F.: SoftSKU: optimizing server architectures for microservice diversity @scale. In: Proceedings of the 46th International Symposium on Computer Architecture. ISCA \u201919. New York, NY, USA: Association for Computing Machinery, 513\u2013526. isbn: 9781450366694. https:\/\/doi.org\/10.1145\/3307650.3322227(2019)","DOI":"10.1145\/3307650.3322227"},{"key":"99_CR26","unstructured":"Tavakkol, A.,\u00a0et al.: Mqsim: a framework for enabling realistic studies of modern multi-queue SSD devices. In: 16th fUSENIXg Conference on File and Storage Technologies (fFASTg 18), pp. 49\u201366. urlhttps:\/\/www.usenix.org\/conference\/fast18\/presentation\/tavakkol (2018)"},{"key":"99_CR27","doi-asserted-by":"crossref","unstructured":"Theodosiou, M.: Forecasting monthly and quarterly time series using STL decomposition. Int J. Forecast. 27(4), 1178\u20131195 (2011)","DOI":"10.1016\/j.ijforecast.2010.11.002"},{"key":"99_CR28","doi-asserted-by":"publisher","unstructured":"Tian, C.J.: A Limiting property of sample autocovariances of periodically correlated processes with application to period determination. J. Time Series Anal. 9(4), 411\u2013417. https:\/\/doi.org\/10.1111\/j.1467-9892.1988.tb00480.x(1988)","DOI":"10.1111\/j.1467-9892.1988.tb00480.x"},{"key":"99_CR29","doi-asserted-by":"crossref","unstructured":"Toller, M., Kern, R.: Robust parameter-free season length detection in time series. In: arXiv preprint arXiv:1911.06015 (2019)","DOI":"10.32614\/CRAN.package.sazedR"},{"key":"99_CR30","doi-asserted-by":"crossref","unstructured":"Toller, M., Santos, T., Kern R.: SAZED: parameter-free domain-agnostic season length estimation in time series data. Data Mining Knowledge Discovery 33(6), 1775\u20131798 (2019)","DOI":"10.1007\/s10618-019-00645-z"},{"key":"99_CR31","unstructured":"Tukey, J.W., et al.: Exploratory data analysis, vol. 2. Reading Mass (1977)"},{"key":"99_CR32","doi-asserted-by":"crossref","unstructured":"Vengadeswaran, S., Balasundaram, S.R.: Clust: grouping aware data placement for improving the performance of large-scale data management system. In: Proceedings of the 7th ACM IKDD CoDS and 25th COMAD, pp. 1\u20139 (2020)","DOI":"10.1145\/3371158.3371159"},{"key":"99_CR33","doi-asserted-by":"crossref","unstructured":"Vlachos, M., Yu, P., Castelli, V.: On periodicity detection and structural periodic similarity. In: Proceedings of the 2005 SIAM international conference on data mining. SIAM, pp. 449\u2013460 (2005)","DOI":"10.1137\/1.9781611972757.40"},{"key":"99_CR34","doi-asserted-by":"crossref","unstructured":"Vlachos, M., et al.: Identifying similarities, periodicities and bursts for online search queries. In: Proceedings of the 2004 ACM SIGMOD international conference on Management of data, pp. 131\u2013142 (2004)","DOI":"10.1145\/1007568.1007586"},{"key":"99_CR35","doi-asserted-by":"publisher","unstructured":"Wang, J., Chen, T., Huang, B.: Cyclo-period estimation for discrete-time cyclo-stationary signals. IEEE Transact. Signal Proces. 54(1), 83\u201394. https:\/\/doi.org\/10.1109\/TSP.2005.859237(2006)","DOI":"10.1109\/TSP.2005.859237"},{"key":"99_CR36","doi-asserted-by":"crossref","unstructured":"Wang, J., Shang, P., Yin, J.: Draw: a new data-grouping-aware data placement scheme for data intensive applications with interest locality. Cloud Comput. Data-Intensive Appl. Springer, pp. 149\u2013174 (2014)","DOI":"10.1007\/978-1-4939-1905-5_7"},{"key":"99_CR37","doi-asserted-by":"crossref","unstructured":"Yan, S., et al.: Tiny-tail ash: near-perfect elimination of garbage collection tail latencies in NAND SSDs. ACM Transact. Storage (TOS) 13(3), 1\u201326 (2017)","DOI":"10.1145\/3121133"}],"container-title":["CCF Transactions on High Performance Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42514-022-00099-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42514-022-00099-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42514-022-00099-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,25]],"date-time":"2024-09-25T19:15:52Z","timestamp":1727291752000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42514-022-00099-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,23]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["99"],"URL":"https:\/\/doi.org\/10.1007\/s42514-022-00099-8","relation":{},"ISSN":["2524-4922","2524-4930"],"issn-type":[{"type":"print","value":"2524-4922"},{"type":"electronic","value":"2524-4930"}],"subject":[],"published":{"date-parts":[[2022,5,23]]},"assertion":[{"value":"30 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest, financial or otherwise. On behalf of all authors, the corresponding author states that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}