Abstract:
Increasingly large graph processing applications adopt the approach of partitioning and
then distributed processing. However, maintaining guaranteed Service Level
Agreement (SLA) on distributed graph processing for concurrent query execution is
challenging because graph processing by nature is an unbalanced problem. We
investigate on maintaining predefined service level agreements for commonly found
graph processing workload mixtures. We develop a Graph Query Scheduler
Mechanism (GQSM) which maintains a guaranteed service level agreement in terms
of overall latency.
The proposed GQSM model is implemented using the queueing theory. Main
component of GQSM is a job scheduler which is responsible for listening to an
incoming job queue and scheduling the jobs received. The proposed model has a
calibration phase where the Service Level Agreement data, load average curve data,
and maximum load average which can be handled by the hosts participating in the
cluster without violating SLA is captured for the graphs in the system. After
completing the calibration phase the job scheduler is capable of predicting the load
average curve for the incoming job requests. The scheduler checks whether the
maximum load average extracted from the predicted load average curve exceeds the
load average threshold values captured in the calibration phase. Based on the result the
job scheduler accepts or rejects the job requests received.
Results show that SLA is successfully maintained when the total number of users is
less than 6 in a JasmineGraph cluster deployed in a single host. For distributed clusters
the number of users can go up to 10 without violating SLA. The proposed model is
scalable and it can be applied to a distributed environment as well.
As future work, the proposed model can be extended to work with less initial
calibration steps and the scheduling algorithm can be improved with intelligent
workload management among hosts for more efficient resource consumption.
Citation:
Weerakkody, W.A.C.R.. (2022). Guaranteeing service lavel agreements for triangle counting via observation - based admission control algorithm [Master's theses, University of Moratuwa]. Institutional Repository University of Moratuwa. http://dl.lib.uom.lk/handle/123/21585