August 07, 2004

System design

Sometimes one does very silly things. For example, I decided to merge the ID and offset fields in the object location table. Good idea at the time: smaller files. Then we ran into the problem of how to deal with deleted records, and eventually a dirty method was used: we mark it as deleted, and forget about it. A cleanup method was required for this, to clean out orphaned records. Method had a complexity of O(n^2/2).

A good friend of mine, Ycros to be exact, was reading up on file system design. This turned out to be extremely fortunate for me. He suggested a linked list of deleted records be constructed inside the OLT. Smart. Records already have an offset field, just set it to the next avaliable record (ie, a deleted one). Aha! no need for that terrible O(n^2/2) function to efficiently use diskspace!

The problem is, since I tied ID and offset together, and insertions into the XML file are indeed at the end, it effectively meant the records in the OLT have to reflect the ordering of objects in the XML file. Bad steve!

Solution is simple: split ID and offset apart again, and re-use offsets of deleted records. *sigh* More back tracking and coding. System design document has been updated to reflect this change in design :)

*Yawn* work tomorrow, good night!