Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Background job queues and priorities may be the wrong path

alexis.bernard.io

Post reply on HN
Print view View original

11–20 of 52 posts

Re: Background job queues and priorities may be the wrong path

#11

Post by jupp0r »

paulsutter wrote: post #8

If you want to write any complicated concurrent code, the simplest and best way is one long polling loop state machine. You might use a thread to call a blocking API, but the majority of the logic should be in a polling loop. I used to love chained callbacks when I was 16, and later I thought threads were the greatest, and I've written a bunch of device drivers that operate at different IPLs. But 20 years ago a cofou…

Ideally, you don't have blocking APIs at all. There isn't any reason nowadays. Every blocking API in your system is there for historic reasons (ie it's >20 years old) or because somebody made a terrible design decision in the last 20 years.

I am obviously referring to operations that do actual IO or wait for work on other threads only.

Re: Background job queues and priorities may be the wrong path

#12

Post by jph »

There are better ways to manage and measure queues, IMHO, by using basic queuing theory such as 'ρ' for utilization, 'ε' for error rate, 'Aθ' for activity step time, and Little's Law.

My queuing theory notes and notation are here:

https://github.com/joelparkerhenderson/queueing-theory

Re: Background job queues and priorities may be the wrong path

#13

Post by AlotOfReading »

The article is a bit unclear because it's lacking the proper vocabulary. Priorities and deadlines (what the article calls "SLOs") are both valid ways to approach scheduling problems with different tradeoffs.

The fixed priority systems the article talks about trade off optimal "capacity" utilization for understandable failure dynamics in the overcapacity case. When you're over capacity, the messages that don't go through are the messages with the lowest priority. It's a nice property and simple to implement.

What the article proposes is better known as deadline scheduling. That's also fine and widely used, but it has more complicated failure dynamics in the overcapacity case. If your problem domain doesn't have an inherent "priority" linked to the deadlines, that may be acceptable, but in other cases it may not be.

Neither is inherently better and there's other approaches with yet different tradeoffs.

Re: Background job queues and priorities may be the wrong path

#14

Post by taeric »

jupp0r wrote: post #11
paulsutter wrote: post #8

If you want to write any complicated concurrent code, the simplest and best way is one long polling loop state machine. You might use a thread to call a blocking API, but the majority of the logic should be in a polling loop. I used to love chained callbacks when I was 16, and later I thought threads were the greatest, and I've written a bunch of device drivers that operate at different IPLs. But 20 years ago a cofou…

Ideally, you don't have blocking APIs at all. There isn't any reason nowadays. Every blocking API in your system is there for historic reasons (ie it's >20 years old) or because somebody made a terrible design decision in the last 20 years. I am obviously referring to operations that do actual IO or wait for work on other threads only.

I don't know that I agree. Blocking logic is far easier to understand, as it lets you ignore partial operations. It also lets you specify, in a more direct manner, where data is buffered.

Re: Background job queues and priorities may be the wrong path

#15

Post by karmakaze »

AlotOfReading wrote: post #13

The article is a bit unclear because it's lacking the proper vocabulary. Priorities and deadlines (what the article calls "SLOs") are both valid ways to approach scheduling problems with different tradeoffs. The fixed priority systems the article talks about trade off optimal "capacity" utilization for understandable failure dynamics in the overcapacity case. When you're over capacity, the messages that don't go thro…

Yeah, I don't see how deadlines/SLOs does any better when there's insufficient capacity to meet those of queued jobs at their concurrency.

> I don’t think it’s possible to meet a latency target through prioritization when there is a fundamental lack of capacity.

This seemingly implies that it would be achievable with target deadlines/SLOs. At capacity I don't see a better solution than give each priority (or target latency) a defined minimum resource allocation.

Re: Background job queues and priorities may be the wrong path

#16

Post by Groxx »

># If workers are quiet, job1 will be run first in 10 minutes

># If workers are busy, job2 will be run first in 11 minutes

># If workers are too busy, both jobs will exceed their max latency.

So... priorities for tasks in a background queue.

I agree explicit latency tolerance is often a great way to do this - it lets you know what you can relax and reschedule, and if it's far enough in the future you can predict load / scale preemptively. Plus it works without having to deal with defining who gets what priority integer (or when to subdivide floats). But it degrades to the same behavior as priorities.

Re: Background job queues and priorities may be the wrong path

#17

Post by rewmie »

AlotOfReading wrote: post #13

The article is a bit unclear because it's lacking the proper vocabulary. Priorities and deadlines (what the article calls "SLOs") are both valid ways to approach scheduling problems with different tradeoffs. The fixed priority systems the article talks about trade off optimal "capacity" utilization for understandable failure dynamics in the overcapacity case. When you're over capacity, the messages that don't go thro…

Thanks for sharing some of your insight onto the problem domain. Do you happen to have any reference for laymen like me to onboard onto the subject? It's an awfully interesting topic but when I stumbled upon it I tend to fall back to JIT learning and troubleshooting, which is far from the best position to be.

Re: Background job queues and priorities may be the wrong path

#18

Post by hinkley »

AlotOfReading wrote: post #13

The article is a bit unclear because it's lacking the proper vocabulary. Priorities and deadlines (what the article calls "SLOs") are both valid ways to approach scheduling problems with different tradeoffs. The fixed priority systems the article talks about trade off optimal "capacity" utilization for understandable failure dynamics in the overcapacity case. When you're over capacity, the messages that don't go thro…

IN multitenant situations this is even more complicated. Because I may have a time slice of the machine I’m “entitled” to and within that I have priorities with which I want to allocate things. If one of my tasks can’t complete, I hope it’s to the benefit of another of my priorities. Not someone else’s.

I suspect you intimately need a little language for this. Decoding priorities for frames in a video stream are already complex and those are trivial compared to the sorts of scenarios Conway’s Las introduces.

Re: Background job queues and priorities may be the wrong path

#19

Post by svilen_dobrev »

ralferoo wrote: post #2

Just quickly skimmed this, but it seems the conclusion is wrong: A job needs two attributes to define when it should be started: run_at and max_latency. That means the job worker only needs to order them by run_at + max_latency, and takes the first. It seems both flexible and simple. Just considering two jobs (run_at=10,max_latency=15), (run_at=11,max_latency=13), it's clear that following that approach, the first ta…

i guess the messages should be sorted by that tuple (run_at, max_latency), and only if they miss the run_at, then run_at+max_latency comes into play. Or something even more twisted.

Re: Background job queues and priorities may be the wrong path

#20

Post by AlotOfReading »

rewmie wrote: post #17
AlotOfReading wrote: post #13

The article is a bit unclear because it's lacking the proper vocabulary. Priorities and deadlines (what the article calls "SLOs") are both valid ways to approach scheduling problems with different tradeoffs. The fixed priority systems the article talks about trade off optimal "capacity" utilization for understandable failure dynamics in the overcapacity case. When you're over capacity, the messages that don't go thro…

Thanks for sharing some of your insight onto the problem domain. Do you happen to have any reference for laymen like me to onboard onto the subject? It's an awfully interesting topic but when I stumbled upon it I tend to fall back to JIT learning and troubleshooting, which is far from the best position to be.

This is a class of problems known as scheduling. The Wikipedia page is a good place to start [0]. It focuses on task schedulers rather than message queues, but the same principles apply. For a deeper theoretical basis, Wiley has a good book [1]. Most undergrad curricula will have a module on this as well, so you can find info in most comp sci textbooks.

[0] https://en.m.wikipedia.org/wiki/Scheduling_(computing)

[1] https://onlinelibrary.wiley.com/doi/book/10.1002/97811189844...

Post reply on HN