Is there any algorithm for R / W blocking charts?
Suppose we have resources A, B, C and their dependencies are not cyclical :
B->A C->A
The values of B are highly dependent on A and C being highly dependent on A. For example: B, C are pre-computed resources from A. So if A update, B, C needs to be updated as well. But if B is updated, nothing changes except B.
And for the problem: given the fact that each node of the chart can be accessed to Read or Write or Read / Update before writing in multithreaded mode, how can locks be managed on such a chart? Is there a generalization of this problem?
Update
Sorry for the confusing question. It's also very important here: If, for example, A modifies and forces B, C to update, it means that moment B and their dependencies are updated - it will release the write lock.
source to share
Your question is a combination of transaction - locking - concurrency - conflict resolution. Therefore, the models used in relational databases can serve your purpose.
There are many methods defined for concurrency control .
In your case, some may apply depending on how optimistic or pessimistic your algorithm is, how much it reads or writes, and how much data per transaction.
I can think of two methods that might help in your case:
1. Strict two-phase blocking (SSPL or S2PL)
It begins a transaction, lock A
, B
, C
and persist until the end of the transaction. Because multiple locks persist until the end of the transaction, a deadlock condition may occur when acquiring locks. Locks may change during a transaction.
This approach is serializable, which means that all events come in order and no other party can make any changes during the transaction.
This approach is pessimistic, and locks can be held for a sufficient amount of time, so resources and time will be wasted.
2. Multiversion
Instead of placing locks on A
, B
, C
, save the version numbers and create a picture of each. All changes will be made for snapshots. At the end, all snapshots will replace previous versions. If any version A
, B
and has C
been changed, an error condition occurs and the changes are discarded.
This approach does not set read or write locks, which means it will be fast. But in case of conflicts, if any version has changed in between, then the data will be discarded.
This is optimistic, but it can spend a lot more resources in favor of speed.
There is also the concept of a "transaction log" in database systems. This means that any transaction that is completed or expected will be present in the "transaction log". Therefore, every operation performed by any of the above methods is first performed in the transaction log. Journal transactions will be executed at the right time in the main store. In case of failures, the log is analyzed, completed transactions are materialized to the main store, and pending transactions are discarded.
It is also used in "log shipping" to send the log to other servers for replication purposes.
Notable implementations
There are several in-memory databases that can get in the way of some problems when implementing your own solution.
H2 also provides a serializable isolation level that may suit your use case.
go-memdb provides multiversion concurrency. In this case, an immutable radix tree algorithm is used , so you may want to look at this information as well if you are looking to create your own solution.
Many of them are defined here .
source to share
I don't know of a specific pattern here; so my solution would look like this:
First of all, I would change the edges in your graph. You don't care that A is a dependency on B; meaning: the other direction tells you what it takes to block:
A->B A->C
Because now you can say: if I want to do X on A, I need a lock of X on A and any object that depends on A.
And now you can go; check A and objects depending on A; ... etc to determine the set of objects for which X lock is required.
Regarding your comment: since X in this case is either Read or UpgradedWrite, and if A Need Write, that clearly doesn't mean B needs it .... for me this translates: the whole "graph idea" doesn't help. You see, such a graph is only useful for expressing direct relationships such as "if a then b". If there is an edge between A and B, that means you would like to treat them "the same". If you are now saying that your objects may or may not need to be locked as a record, what would be the point of that graph? Because then you end up with many virtually independent objects, and sometimes writing to requires locking the write to something else; and sometimes not.
source to share