corruption, fragmentation and scalability

Disk space management is the foundation on which AgileWiki is being built. And there are three which need to be addressed: corruption, fragmentation and scalability. Until these are addressed there is little point in continuing.

The form of corruption which concerns me most is pending errors. This occurs when one leg of a
fork frees a block which is still in use by the other and then a system-level free of the block occurs. Unfortunately the API lends itself to this error. But it is likely quite repairable--the block is no longer in use and only we have not removed the block from the pending list. On the other hand, since it is an easy error to make, we need to be able to catch this error prior to completing the transaction which does the system-level free of the block. This can be done by maintaining a database-level list of all pending blocks and checking this list prior to doing a free. Other forms of database corruption being experienced just need to be shook out of the existing code base through the usual test/fix process.

Fragmentation is another concern, especially as the list of all free blocks is maintained in memory. Currently this is being addressed by forcing all disk space allocations to be a multiple of 64. Increasing this number has a significant impact on fragmentation and the number of blocks in the free block list, but is expensive in terms of small blocks. But there are other approaches which can be used. Remember the old buddy allocation scheme where blocks were allocated with a length which was always a power of 2? Fragmentation is avoided, but at a cost increasing disk space requirements by 100%. I am thinking that there is a less costly approach. We only allocate blocks whose size is a Fibonacci Number. This should also avoid fragmentation while increasing disk space requirements by only 60%.

Finally, there is a scalability issue in the pending lists held by the fork blocks. This list can get very large. We need to move these lists out of the fork block and into another database-level table.

COODBMS release 0.18.8

o Validate now logs numerous counts helpful in assuring the integrity of the database.
o PurgeHistory is now removes all old links and backlinks.
o Backlinks are now correct--fixed a bug in JTransacton.

There will be no subsequent release for the next week--I'm traveling.

--b

COODBMS release 0.18.7

o loggers have been split out for fine-grain control and the basic disk management events have been added.

o Validate no longer reports a bogus memory leak.

o JUnit internal node configuration has been fixed.

o RunScript now accesses static.cowdb with a query rather than a transaction.

more bugs

I just realized that there are several places where internal b-tree nodes are transparent where they should not be. Gotta fix this.

good progress today

The memory leak which occurs after the backlinks table splits are the two new subordinate nodes of the backlinks table root node. This is because validate does not see the subordinate nodes--they are transparent to the normal iterator. Basically this is a bug in validate.

COODBMS release 0.18.6

o Enhanced disk space management consolidates adjacent blocks sooner and has a new method, notFree, which confirms that a block has not been freed.

o Additional test scripts included in this release.

the new AvailableApp

The new AvailableApp is working just great and sports a method, notFree, which can be used by Fork to catch that intermittent (and likely debugging-related) database corruption bug just a bit earlier.

One advantage of the new code is that it consolidates adjacent free blocks sooner. Another advantage is that you can check to see if a block has already been freed sooner and more easily.

On the down side, the validate utility is now broken and needs to be fixed. And the new code offers no help in the latest database corruption bug which occurs after a [b-tree] split, as that is a memory leak and can only be detected by the validate utility by walking through all structures.

(The sourceforge site is down as I write this, though the new code has been checked in.)

COODBMS release 0.18.5

o Reworked PurgeHistory;
o Found/fixed a bug in Rolon.free;
o Browse run command now handles full-line comments; and
o 6 test scripts added.

a rough spot

There are now two bugs causing database corruption. One occurs when doing debugging, the other occurs when the backlinks table splits. And as the code stands, these are not easy bugs to find.

Database integrity is validated by a separate utility and can not currently be called as needed while processing a transaction. But the logic which manages disk space can be enhanced so we can check db integrity at any time--so long as only one thread is running. Seems to me like a very worthwhile project.

shaken, not stirred

Just got in. Left Delhi at 4:55 AM on Friday and then spent the next 30 hours being rocked back and forth. I am told that I will need to return again to Delhi in 2+ weeks. Meanwhile I have US and Indian taxes to work on. Life is what you make of it, yes?

So there I was, thinking about 2-time. It finally dawned on me that "it is much simpler than I had been thinking." Indeed, there is nothing further that needs to be implemented. Consider a check register application. Let us say that each check entry is a Rolon and we have a ledger Rolon whose children are the checks--and the check Rolons are named by the Ledger Rolon with a key which begins with the date the check was written, i.e. the effective date. This is a 2-time check register.

The first time axis is operational time. This is the time when a check is entered into the system or the time when the check entry rolon is updated. Operational time is also what we navigate with the "when" command. So we can easily go back to before then last set of entries/changes were added to the system and view the ledger (the children of the ledger rolon) for some past time.

The second time axis is effective time and is the prefix of the keys used to name the check entries in the ledger rolon. We see things in effective time order when we list the children of the ledger rolon. And we can process them in effective order when we iterate through the children of the ledger rolon.

And that's 2-time. Is simple.

off line for a few days

Heading out to Delhi by train tomorrow morning to apply for a new visa. I'll be back Thursday.

COODBMS release 0.18.4

o Multiple sessions are now supported.
o Numerous bug fixes have been added.
o Purge history is now working but remains incomplete.

retrodiction, when?

Retrodiction, the ability to change our perception of past events, is a key concept in Rolonics. Every living thing has this capability and many applications in the insurance industry, to give an example, require this capability. But this capability was not part of AgileWiki3, nor is it a part of COODBMS--these time machines only allow past state to be navigated.

Now depending on how it is implemented, retrodiction can be very expensive. Normally you simply reprocess all activity since the last valid snapshot. But while this may work for an application with well defined scope, it does not work in the general case unless we have well defined worksets--and even then it can be expensive.

Working with virtual snapshots, as COODBMS does, has a similar problem when it comes to retrodiction--how many snapshots need to be created, i.e. which journal entries need to be revisited? Again, it would work ok for an application with very narrow scoping.

On the other hand, deductive inferencing systems, good ones any way (not AgileWiki3) track the dependencies of each deduction and allow changes. (All X were smaller than i, but now we have a new X which is larger than i.) Ah hah! Here we have the basis for a scalable retrodiction system.

But there's still a trick. Retrodiction is about viewing past state and changes over time. If we implement it as part of the inferencing layer, then we need to support views of deductions in 2-time. So for example, if at time t4 we enter a policy with an effective date of t1 and a claim for time t2 is entered at time t3, then we need to conclude at time t3 that the claim is invalid but revise at conclusion at time t4, for at time t4 we see the retrodicted history of having a policy at time t1 and a claim at t2.

So I am thinking we can have a scalable retrodiction system by implementing it in the inference layer. But our inference engine will need to work in 2-time.

Now let us consider a check register. We want to view the checks in the order they were written, not in the order they were entered. And we want to know the account balance when each check was issued. Now we deduce the balance from the balance after the previous activity completed. But my wife and I have a joint account and I am especially bad at entering the checks I have written. So for a given check, the prior check will change over time. This then changes what the account balance was when the check was written and impacts subsequent checks as well. But this is nothing that a good inverence engine can't handle.

Now here I am talking about using inferencing as a means of implementing a scalable retrictive system. The problem is that inferencing systems don't scale. Fortunately this is one issue which was addressed in AgileWiki3. In the semantic layer (namespaces) we define worksets and use those worksets to restrict the scope of any given inference. Bingo!

COODBMS release 0.18.3

o Bug fix: snapshot backlinks were incorrect.
o Bug fix: links were accessible prior to their creation.

retrodiction in 2-time

While working on this timetravel bug, I've come to a bit of a better understanding of 2-time, specifically retrodiction in 2-time.

Let us say that when you enter a transaction you can give an effective date, either past or future. One time axis then is the time of entry and the other is the effective date. You could now potentially navigate time along either axis while viewing the state of the system. For example, I might want to view the state of the system as it was yesterday given only yesterday's entries. Or I might want to view the state of the system as it was yesterday given today's entries/corrections as well. And of course, you could view future states too.

The brain tease for me is, how do you implement such a system so that it can scale?

COODBMS release 0.18.2

o fixed several bugs relating to navigation in time.
o New setAttribute command.
o The snapshots command now lists the headlines from the corresponding transaction rolons, which gives a description of what was changed after the snapshot was made. (Snapshots being before immages.)

Heading off to Delhi, a reasonably productive day

Looks like I'll be heading off to Delhi this weekend. Should be back later next week. My visa is expiring in 2 months and it is time to work on that. So I'll also be a tad distracted these next few days as I have a whole pile of forms to work on.

All in all, it was a reasonably good day. Found/fixed some bugs. Added a missing command. Had a break from the code on Sunday and Monday, which was good as there were other things that needed working on.

what we are about

I've just added the two paragraphs below to the home page:

Application programs, when viewed from a Rolonics perspective, decompose nicely into structure, stream, wholeness and partness operations, with the occasional wholeness/partness or structure/stream operation. Addressing these aspects directly in the framework and common classes gives us a generic system that is considerably simpler than mixing these operations with the business logic of the application.

The objective of this project then is not to devise some set of extraordinary features, but to facilitate the application of Rolonics. We are not then stumbling in the dark, busily coding up something which might have some value. Only we are implementing what is clearly needed and helpful, based on a new understanding of the world around us.

updated home page

Today I rewrote much of the material on the Agile Wiki home page: http://agilewiki.wiki.sourceforge.net/

You may just find it helpful. It gives a better overview than what I had before.

Any comments you have would be greatly appreciated. Thanks in advance!

COODBMS release 0.18.1

The COODBMS database is now a time machine which fully supports navigation in time. You can go back to any prior time, view content and navigate links.

http://agilewiki.wiki.sourceforge.net/CoodbmsReleases

good day, strange ending

Release 0.18.1 is ready to go. Hardest part ws getting backlinks to work--lots of bugs there.But everything is looking good now, except that I can't seem to edit the wiki pages right now (this happens often enough) and while you can upload files, you can't access them. So expect a release within 12 hrs if all goes well--I'm calling it a night.

Had a nice chat with Thomas today (skype). He's definately interested in working on this project. He's also a friend, a co-worker from when I was working at Sun, and an ex-employee who used to work on Quick/qare/jxweb. Bright guy, and I've high expectations.

milestone reached

The code has now been roughed out for time navigation, but who knows how much has been broken in the process. Time to hammer it into shape.

a good day, but still a long way to go

Wrote the code today for resolving pathnames in past time. Now I've got to find all the places where it needs to be called.

Need a new method for generating the pathname when in past time as well. So it looks like it will be a few days before the new release is ready.

The one saving grace here is that this is not my first time machine. I know it can be done and how to do it. Progress has been steady and I've finished the hard parts already. Mostly just a lot of details to attend to and then a lot of testing.

back online

The phone is working again and I've now got broadband connectivity.

I've made a lot of progress meanwhile. Browse is now aware of time. There's a new when command. The wellknown table's keys are now "when;what". The snapshot command now uses when as the default command. And I'm just starting to work on resolving pathname for when. Things are in a bit of a mess right now and may take a day or two to fall back into place. I'm also a bit behind on the documentation.

back from Bangalore

Had a good trip, but a bit tired. No phone/internet service right now due to some local construction which damaged 30' of cable and took out 800 subscribers. It happens and no one pays any penalty. This is a bit like the wild west.

Started working on changing the wellknown table. The keys will now have a prefix--"timestamp;", or in the case of current time, "9;". This is going to mess up CowDb a bit so I will need to clean that up before going further.