First attempt at isolated transactions

Request For Comments
1

I pushed some changes that implement a first attempt at dealing with isolated transactions and snapshots. There are quite likely still issues with it, although it isn’t likely to break much as long as you do not use them. Possibly some performance degradation, but on my tests they seem neglectable. As SWI-Prolog follows the Release Early, Release Often model, it is time to share :slight_smile:

To play, just pull the git and build. I’ve tested the builds on multi and single threaded versions on Linux, MacOS and Windows (32 and 64 bits). Tests are in src/Tests/transactions/.

My questions are

  • Do you see potential in this and if so, what is lacking to make it really work for you?
  • Can we find programs where it badly affects performance? There is a little more synchronization in multiple threads performing assert/retract and the code skipping invisible clauses (due to the logical update view or isolated in a transaction) is a bit more complicated. Other than that, all works exactly the same and possible performance changes are just variations.

Below are the docs in their current state, copy-pasted from the HTML. You can also read them locally after installing using

?- help(transactions).

Enjoy --- Jan

4.13.1.1 Transactions

Traditionally, Prolog database updates add or remove individual clauses. The Logical Update View ensures that a goal that is started on a dynamic predicate does not see modifications due to assert/1 or retract/1 during its life time. See section 4.13.5. In a multi-threaded context this assumption still holds for individual predicates: concurrent modifications to a dynamic predicate are invisible.

Transactions allow running a goal in isolation . Database changes from other threads are invisible while changes inside the transaction are invisible to other threads and become atomically visible to other threads if the transaction is committed . Transactions have several benefits.

  • If a database update requires multiple assert/1 and/or retract/1 operations, a transaction ensure either all are executed or the database remains unchanged. Notably unexpected exceptions or failures cannot leave the database in an inconsistent state.
  • Other threads do not see the intermediate inconsistent states when performing a database update as above. Notably, this avoids the need for locking for a database update that updates a clause by retracting it and asserting a new one. For example, when using the code below to update temperature/1 , consumers of this fact do not need synchronization because temperature/1 is always present and always has exactly one clause.
update_temperature(Temp) :-
    transaction(( retractall(temperature(_)),
                  asserta(temperature(Temp)))).
  • Transactions allow for “what if’’ reasoning over the dynamic database. This is particularly useful when combined with the deductive database facilities provided by tabling (see section 7]).

SWI-Prolog transactions only affect the dynamic database. Static predicates are globally visible and shared at all times. In particular, transactions do not affect loading source files and thus, source files loaded inside a transaction (e.g., due to autoloading ) are immediately globally visible. This may pose problems if loading source files provide clauses for dynamic predicates.

transaction (:Goal)

Run Goal as once/1 in a transaction. This implies that access to dynamic predicates sees the dynamic predicates at the moment the transaction is started, together with the modifications issued by Goal. Thus, Goal does not see changes to dynamic predicates from other threads and other threads do not see modifications by Goal ( isolation ). If Goal succeeds, all modifications become atomically visible to the other threads. If Goal fails or raises an exception all local modifications are discarded and transaction/1 fails or passes the exception.

Currently the number of database changes inside a transaction (or snapshot, see snapshot/1) is limited to 2 ** 32 -1. If this limit is exceeded a representation_error(transaction_generations) exception is raised.

Transactions may be nested. The above mentioned limitation for the number of database changes applies to the combined number in nested transactions. A discarded nested transaction or snapshot resets the database counter for the outer transaction.

snapshot (:Goal)

Similar to transaction/1, but always discards the local modifications. In other words, snapshot/1 allows a thread to examine a frozen state of the dynamic predicates and/or make isolated modifications without affecting other threads and without making permanent changes to the database.

Issues The current implementation does not guard against multiple transactions performing conflicting database updates. For example, running the above update_temperature/1 concurrently may result in a situation where we have multiple clauses for temperature/1 . If two transactions run this at the same time, both will remove the existing clause and both will add a new clause. Currently the only way to gurantee consistency is by wrapping transactions that may perform conflicting updates using with_mutex/2. Future versions may provide database constraints to prevent a transaction from creating an inconsistent state.

Status SWI-Prolog transaction management is highly experimental. Interaction with other parts of the system such as the library library(persistency) , incremental tabling (section 7.7]), etc. still have to be settled. Future versions may also support non-determinism through transactions and snapshots. This is merely a first step to explore isolated changes to the dynamic predicate database.

7 Likes
3

I do not see the relevance. Re-formatted, this is

?- transaction(((foo(X), assertz(foo(X)), fail; true),
                (foo(X), assertz(foo(X)), fail; true))).

Both failure driven loops duplicate the foo/1 facts, so you end up with 4 times the number of facts you had before, just as you would have without transaction/1. This is true in general, transaction(Goal) has the same effect as once(Goal) if Goal succeeds, except that the intermediate states are not visible to other threads.

5

Yes. The docs say “sees the dynamic predicates at the moment the transaction is started, together with the modifications issued by Goal”

Is typically uploaded around 02:30 UTC. Seems you were earlier.

You’ll need some cooperation from the inside and outside. E.g., to preserve truth and only rollback on an exception, wrap the goal into a goal with an extra argument to tell true/false and catch on the outside of the transaction.

More serious is that transaction/1 acts as once/1. Often that seems a good idea as notably forever pending choice points easily lead to transactions that are never committed. I can imagine situations, notably for snapshots, that want to preserve non-determinism. As is, you can do that by encapsulating the snapshot in a thread and setting up nondet answer exchange using message queues. Possibly that is good enough.

7

That seems the perfectly fitting case. You just do all the work in your transaction and if you want to commit you succeed to end the transaction and else you fail (or throw a transaction).

Having snapshots (basically a database generation as a separate object is something I might consider at some point. It has the big disadvantage that the complex control flow of Prolog make it very easy to get into a situation with permanent forgotten snapshots that prevent (clause) garbage collection, dealing improperly with nesting, etc.

We’ll see where it goes. Getting isolation to work is a big gain. Real use cases will shape where it goes. That has always been how SWI-Prolog evolved.

8

Should these transactions be thought of the same as transactions in SQL databases?

Some descriptions of SQL database transactions that relate to what I think of as SQL database transactions:

TutorialsPoint
Wikipedia
c-sharpcorner

If so then will all the ACID rules apply? I take it that the answer is yes because the description notes

Transactions allow running a goal in isolation . Database changes from other threads are invisible while changes inside the transaction are invisible to other threads and become atomically visible to other threads if the transaction is committed .

I noticed that D for Durability is missing.

If so then I will use the Microsoft Northwind database which is like a Hello World! of SQL databases and has countless examples accessible via the Internet to do similar examples with SWI-Prolog. Also there is wide-world-importers which I just learned about and looks to have many transaction examples.

Related to this is the NoSQL database Neo4j from which I have learned a lot about SQL databases from their documentation, e.g.
Graph Databases for Beginners: ACID vs. BASE Explained
Neo4j’s Causal Clustering
Cypher transaction API

All of this could take some time so I will be stepping away from the Discourse self-hosting project while doing this. If these examples turn into something promising I will look at creating some Wiki topics for them. :grinning:

10

As is, no. ACID (atomicity, consistency, isolation, durability) (Wikipedia).

Right now, we have atomicy and isolation. durability refers to persistent store (I assume) and as this is pure in-memory, this can’t be provided. Possibly it can be linked to library(persistency) to achieve that. This would require a hook that can make the pending commit actions persistent. That will be added at some point.

consistency is now only resolved when you serialize possibly conflicting transactions using a lock. We probably do want to address this at some point. As yet, I do not know how. One of the things I’m considering is to associate constraints to the DB/a transaction and have a serialized area that consists of three steps

  • locked
    • Move the visibility to the current global state + local modifications
    • Run the constraints
    • On failure, discard
    • On success, commit

I think that is pretty simple to implement. Updating the visibility inside a transaction is nothing more than setting a new start generation value. Ideas are welcome. There is of course a lot of prior work in databases. Some of this probably applies, with or without some adjustment to make it fit Prolog.

My main current focus is to make the isolation work properly. It isolates fine, but its cooperation with clause garbage collection delays reclaiming clauses too much. If I can make that work fast we have a nice and clean alternative for the commonly seen

  • do a lot of computation using the dynamic database
  • clean the database.

That is than as simple as below, which also makes it thread-safe without the need to know which dynamic predicates it uses. This is less efficient than thread-local predicates though as we end up with a single clause list of which each thread (snapshot) sees as different subset.

 snapshot(compute).
1 Like
11

Thanks,

Your models of how SWI-Prolog works are so much more extensive than my mental models.

Does a graphic exist of all these parts?

I don’t want to branch off into another subtask, (go down the rabbit hole), to create the graphic so I will go back to the self-hosting project but will revisit this from time to time as using SWI-Prolog database with ACID could replace a major task of my much larger project. I am also considering TerminusDB for my much larger project. :grinning:

1 Like
12

No. I draw a lot of pictures while designing this kind of stuff, but they are really use-once. A couple of days later I often don’t even understand my own drawing :slight_smile:

2 Likes
13

I wish more people would start with pen an paper when problem solving!

A while ago I added TIFF as a format to Discourse that can be uploaded so that the hand drawn images could be scanned then uploaded e.g. in this post is PostScript Number and Name object Syntax Diagram.tif

For others: I am not encouraging users to start uploading TIFF images as we have storage constraints to contend with at present but for certain cases having the image outweighs using the storage space; when we move to self-hosing the storage space increases greatly. Also remember that when creating a TIFF image, options are usually available to create a black and white image which greatly reduces the byte size of the file and judicial use of other options when scanning will also reduce the file size.

If the image is useful we could always convert it to the DOT language and use GraphViz which is magnitudes of size smaller.

Donald Knuth (ref) and Edsger Wybe Dijkstra (ref) often scanned their notes and made them available.

16

Your isolation/1 is snapshot/1 (I thnk). transaction/1 is currently AI :slight_smile: , atomic and isolation. It will get C (consistency), for which I already suggested one idea. It will also get D (durable) as this means little more than a hook in the commit. It may turn into transaction/2 with a option list or possibly other higher argument versions. The similar rdf_transaction/1 has proven to be a simple and usable primitive.

I think AI is already a quite valuable addition. Even single threaded it simplifies consistent updates that need multiple assert/retract and simplifies temporary use of the dynamic DB for computing something. It allows the global state of multi-threaded applications to be always consistent (provided the application adds logic to ensure competing transactions do not violate constraints). With a global consistent state we can use snapshot/1 to have a thread providing consistent answers about this state.

3 Likes
18

The docs already say a transaction is not sufficient. In this particular case you can simply do this. Using this, all threads see exactly one clause for temperature/1 at any time. If this were a realistic domotica application there would probably be only one thread listening to the temperature sensor and we could do without the lock. The big pro remains: all the agents that need to use the temperature do not have to worry there is no temperature at some point or there may be two of them.

update_temperature(Temp) :-
    with_mutex(temp,
               transaction(( retractall(temperature(_)),
                             asserta(temperature(Temp))))).

Working on a real use case with CMU, we decided to add transaction(Goal, Constraint, Lock):

                                                    Availability: built-in

transaction(:Goal, :Constraint, +Mutex)
    Similar to transaction/1, but allows verifying Constraint during the
    commit phase. This predicate follows the steps below. Any failure or
    exception during this process discards the transaction  and releases
    Mutex  when  applicable.  Constraint may  modify the  database. Such
    modifications follow the semantics that apply for Goal.
      • Call once(Goal)
      • Lock Mutex
      • Change the visibility to the  current global  state combined
        with the changes made by Goal
      • Call once(Constraint)
      • Commit the changes
      • Unlock Mutex.

This deals with cases where Goal takes considerable time and conflicts are not common. It allows multiple threads to start their transaction. At the end, the Constraint and commit phase are locked and the Constraint shall only succeed if the database is consistent. This makes us ACI :slight_smile: .

In fact, it also allows for ACID as the constraint can be misused to make sure the changes are stored in a durable manner. There is transaction_updates/1 that allows the anything running inside the transaction to get a list of the updates a commit would do.

Note that the above also allows writing the temp example as below.

update_temperature(Temp) :-
    transaction(true,
                ( retractall(temperature(_),
                  asserta(temperature(Temp))),
                temp).
2 Likes
20

I tend to think of this as when two-phase commit is needed. Most the time you use transactions as a safe guard in case something fails. When working with database transactions I can’t recall a transaction ever failing in production on a single system. With messaging systems that do store and forward, they wrap the forward part in a transaction to ensure the message makes it to the next hop. When you have many systems connected doing this, then it was not uncommon to see the forward part fail but because it was wrapped in a transaction the store part was considered a safe state to fall back. In a period of time the forward would be attempted again and often succeed.

22

You do not seem to get the point of transactions :slight_smile: There are three major differences. (1) If anything goes wrong during the sequence of (related) database updates, transactions guarantee the partial update is discarded while with_mutex/2 leaves the database in an inconsistent state. (2) The reader also needs to use with_mutex/2, using the same mutex as otherwise the retractall/1 may have completed, but the asserta/1 is not yet done. For the transaction based version this is not needed. (3) writers and readers can progress with much less locking. Notably readers can use snapshot/1 to get a coherent database at any time without locking writers.

2 Likes
24

Logically, transaction/3 is not needed. It improves concurrency in the case we have a long running goal inside a transaction and a fairly cheap way to check that the updates inside the transaction do not conflict with the current global state.

This comes from a practical use case where concurrent transactions are used that perform what if reasoning. I.e., they change the database, use incremental tabling to explore the consequences and if these are satisfactory they can commit, unless some concurrent transaction has already created a conflicting state. The constraint is used to verify whether or not this is the case. As all this is very new, we are still in the explorative state :slight_smile:

The tests contain a pretty useless example, doing the retractall/assert as goal and a constraint that says there must be exactly one clause for the temperature. Now we have two threads setting the temperature in a loop to random values and a third reading the current temp in a loop and verifying there is exactly one temp. Unfortunately this test sometimes fails, so I need to do more debugging :frowning:

1 Like
26

In this case it is not the best wording. The logic of database changes and thread synchronization is, I guess, not that easy to describe. If we do

with_mutex(x, transaction(Goal))

and Goal is designed such that it brings the database from one valid state to the next we have a globally observable database that atomically jumps from one valid state to the next. That is nice and fairly simple. The downside is that there is no concurrency, which is fine if Goal is a mere series of assert/retract operations, but not so fine if Goal is slow.
So, transaction/3 runs Goal concurrently in each thread doing the transaction. It then guarantees that if Constraint only succeeds if the database is in valid state at the end of the Constraint, the globally visible state is always valid. Note that Constraint sees the database in the state it will be after the commit.

An yes, you can do what-if reasoning without transactions, but transactions make it a lot easier.

29

You can get this working. For this simple case it won’t be better than just a lock around the transaction, but this is what I would do:

increment_counter(Delta) :-
    transaction(( retract(counter(Value)),
                  Value2 is Value+Delta,
                ),
                ( counter(Value),
                  asserta(counter(Value2))
                ),
                counter_lock).

This is close to the compare-and-swap technique used for lock-free programming: optimistically prepare a new value and at the end replace the old value if the value has not been changed. You can also swap this around. Both assume there is always just a single counter/1 clause (and maintain this invariant). I think this is a little more elegant as it is closer to the compare-and-swap and because a possible conflict causes an empty rollback.

increment_counter(Delta) :-
    transaction(( counter(Value),
                  Value2 is Value+Delta,
                ),
                ( retract(counter(Value)),
                  asserta(counter(Value2))
                ),
                counter_lock).

Needless to say, this only makes sense if the Goal (first arg) is a more expensive computation and conflicts are relatively rare. This is a quite nice example of one way to use transaction/3 though :slight_smile: I think I’ll add it to the manual.

1 Like
31

I understand this is just an example, but if it is just a counter, wouldn’t you simply use nb_setval/2?

32

It must be shared between threads. Good old flag/3 is a way simpler to share a counter between threads though. So yes, this is really about more complex operations that simple counters (or setting the temperature).

33

Yes. In a CAS like design it is not always the case that you need to retry though. For a counter, yes.

There are three steps involved in the final locked update: (1) sync the view with the global state, (2) running the constraint and (3) commit the changes. I do now have a rather nasty test, notably to verify that the globally visible world is consistent with what the constraint verifies at all time. Took some time to get the generation updates correctly ordered to make this work :frowning:

1 Like
34

FYI

In reading up on Sidekiq which is Simple, efficient background processing for Ruby or in other words runs a few to thousands of background jobs per second and uses threading, here it notes that

autoloading and eager loading is a frequent cause of problems

Not expecting a reply but something that might be of value if the same occurs with Prolog code and should be noted in documentation if needed.