Graph Structured Prioritized Task Queues
Written by: Dewire Labs Team
September 11, 2016
In the area of provisioning and task processing, queues are ubiquitous for handling system tasks. Task queues come in many shapes and sizes but more often than not their feature set is lacking when business processes impose complex requirements. At Dewire we often implement our own task queues and implement the feature set required by the particular system.
We have identified that our system always has internal sub domains within which all processing is order independent on other sub domains. The sub domain is identified as an organization. Our present queue implementations always honor this fact and enable us to handle an arbitrary set of queues, one for each organization, without implementation complexity or performance implications.
One implication of this model is user experience. When an organization has many users performing many tasks, the queue for that organization will grow and the user will experience delays before their commands are executed. This implies that we need to take the queue structure at least one step further.
We need to identify tasks that can be processed in parallel. Such a task might be a user changing its presence status. This task does not need to depend on other similar tasks but might depend on global tasks such as manipulating user groups. Group manipulating is rare and has little impact on queue size but status changing is common and has a large impact on queue size.
Furthermore, the task queue system must support such prioritization. We envision a tree-structured queue where subtrees depend on other subtrees. This way parallel processing can be enabled when there are no waiting tasks in the common roots of subtrees. The task selection process is subject to a few basic requirements and the theoretical model and implemented data structure must support those requirements to fulfill the business process needs.
The initial scope of the thesis includes work for one student. The scope can be extended by including more theoretical aspects like per-task dependencies or practical like queue management and visualization.
- Propose a theoretical model that can be proven to fulfill the requirements of the task selection.
- An implementation should be presented and a proposal on how to integrate the process into existing task queues.
- The implementation should be tested to fulfill functional requirements and a performance - tests in regard to both load and throughput should be performed.