Opened 18 years ago

Closed 8 years ago

Last modified 6 years ago

#40 closed enhancement (fixed)

Alternative approach to tracking free blocks in btrees

Reported by: Olly Betts Owned by: Olly Betts
Priority: low Milestone: 1.3.2
Component: Backend-Brass Version: SVN trunk
Severity: minor Keywords:
Cc: dcolish@… Blocked By:
Blocking: Operating System: All

Description (last modified by Olly Betts)

Use chains of free blocks rather than a bitmap - then we can store many old revisions more cheaply (just the space they actually need, not a whole bitmap for each one too). Then readers use fcntl locking on a single byte corresponding to the revision they're using (bytes off the end of the file can be locked, and shared locks on read-only files are ok). Then a writer would only delete old revisions for which it could obtain an exclusive lock (otherwise it would preserve them).

The Btree manager is generally written with multiple old revisions in mind, so this shouldn't be a huge project.

Attachments (1)

betterdebug.patch (641 bytes ) - added by Olly Betts 16 years ago.
Debug tracing tweaks to help investigate this

Download all attachments as: .zip

Change History (13)

comment:1 by Olly Betts, 18 years ago

Severity: blockernormal
Status: newassigned

comment:2 by Olly Betts, 17 years ago

Component: otherBackend-Flint

Reassigned to the flint backend.

The fcntl locking issue is now addressed (in flint).

I've also worked out how to update freelists atomically and cheaply.

comment:3 by Olly Betts, 16 years ago

op_sys: otherAll
rep_platform: OtherAll
Severity: normalenhancement
Version: otherSVN HEAD

comment:4 by Olly Betts, 16 years ago

Priority: highlow

by Olly Betts, 16 years ago

Attachment: betterdebug.patch added

Debug tracing tweaks to help investigate this

comment:5 by Olly Betts, 16 years ago

attachments.isobsolete: 01
Operating System: All

(From update of attachment 56) Gah! Attachment meant for a different bug. I hate bugzilla.

comment:7 by Olly Betts, 14 years ago

Component: Backend-FlintBackend-Chert
Description: modified (diff)

Remarking for chert...

comment:8 by Olly Betts, 13 years ago

Component: Backend-ChertBackend-Brass
Milestone: 1.2.x

I'm intending to implement this as part of the new B-tree manager for brass.

comment:9 by Olly Betts, 13 years ago

In brass, there will be a single for each revision which is still valid, so the readers just need to lock the one they are using.

comment:10 by Dan, 12 years ago

Cc: dcolish@… added

comment:11 by Olly Betts, 10 years ago

Milestone: 1.2.x1.3.2

I have a patch implementing free lists instead of bitmaps now, which it should be feasible to land for 1.3.2.

The "betterdebug.patch" attachment seems to be unrelated to this ticket - I suspect it was aimed at a different ticket, but despite looking through the list of tickets, I failed to work out which one...

comment:12 by Olly Betts, 9 years ago


comment:13 by Olly Betts, 8 years ago

Resolution: fixed
Status: assignedclosed

This change was merged on 2014-02-21 in r17864.

I've opened #648 for the reader locking idea.

Last edited 6 years ago by Olly Betts (previous) (diff)
Note: See TracTickets for help on using tickets.