Designing a Query Queue for ScyllaDB by Avi Kivity

Database queries vary widely—from milliseconds to hours. Optimizing concurrency is a delicate balance of CPU, memory, and stability. Bad design can lead to high latency or crashes. Join us to learn how we designed ScyllaDB's query queue to handle these challenges. #Database #ScyllaDB

1. A ScyllaDB Community
Avi Kivity
CTO & Co-founder
Designing a Query Queue
for ScyllaDB

2. Avi Kivity

CTO at ScyllaDB
■Linux KVM, Seastar, ScyllaDB

3. Typical queue presentation
●SPSC/MPSC Queue
●1 instruction/queue, 2 instructions/dequeue
●No lock!
●Tricky code involving memory barriers
●Test on 435 core machine @ 331,442,336 ops/sec

4. This is not that presentation!
SPSC queue (and similar)
●Tiny amounts of memory per item
●Fixed size, regular
●Few instructions
●Millions ops+/sec
●CPU only
This queue
●Megabytes (potentially) per item
●Variable size
●Millions of instructions
●10k ops/sec/vcpu
●CPU + I/O

5. About ScyllaDB
●Horizontally and vertically scalable NoSQL database
○Horizontally = just add nodes
○Vertically = happy to use fat nodes
●Using the thread-per-core Seastar framework
●Cassandra, DynamoDB compatible

6. ScyllaDB read path overview
Coordinator
Replica
Coordinator
Replica
Coordinator
Replica
Coordinator
Replica
Coordinator
Replica
Coordinator
Replica
Client request (“SELECT”)
●Coordinator selects replicas that own the data
●Issues reads to replicas, merges responses

7. Replica-side read features
●Variable response size
○One 100-byte row
○100 10kB rows
○Zero rows
●Variable effort
○Lookup cache, return row
○Merge data from memtable and 8 sstables
■Many megabytes of parallel and sequential I/O
●Variable timeout
●Variable importance to end-user
●Queries can pause and restart (“paging”)

8. Why queue?
Hypothesis: let requests execute as they arrive
●Simple
●No time lost waiting in queue
Problems
●Queries use too much memory, going
out-of-memory (OOM)
●Queries compete against each other
○Everyone loses
○Queries time out during execution
○Partial work is thrown away
RPC
Query 1
Query 2
Query 3
Query 4
Query 5

9. Simple, no concurrency queue
●One (at most) executing query
●The rest wait
●Advantages
○Won’t OOM
○Minimal latency for executing query
○Queries in queue can be timed out before
starting execution
●Disadvantages
○Disk underutilized
○CPU unused while waiting for disk
RPC
Query 1
Query 2
Query 3
Query 4
Query 5
Queue Execution

10. Count limits
Allow 100 queries to execute, the rest wait

Advantages
●Saturate CPU, disk
Disadvantages
●Queries use too much memory, going
out-of-memory (OOM)
●Queries compete against each other


RPC
Query 1
Query 2
Query 3
Query 4
Query 5
Queue Execution

11. Memory accounting
Account for every byte used in query
●Disk DMA buffers allocated and deallocated
●Temporary structures used for holding query rows
Queue issues queries for execution only if memory is available
●Memory can grow past the limit as the query executes

12. Query caching
SELECT * FROM my_table
●Coordinator assigns each query an ID
●When a query completes a page, store state in a cache
●When the next page is requested, pull state from cache
●Cache has its own memory and count limits
●Avoids per-page index lookup
●Reuses disk buffers and query state

13. Out-of-memory killer
Memory accounting is great, but still unbounded
●Add OOM killer
○On threshold 1, stop issuing new queries
○On threshold 2, kill all queries but one
■Allow the user to see slow progress
○On threshold 3, kill everything
■Protect the database
●Rarely triggered

14. Disks vs vCPUs
vCPUS
●Only process one thing at a time
●Add more things
○Latency increases
○Throughput decreases slightly
Disks
●Process many things at a time
●Add more things
○Latency increases slightly
○Throughput increases
○(up to a point)

15. CPU accounting
Reducing query competition
●One queue per vCPU
●Query graph is parallelized
○Count how many leaves are blocked on I/O
○(Each leaf = a disk or memory read)
○If all - issue one more query
●Serializes cache-only queries
●Stops issuing queries when CPU bound
●Allows concurrency when I/O bound
Advantages
●More queries can be timed out while queued
●Early queries get lower latency

16. What about I/O?
I/O scheduling is delegated to the Seastar I/O scheduler

17. Re-introducing parallelism
Not all queries are equally important to
the user
●Solution: one queue per session
○Each with its own memory reserve
○Queries from different queues compete
○Queues serialize (when possible) own
queries
○Seastar CPU and I/O schedulers assign
resources according to priority

DB
OLTP OLAP

18. Gotchas
■Can have a single query page
consume large amounts of CPU
■Stalls all queries behind
■Solution: introduce user
override for CPU concurrency

19. Conclusions
●Database query queues are complicated
●High-performance queue, yet focused on “administrative” tasks
●Years of effort
●Journey is never complete, but can reach asymptotically

20. Thank you! Let’s connect.
Avi Kivity
[email protected]
@AviKivity