[
https://issues.apache.org/jira/browse/JENA-514?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13743379#comment-13743379
]
Andy Seaborne commented on JENA-514:
------------------------------------
Interesting patch - it's really made me think!
I've rewritten DatasetGraphBase.deleteAny to use buffered slice approach to
avoid assuming the iterator supports .remove(). This is what TDB does now
except TDB does it more efficiently on the data structures directly.
There three areas where I think there are some issues:
* concurrent access
* maintaining B+Tree invariants.
* use in read-transactions
*Concurrent Accesses*
The original code assumes that iterators are read only. The lack of an
operational .remove() is one part of this.
Here is a situation where it matters:
Suppose there are two RecordRangeIterators, A and B, accessing the same
RecordBufferPage and that B is a few places ahead of A. If A removes a record
from the RecordBufferPage, B does not know about the RecordBufferPage changing
nor will the value of B.currentIdx be adjusted.
B will miss one record from its iteration.
Another problem is that B may not see currentPage.getCount() changing or the
change happens just after B has read currentPage.getCount(). It may read it,
be at the point where currentIdx == currentPage.getCount() and then A does it's
.remove().
B will then attempt to read off the end of the RecordBufferPage and cause an
exception in RecordBuffer as it access a now-out-of-range record.
*B+Tree invariants*
In a B+tree the whole algorithm has to be considered. There are global
properties in a B+tree, one of which is that all blocks are at least half-full.
If it drops below that, first the code tries to move an element from an
adjacent block. If both adjacent blocks are already at minimum size, the
B+Tree algorithm merges two blocks into one and cascades the fact it is now one
element smaller back up the tree, which may in turn cause blocks to be merged.
The manage of a block for moving between siblings or merging happens in the
code for the block about i.e. in the B+Tree branch code, and the ExtHash code
(ExtHash is unused currently).
Just deleting a record in the RecordBufferPage does not maintain that
invariant. We could choose to ignore that issue, do the delete and just let the
block potentially be undersized. This would need extensive testing though to
make sure the whole B+Tree code works properly. The code was written with the
B+Tree invariants assumed to be true.
*Read vs Write*
In TDB with transactions, a block needs to be promoted before it's modified,
not after. Promotion takes a copy for the writer to work on so all readers
continue seeing the old state. TDB allows man readers and one writer to be
active at the same time.
For TDB, changes in a read-iterator need to be trapped and an error generated.
Allowing changes will corrupt the database. The iterator may be working over a
block that really is part of the dataset in the case of a read transaction and
memory mapped files where there is no explicit write-to-disk step.
> Add remove() operation support on iterators of triple/quad
> ----------------------------------------------------------
>
> Key: JENA-514
> URL: https://issues.apache.org/jira/browse/JENA-514
> Project: Apache Jena
> Issue Type: Brainstorming
> Components: TDB
> Affects Versions: TDB 0.10.1
> Reporter: Knut-Olav Hoven
> Attachments:
> 0001-Applied-changes-to-how-deletion-of-triples-quads-are.patch,
> 0002-Need-to-promote-block-before-writing-it-to-avoid-get.patch
>
>
> By implementing remove() operation it will fix the issue of loading all
> objects in memory before deleting them one by one.
> It will not fix the issue of keeping all write blocks in memory inside
> BlockMgrJournal.
> Ref. email on dev-mailinglist:
> http://mail-archives.apache.org/mod_mbox/jena-dev/201308.mbox/%3CCAKha0wqFOgR_OVFUhzTiDLML5VfSMW8zdrNfFUbk2Bnktzj_Bg%40mail.gmail.com%3E
> (will supply patch soon)
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
