DSP Algorithm Principles and Application in Crane Predictive Autoscaling

This article explains the Digital Signal Processing (DSP) algorithm used in Crane, a cloud-native predictive autoscaling tool developed by Tencent Cloud. The content addresses the limitations of native Kubernetes Horizontal Pod Autoscaler (HPA), which uses threshold-based reactive mechanisms that cannot effectively handle applications with slow cold start times.

The article begins by introducing the concept of time series in real-world monitoring systems, where metrics like CPU utilization are collected at fixed sampling frequencies (e.g., every 30 or 60 seconds), stored as discrete Timestamp:Value pairs in Prometheus. These time series data exhibit periodic tidal patterns in regular online business scenarios.

The core of the article delves into Fourier Transform theory, explaining how any periodic function can be represented as a superposition of sine waves with different amplitudes, phases, and frequencies. The article provides intuitive explanations using animations and diagrams to demonstrate how multiple waves combine to generate different time-domain patterns.

It then introduces Discrete Fourier Transform (DFT), which converts discrete time-domain signals to frequency-domain representations. The mathematical foundation is explained through the concept of the complex plane and unit circle, where signals are projected onto different frequencies. The article notes that naive DFT has O(n²) time complexity, making it impractical for large datasets, which led to the development of Fast Fourier Transform (FFT).

FFT is explained as a divide-and-conquer algorithm that reduces complexity to O(n*log₂(n)) by leveraging mathematical properties of complex roots of unity: periodicity, symmetry, and conjugacy. The two main stages of FFT are described: bit-reversal permutation (reordering samples) and butterfly computation (combining results).

The article concludes with practical application details of how Crane applies these algorithms: data preprocessing (filling missing values, removing anomalies), main period determination using FFT periodogram and Auto Correlation Function (ACF), prediction via IFFT, and status updates. Configuration parameters for the DSP algorithm are provided.

Python code example for generating square waves through wave superposition:

import numpy as np

import matplotlib.pylab as plt

x = np.linspace(-np.pi, np.pi, 100)

# 振幅

amp=4/np.pi

# 基波频率为 1/2π

base = amp*np.sin(x)

# 协波分量频率为3, 5, 7

harmonic1 = (amp/3)*np.sin(3*x)

harmonic2 = (amp/5)*np.sin(5*x)

harmonic3 = (amp/7)*np.sin(7*x)

merged=base+harmonic1+harmonic2+harmonic3

plt.plot(x,base)

plt.plot(x,harmonic1)

plt.plot(x,harmonic2)

plt.plot(x,harmonic3)

plt.plot(x,merged)

plt.show()

Crane DSP configuration example:

dsp:

sampleInterval:
"60s"
//采样时间间隔，Prometheus默认为60

historyLength:
"14d"
// predictor从监控系统拉取指标的历史长度

estimators:

fft:

- marginFraction:
"0.2"
// 预留资源余量

lowAmplitudeThreshold:
"1.0"
// 最低振幅阈值

highFrequencyThreshold:
"0.05"
// 最高频率阈值

minNumOfSpectrumItems:
10

maxNumOfSpectrumItems:
20