  Kubernetes (k8s) has the potential to merge the distributed edge and the
cloud but lacks a scheduling framework specifically for edge-cloud systems.
Besides, the hierarchical distribution of heterogeneous resources and the
complex dependencies among requests and resources make the modeling and
scheduling of k8s-oriented edge-cloud systems particularly sophisticated. In
this paper, we introduce KaiS, a learning-based scheduling framework for such
edge-cloud systems to improve the long-term throughput rate of request
processing. First, we design a coordinated multi-agent actor-critic algorithm
to cater to decentralized request dispatch and dynamic dispatch spaces within
the edge cluster. Second, for diverse system scales and structures, we use
graph neural networks to embed system state information, and combine the
embedding results with multiple policy networks to reduce the orchestration
dimensionality by stepwise scheduling. Finally, we adopt a two-time-scale
scheduling mechanism to harmonize request dispatch and service orchestration,
and present the implementation design of deploying the above algorithms
compatible with native k8s components. Experiments using real workload traces
show that KaiS can successfully learn appropriate scheduling policies,
irrespective of request arrival patterns and system scales. Moreover, KaiS can
enhance the average system throughput rate by 14.3% while reducing scheduling
cost by 34.7% compared to baselines.
