500lines
500lines copied to clipboard
Transaction bug in functional db, the 'ts' field will be incorrect if execute more than one operations in a single transaction?
@yoavrubin
The functional db project is really cool, and I learned a lot from it. After reading it, I have a doubt about the Transaction section. I'm not familiar with Clojure
, if I have a wrong understanding, please forgive me, thank you very much.
In the transact-on-db
function, each operations will be executed on the initial-db
and finally generated an updated database named transacted
, and then the newest layer in transacted
will be appended to the initial-db
as the newest layer. I think there is a bug in the last process if more than one operations need to be executed in an transaction. Consider the following example:
- The
initial-db
has two layers, the first layer is empty(ts
is0
), and the second one has only one entitye
with an attribute nameda
, anda
's value isv1
,ts
is1
. - Execute two update operations in a transaction: the first one will update
a
tov2
and the second one will updatea
tov3
. The first operation will generate a new layer, in whicha
's value isv2
andts
is2
,prev-ts
is1
. The second operation will generate a new layer too, in whicha
's value isv3
,ts
is3
,prev-ts
is2
. - After above two operations,
transact-on-db
will append the layer generated by second operation toinitial-db
's layers, now theinitial-db
has three layers, the first one'sts
is0
, the second one'sts
is1
, but the third one'sts
is3
, anda
'sprev-ts
is2
in the third layer. At this time, if we invoke theevolution-of
function oninitial-db
, we will fall into an infinite loop.
The above example is just one possible error, if we execute more than two update operations in a single transaction and then invoke evolution-of
, we will fall into a 'layer not found' error.
@mlmhl Thanks for reading and I am glad you enjoyed it!
Let's start with understanding the semantics of "execute more than two update operations in a single transaction".
A transaction is defined and designed to be a set of operations occurring all together in a single point in time. Two (or more) updates on the same attribute cannot happen at the same time, and allowing that to happen contradicts the definition of transaction, therefore ends up in an undefined state.
The right way to handle such an issue is to add a thorough user's input validation.
Having said that, in our case, the main implementation concerns revolved around demonstrating the ideas behind functional database in a correct, readable and concise manner.
Thorough user input verification, alongside other production-related concerns, such as performance or security, were left aside by design.
In scenario you described we'd fall into an infinite loop when calling evolution-of
, which reflects the undefined state that the improper transaction call created (still, if you'd look at datom, they would reflect the intended user call's semantics).
I'd like also to discuss another point in your scenario, which is the timestamps assigned to the datom in the transaction you've defined. The update (a,v2) will have ts
of 2 and prev-ts 1, the update (a,v3) will have ts
of 2 and prev-ts
2, and the topmost layer at the database would have ts
of 2. There would not be a timestamp of 3 anywhere. This is due to the fact that the update to a database's timestamp happens only at the end of transact-on-db
, and the timestamp of every intermediate layer created in this function is the timestamp of initial-db
+1.
@yoavrubin The build.py script in this project is broken, do you offer an online pdf version of your functional DB, or sth else containing your work?
@Shuumatsu I'm not aware of an online PDF version. The chapter itself can be found here. The complete code can be found here.
@yoavrubin Thank you