I think it's a good quality of life improvement to Redis.

@oranagra Pinging you since I would like your buy in before Jim does any more work. The current PR just includes the high level APIs, but the intention is to use this functionality to replace the bio.c functionality. I couldn't immediately think of other places the FIFO might be used, but I still think it's useful enough to include. The goal would be to include the refactoring after we stabilize 7.2 and target it for Redis 8. Note this will eventually be a major decision since we will want to allow configuring a custom number of threads.

Not a full review. This looks like two good ideas!

Thanks Viktor @zuiderkwast

If BJM replaces BIO, I'd prefer that BIO is deleted at the same time so we don't have several ways of doing the same thing.

Absolutely. I just want a go/no-go decision before I put in the work to remove BIO. But that's definitely my intent.

Regarding the included fifo datastructure, can it replace adlist in more places, perhaps all occurrences throughout the repo? If yes, we can delete adlist too. If not, perhaps it can be beneficial to replace a few usages. AFACT, this fifo data structure can easily be made to support the operations of a double-ended queue, i.e. push and pop in both ends.

I have some FIFO use cases in local code, but I'm not sure that this is applicable in too many places for OSS Redis. This is a very efficient FIFO queue, but it has limitations for other uses. Namely:

• It's singly-linked. This saves space. Adding a reverse pointer would increase memory overhead by ~134%. Since it's singly-linked, pops off the rear aren't possible.
• There's no mechanism to remove items from the middle of the list other than an O(n) search. There's no way to address an item other than it's value. The physical location of an item can change.

@JimB123

This is a very efficient FIFO queue, but it has limitations for other uses. Namely:

• It's singly-linked. This saves space. Adding a reverse pointer would increase memory overhead by ~134%. Since it's singly-linked, pops off the rear aren't possible.

Right, I didn't think about that. We can't have pop_back but it'd be possible to add a push_front in O(1) if that's useful in any case.

• There's no mechanism to remove items from the middle of the list other than an O(n) search.

True, but many of the adlist operations are O(n) too so it doesn't mean it's a regression. But it's cleaner to refuse to add O(n) operations altogether. :)

@zuiderkwast

... but it'd be possible to add a push_front in O(1) if that's useful in any case.

I just added a fifoPushFront in my local branch. Will include with final delivery.

sorry for joining late, too busy elsewhere.
before diving into the code, which i assume is very neat, i'd like to challenge the reasoning that was mentioned (other than a cleanup of ugly code).

first, doing more background jobs in parallel, isn't necessarily desired, examples:

1. freeing expires and db dict in parallel means more contention on the allocator arena locks.
2. for WAITAOF, we recently added some ordering requirements, two jobs of different types designated to the same thread so that we are sure they're not executed out of order.

secondly, the description says it's more memory efficient, but do we really care? AFAIK we don't usually have a long list of tasks in that queue. maybe more important is the insertion and deletion overhead (allocation / deallocation), and the locking (maybe a lockless queue can be beneficial)

@oranagra You are correct that the primary motivation is code cleanup. BJM provides a reusable interface - as opposed to BIO which has a hard-coded interface change for every type of background operation. BJM corrects the layering issues and introduces modularity of design.

Side-node: as evidence of the layering/modularity improvement, 10 functions have been removed from server.h, either becoming local (static) functions or being eliminated completely.

1. freeing expires and db dict in parallel means more contention on the allocator arena locks.

Yes, that's possible/probable. However I did some testing and do see an overall improvement in time. Note that the expires dictionary is actually pretty trivial and doesn't contribute a lot to the operation.

2. for WAITAOF, we recently added some ordering requirements, two jobs of different types designated to the same thread so that we are sure they're not executed out of order.

I'd suggest that this isn't the best model. Enforcing an ordering on fire-and-forget background tasks shouldn't be necessary. For the case mentioned, with 2 tasks, this is easily accomplished with a single callback which performs the events serially. Alternatively, the initial task could initiate (queue) the 2nd task before completion.

secondly, the description says it's more memory efficient, but do we really care?

Again, you are correct. The background queue usually has a very limited list of items (typically 1 or 0). Unless something weird is happening, memory should not be a concern.

I mentioned performance and memory as side-benefits, mostly as an indication that this change shouldn't degrade performance or memory usage.

For a queuing use case, the Fifo queue is much more memory efficient and faster than using list. While it won't make much of a difference here, I suspect there are additional use cases where this data structure will be handy. (I have some local use cases.)

Integration complete. Changes visible now.

• BJM replaces BIO providing better modularity and reusability
• LazyFree has been refactored for better modularity and reusability
• All code referencing BIO or LazyFree has been updated

I'd suggest that this isn't the best model. Enforcing an ordering on fire-and-forget background tasks shouldn't be necessary. For the case mentioned, with 2 tasks, this is easily accomplished with a single callback which performs the events serially. Alternatively, the initial task could initiate (queue) the 2nd task before completion.

IIRC it's not two tasks that can be replaced with a single callback that performs both since the tasks are not started together.
IIRC it's an fsync and close tasks, each also updating the global synced replication offset, and if they're executed out of order then the one scheduled earlier can override the fsynced replication offset already updated (setting it to a lower value).

@slavak correct me if i'm wrong, and if you have time, take a look at the changes in this PR.

I like the idea, I proposed a refactor in #11713 (comment) before, while the current way is too coupled. In my imagination something like thread pool(exactly the BJM here) substitutes the BIO, somehow instead of the fire-and-forget interface, I assume a future based implementation, which can impose the order between jobs, or wait for a specific job.

future f = submit(task); // run task asynchronously
future f2 = submit_then(f, task2); // run task2 after task is done
f2.get(); // wait for the finish of task2

For the case mentioned, with 2 tasks, this is easily accomplished with a single callback which performs the events serially. Alternatively, the initial task could initiate (queue) the 2nd task before completion.

It requires task1 knows about task2, or callback knows task1 and task2 both. However the task is dynamic so many cases may occurs:

1. task1 is running, and task2 is issued
2. task1 is done, and then task2 is issued
3. task1, task2, task3... is issued

IIRC it's not two tasks that can be replaced with a single callback that performs both since the tasks are not started together.
IIRC it's an fsync and close tasks, each also updating the global synced replication offset, and if they're executed out of order then the one scheduled earlier can override the fsynced replication offset already updated (setting it to a lower value)

Reviewed the WAITAOF code, I also suppose it's the race condition that slavak wanna forbid. I find another way to solve it without making the task in order. When updating the fsynced replication offset in bio, we can compare the to-be-fsynced offset and currently fsynced offset, skip the set if the set would rollback the offset, otherwise CAS the fsynced offset to the new one, so simply fire-and-forget model works well.

@oranagra is correct about the WAITAOF ordering requirements. In fact, the requirement goes both ways:

Suppose we have task f which fsyncs and updates the fsynced offset to a, and task g which fsyncs and updates the offset to b, where a < b.

1. If g gets executed before f, we don't want f to overwrite the offset value b with the smaller a.
2. In specific cases (IIRC- during AOF rewrite), executing g may not guarantee all data up to that point has been actually fsynced until f is also executed, so setting the offset to b may actually provide invalid durability guarantees.

(1) can be resolved with a CAS that takes the maximum of the two values. (2) was the main reason we chose to enforce ordering on the tasks. I think eliminating the requirement for task ordering will be quite difficult.

I think eliminating the requirement for task ordering will be quite difficult.

So, maybe the best option is to keep BIO for it's original purpose (I/O) - leave it for the AOF single-queue case, but strip out other use cases?

Alternatively, BJM could add an additional thread which is dedicated to sequential jobs. We could have something like submitSequential which ensures FIFO ordering to a single thread.

I think eliminating the requirement for task ordering will be quite difficult.

So, maybe the best option is to keep BIO for it's original purpose (I/O) - leave it for the AOF single-queue case, but strip out other use cases?

Alternatively, BJM could add an additional thread which is dedicated to sequential jobs. We could have something like submitSequential which ensures FIFO ordering to a single thread.

How about my future based proposal? In contrast to fire-and-forget, every submission will return a stub, so we can query the task completion by the stub, or submit new task in respect of dependencies. For example

future f1 = submit(task1)
future f2 = submit_with_dependency(task2, f1)
// if we wanna know if task2 completes
status = query_task(f2)

which makes task1 and task2 in sync. I have a rough draft of it(though not implement it yet), if you have interest I'd like implement it.

How about my future based proposal? In contrast to fire-and-forget, every submission will return a stub, so we can query the task completion by the stub, or submit new task in respect of dependencies. For example

I like the futures idea. It could be called on the event loop, such that when the background operation is done it will invoke a callback from the eventloop.

How about my future based proposal? In contrast to fire-and-forget, every submission will return a stub, so we can query the task completion by the stub, or submit new task in respect of dependencies. For example

I like the futures idea. It could be called on the event loop, such that when the background operation is done it will invoke a callback from the eventloop.

Certainly possible. But greatly increases the overhead. This would require:

• Returning data from the background thread to foreground thread via mutex queue (or similar)
• Invoking callbacks via timer(?) task on the event loop
• Additional memory to pass callback info to the background thread - and then return it to foreground thread

In most cases, the future capability would not be needed. We could make the "future" part optional, only incurring the overhead when something more than fire-and-forget is needed. However, if it's going to be optional, maybe we want to implement without the future capability and then later implementing that as an extension.

In most cases, the future capability would not be needed. We could make the "future" part optional, only incurring the overhead when something more than fire-and-forget is needed. However, if it's going to be optional, maybe we want to implement without the future capability and then later implementing that as an extension.

I agree with this.

However, if it's going to be optional, maybe we want to implement without the future capability and then later implementing that as an extension

doesn't that mean merge a PR that introduces a bug into redis?
i.e. causes WAITAOF to be unsafe?

doesn't that mean merge a PR that introduces a bug into redis?

I don't know if this was specifically targeting to be the solution to WAITAOF. We definitely need to resolve the WAITAOF issue before merging.

Thank you for your submission! We really appreciate it. Like many open source projects, we ask that you sign our Contributor License Agreement before we can accept your contribution.
_{You have signed the CLA already but the status is still pending? Let us recheck it.}

@JimB123 When you get a chance, move this PR to https://github.com/placeholderkv/placeholderkv