[FEATURE] Transactional Zone Tree Iterator

[nzdev]

Is your feature request related to a problem? Please describe.
ITransactionalZoneTree does not have a way to iterate the items.

Describe the solution you'd like
CreateIterator from IZoneTree supported on ITransactionalZoneTree.

Describe alternatives you've considered
I've considered using IZoneTree instead of ITransactionalZoneTree, however I require transaction support and it does not appear to be possible to have both IZoneTree and ITransactionalZoneTree in use at the same time.

Additional context

[koculu]

Hi @nzdev
Thank you for the reasonable feature request.
There is a workaround for you to be able to iterate transactionally.
You may use the following workaround until the feature is implemented.

I haven't tested the following scenario yet, but theoretically it should work.
I will implement a transactional iterator as soon as possible using this technique.

// Assuming a transaction is already started with following id.
long transactionId; // your transaction id
ITransactionalZoneTree<,> transactionalTree; // your transactional tree
var zoneTree = transactionalTree.Maintenance.ZoneTree; // underlying ZoneTree

// Create a non-transactional iterator using underlying ZoneTree.
using var iterator = zoneTree.CreateIterator(
	iteratorType: IteratorType.AutoRefresh, includeDeletedRecords: true);
	
while(iterator.Next()) {
   var key = iterator.CurrentKey;

   // Read the value transactionally to put the read-timestamp and dependency record.
   // Transaction can be aborted here with an exception because of dependent writes from earlier transactions. 
   // (optimistic transaction works like this)
   //
   // As an alternative you can use ReadCommittedTryGet instead of a TryGet to retrieve the committed value only.
   // In this case no read-timestamp nor dependency record is added,
   // and the transaction does not abort with an exception.
   // Faster in execution with no footprint.

   if (!transactionalTree.TryGet(transactionId, in key, out value))
     continue;


   Console.WriteLine(value);
}

[nzdev]

Thanks @koculu. I'll give this a go.

[koculu]

Additional notes:

ZoneTree supports only OptimisticTransactions right now.
My long-term goal is to add support for the following transaction types:

• Two-phase locking (2PL)
• Multiversion concurrency control (MVCC)

Starting reference on the topic: https://en.wikipedia.org/wiki/Concurrency_control

How Optimistic Concurrency works?
https://en.wikipedia.org/wiki/Timestamp-based_concurrency_control

Reading values transactionally comes with a cost: Every read creates a read-write stamp and adds a transaction dependency record if the read value is written by another uncommitted transaction.

If you don't want this cost and reading committed values is ok for your business logic,
you may use ReadCommittedTryGet instead of a TryGet in the iteration.
In this case, the isolation level would be ReadCommittedSnapshot.

If you directly use the non-transactional iterator's value, the isolation level becomes dirty reads.

Avoiding phantom reads is not supported yet.

Solution for Phantom read phenomenon (for optimistic transactions with B+Trees):
https://citizenchoice.in/course/Data-Base-Management-System-Question-Answers-/Chapter%205:%20Concurrency%20Control%20Techniques/Phantom-Phenomenon

ZoneTree is a LSM tree and provided B+Tree solution is not applicable.
However it gives the insight for the right direction.
We need to add range based time-stamps to support avoiding phantom reads.
Noted here for future reference.

Additional references:
https://dev.mysql.com/doc/refman/8.0/en/innodb-next-key-locking.html
https://en.wikipedia.org/wiki/Isolation_(database_systems)