queue: support priority queue

[glorv]

this PR introduces a new type of queue: priority queue. The priority queue sorts task by their priority value that can allow inserting tasks in the front or middle, so we can support a more flexible schedule policy.

Why Priority

The default multi-level queue is suitable for most FIFO scenarios. But in cases that need more fine-grained control of the task schedule order, FIFO is not good enough. For example, in a shared environment for multiple users, the scheduler should schedule tasks from different users according to their share. In this case, a priority-based scheduler based on the total execution time by the user may be a workable solution.

Drawbacks

The priority queue is not perfect for all cases. The scheduling overhead is a little bigger than the multi-level queue. And there is no default implementation that is suitable for common cases. The schedule also doesn't implement the multi-level strategy that automatically degrades slow tasks.

Implement detail

The priority queue is backed by crossbeam-skiplist, the key is the priority value and the value is the task. The implementation attaches the key with an extra auto-incremented sequence number to ensure the key never duplicate with each other.

The user should provide an implementation of the trait TaskPriorityPriovider to generate the priority value of each task.

Benchmark Result

I test the priority queue performance by comparing the overall performance of tidb cluster with sysbench oltp_read_only and select_random_ranges workload.
In this brief benchmark, the priority scheduler implements the mclock algorithm to support fair scheduling among multi resource groups. Becuase by default there is only one resource group, so it can be treat as a FIFO queue. The priority test code is: https://github.com/glorv/tikv/tree/qos-http and the nightly code is commit 2704588c6aaa1a269bb91499229e358d23cc636b.

The benchmark is running on 3 8core tikv and 6 8 core tidb so tikv should be the performance bottleneck. Result:

(the first is priority queue and second is yatp multi-level queue)

The benchmark shows that the overhead of priority-queue is bigger than multi-level queue. The performance drops about 5% in oltp_read_only and 1% in select_random_ranges.

[glorv]

@Connor1996 @sticnarf @BusyJay PTAL

[BusyJay]

Can you highlight the cases that priority queue solves better than multi level queue? And what's the drawbacks of priority queue?

[glorv]

Can you highlight the cases that priority queue solves better than multi level queue? And what's the drawbacks of priority queue?

@BusyJay I have changed the description, PTAL again, thanks

[glorv]

@Connor1996 @sticnarf PTAL, thanks

[glorv]

@BusyJay @Connor1996 @nolouch PTAL again, thank you very much.

[BornChanger]

/test-address-sanitizer-ubuntu-latest-nightly

[glorv]

@BusyJay PTAL again

[glorv]

The failed case is caused by the extra check by Miri, and is fixed by this PR https://github.com/crossbeam-rs/crossbeam/pull/940. Since it doesn't affect correctness, we can fix in the next release version of crossbeam-skiplist.

[glorv]

The failed case is caused by the extra check by Miri, and is fixed by this PR crossbeam-rs/crossbeam#940. Since it doesn't affect correctness, we can fix in the next release version of crossbeam-skiplist.

crossbeam-skip already released v0.1.1 which included the fixed PR, so we can just rerun the failed case.