Wait on database changes

Following up on the remarks below

I think it is wise to consider Qu-Prolog’s wait mechanism on database changes. Found some docs on http://staff.itee.uq.edu.au/pjr/HomePages/QPFiles/SEC3.html, search for thread_wait. Being able to wait for the database has some nice properties as it allows something (typically one or more threads) to update the world view while other threads act as agents, drawing conclusions and taking actions. Current SWI-Prolog isn’t very good at that. Qu-Prolog was built for that.

Acting on the dynamic database notably fits well with the recent incremental tabling and monotonic tabling additions.

First I found an older version of the docs discussing thread_wait/0,1. I think that comes from the days that Qu-Prolog used cooperative threading as it cannot work using preemptive threading as the condition may be fulfilled between deciding it is not fulfilled and waiting. They added thread_wait_on_goal/1,2 which moves the goal to test whether or not to wait inside the predicate, so the whole thing nicely maps to POSIX condition variables and is reliable.

I think the spec is pretty much ok. I’m planning change wait_for(Secs) to be compatible with SWI-'s related predicates that accept timeout(Stamp) and deadline(Secs) and add an option to wait for a module as that seems an attractive simplification between waiting for any dynamic predicate and a list of specific ones.

3 Likes

These things seem to be a little distinct. Web Prolog (AFAIK) relies on the mailbox (=~ message queue) idea. Qu-Prolog assumes there is state (about the world) in dynamic predicates that trigger actions. I was never that interested in this view, but notably the (incremental) tabling work turn this into a more viable idea.

As far as I can tell, the Qu-Prolog idea to associate predicates with the waiting is merely a trick to avoid re-evaluating the goal too often. I.e., you tell the system it only makes sense to re-evaluate the goal if one of the given predicates changed. The default is to trigger on any change to the DB. That can get really costly if we have some piece of the application using the dynamic DB to perform some computation that is completely unrelated.

Pushed some patches that add thread_wait_on_goal/2. If you want to play with it, get the GIT version. For the docs, run

?- help(thread_wait_on_goal).
1 Like

I don’t understand what you mean with a critical action. This stuff basically implements a broadcasted POSIX conditional variable. The waiter grabs a lock, evaluates the condition (calls the goal) and if false waits on the condition variable. The wait unlocks the lock and waits (atomically). The thread changing the database grabs the same lock, checks whether some thread(s) are waiting, verifies they may be waiting for this predicate and if so broadcast the condition variable and unlocks.

That is all pretty much how it should work for POSIX condition variables.

You can in theory call your critical stuff in the Goal of thread_wait_on_goal/2. That does what you describe, but as as have a single monitor for the database this would be rather inconvenient, notably as any database operation in another thread will be blocked.

At least in theory, we could have a per-module monitor when we are waiting for a module. It might make sense to drop the entire idea of a central database lock and do the whole thing only per module. A quick search suggests Qu-Prolog doesn’t have modules.

Need to think a little, but that might make a lot of sense. Watching the entire db is already discouraged as it can easily lead to huge performance issues if some threads decides to use a dynamic predicate as working memory for some computation.

This would need to handle the possibility that one module is the “manager” of the dynamic predicates in another module. This is useful for systems where a “world” is created and managed by an “overseer” module which is responsible of managing the creation/unloading of other modules and their dynamic predicates.

Not sure I get that. It basically defines what should happen on changes to the dynamic predicates inside a module. A module can manage its own dynamic predicates this way or the dynamic predicates of some other module. Instead of merely listening to the database, we might want to add a trigger that is not related to the database, mapping to condition variable signal and broadcast.

Not completely sure, but getting rid of the database as a whole seems a good step. We have modules for a reason :slight_smile:

I guess you mean threaded_wait/1? Checking the implementation, this maps pretty much directly to thread_get_message/2, where an involved object seems to have its own message queue.

This, according to the docs, does

Call Goal with multi-threading turned off. Multi-threading is turned back on when Goal exits (either by success or failure). This predicate has the effect of making Goal atomic with respect to multi-threading.
mode thread_atomic_goal(+term)

This is pretty much not what you want in a multi-threaded environment and probably remains from the days Qu-Prolog did do cooperative multi threading (or it still does, I do not know). Using true preemptive multi threading this is very undesirable and extremely hard to implement. So hard that it caused me, Matt and Keri to change the global garbage collectors to avoid the need for thread-atomic garbage collection (which made predictability of response times a lot better).

We have with_mutex/2 for that, but unlike a general thread_atomic/1, this must be used to synchronize access to a specific shared data structure. I don’t want that either :slight_smile:

I tend to agree on that. On the other hand, I think it is ok if the low level primitives have long names. Libraries can provide comfortable high level primitives on top of that. Nobody should be using much of this stuff directly in application code.

I see, it makes sense.

This sounds good, and I guess it may improve performance in parallel systems.

Pushed a patch that makes the thread_wait_on_goal/2 module-specific. The main advantages are that using it in one place of your application doesn’t cause extra synchronization throughout the application. It also allows for Goal to do more involved things without blocking database operations in the entire system.

Some more thinking tells me we also need a predicate with the tentative name

 thread_update(:Goal)

This should grab the module mutex, execute goal, broadcast the module CV and unlock the mutex. That allows us to perform multiple (or even no) updates to the database that are related and only wakes up the waiting threads after we are done.

The result would be a (I hope) clean encapsulation of the POSIX condition variables at the level of a module. That can deal with a fundamental design the current system can not: have an unknown set of agents modeled as threads independently act on an changing world represented in the Prolog DB.

Now we may need to finalize the names …

Remember that AFIAK, originally Qu-Prolog performed cooperative multi-threading. That is also why they had a simple thread_wait/1. Using preemptive multi-threading this all stops working. hread_atomic_goal/2 is simply with_mutex/2. Nope, and that is just a (recursive) mutex.

The design pattern for a condition variable includes a mutex and shared data. A module seems the obvious holder for all that. We lazily attach the mutex and CV when the wait/update stuff is used and dynamic predicates in the module provide the necessary shared data. The whole thing has very few implications and is pretty flexible. It even allows you to re-implement message queues with as many features as you want. Might be interesting for Web Prolog where the message queues were not a very good match if I recall well.

That’s great

I think this would be great to replace all those with_mutex(...retract...assert)

Not really. It replaces it with thread_update(…assert…retract) and only allows some other thread to wait on this to happen. Transactions are the way to get cleanly rid of the mutex and reduce the time thread_update/1 needs to hold it to the transaction commit.

1 Like

threaded_wait/1 on a list simply is a loop over the elements of the list if you look at the source. So yes, it cannot do what you want it to do. You could achieve that as you describe using with_mutex/2 around it (and make sure any operation on this queue uses the same mutex). I think queue, as is, are not well suited for this task.

The new stuff should allow storing the queues objects in a smarter way and do what you want in a much more scalable way.

Engines are another sensible way to implement a more feature rich queue as it allows storing the queued objects in a normal Prolog data structure.

I think threaded_wait(List) is broken at the moment multiple threads perform such waits. Even properly implemented, the concept easily leads to deadlocks.

I have now renamed thread_wait_on_goal/2 to simply thread_wait/2 and added thread_update/1. I think that finished round one for this interface.

thread_update/2 has an option to control this. The default is to wake all waiting threads (broadcast as POSIX calls it).

As a module now bundles the data, CV and lock, you can only handle them as a triple. You can of course have multiple modules. Multiple condition variables can do nothing new as you can do the same adding some data that tells the waiting threads what to look for. Multiple condition variables can only avoid unnecessary wakeup. We already have additional conditions for the wakeup to only watch certain predicates and either watch any modification or only assert or only retract. That still may lead to more than necessary wakeups, but we should be able to reduce this further given the current interface.

Possibly, but I’d rather go for transactions. These allow for concurrent read with an ongoing update without the need for locks. Still, lock based updating of a shared database is a can of worms. It will probably be needed for some specific cases, but I rather invest time in stuff that reduces the need for locks.

I don’t really see the simpler. Compared to below. As we do not need multiple asserts/retract to update the DB, we do not even need thread_update/2.

:- dynamic queue/1.

dequeue(M) :-
    thread_wait(retract(queue(M)), []).
enqueue(M) :-
    assertz(queue(M)).

Even with thread_update/1, I don’t consider this more complicated. You’ll need more stuff if you want to include timeouts. Just a wait/2 with a timeout doesn’t do as this may be restarted, so you need a absolute time deadline that you need to compute before.

In the end, both your monitors and thread_wait are an encapsulation of POSIX condition variables (or Java monitors, but I suspect these are in the end also POSIX condition variables when I consider the behavior you claim). I do not see anything you can do with one encapsulation and not with the other. Possibly I missed something. The difference in the implementation work is also minimal as we always need a lock and a condition variable, Connecting it to a module that also encapsulates the related data has some appeal to me.

I still don’t see the (fundamental) difference :slight_smile:

No need to guess, just look at the source. No need for a release, just build it from git or, as you mostly seem to be using Windows, just download the daily build from https://www.swi-prolog.org/download/daily/bin/

I haven’t been following this discussion in detail, so perhaps this is a stupid question …

Does the wait mechanism depend on the locking mechanism for assert/retract? In particular, PostgreSQL or BigTable (and I’m guessing Apache HBase) don’t delete or update rows; instead they mark them as deleted or replaced (and coalesce the changes from time to time). The up-side is that reads don’t need to lock; the down-side is that reads may need to scan for updates. If the database uses such a design, would the “wait on change” mechanism work the same way as if the the changes were made directly?