Wednesday, May 30, 2012

Tracking Changes With Event Counters and Marker Didgets

File systems use date and time stamps to keep track of when files are created, last modified and last accessed. As stated earlier, these values are stored within each file metadata record and reflect the value of the system clock running on the host system. Any application can later change these values to anything they want using the file API.

As computers and storage devices became faster and faster, many different files could be created and modified within a single second. This can make it difficult to determine in what order various operations occurred. The solution for file system designers was to increase the granularity of the values stored in the date and time stamps from milliseconds to microseconds and finally to nanoseconds. If the system clock was always guaranteed to be accurate and no applications could set these values to any arbitrary number then this approach would always allow for an accurate accounting of the order of events within a file system. Unfortunately, that is not the case.

The Didget Management System takes an entirely different approach. Each chamber has its own "Event Counter". This event counter is a 48 bit number maintained exclusively by the Didget Manager and that starts with 1 and is incremented each time some event within the chamber occurs. If the current event counter has a value of 100 and ten new Didgets are created, then first Didget created gets the value of 101 in its "Create" field. The second Didget created gets the value of 102 in its field. This continues until the tenth Didget created gets the value of 109. There is no API that allows any application or operating system to directly change the value of any of the event counter fields stored in the Didget records or mess with the event counter itself.

Using this technique, it is always possible to list every Didget in the chamber in the exact order in which they were created. Likewise, you can find the last 100 Didgets that were accessed or the last 10,000 that were modified. You can tell if Didget X was created before or after Didget Y was last modified.

Just like every other field in the Didget table record, these event counter fields can be specified when performing a general search. For example, in a chamber with millions of Didgets, I can get a list of all the Didgets that were created between event counter 100,000 and event counter 300,000 in under a second. A backup program that knows it performed its last backup at event number 1,000,000 can quickly get a list of all Didgets that were either created or modified after that point.

While the event counter allows you to know that event X happened exactly one event before event Y, it doesn't tell you when either of those events actually occurred or how much time passed between them. That functionality is left to special Didgets called Marker Didgets.

A Marker Didget is used to match either a specific date and time (as recorded by the system clock) or a specific type of event with an event counter value. These Marker Didgets are created either by the Didget Manager itself or by applications. Each Marker Didget has a type associated with it. Some types that have been defined so far are "Chamber Created", "Chamber Mounted", "Chamber Dismounted", "Backup Started", "Backup Ended", "Virus Scan Started", "Virus Scan Ended", and "Time Stamp". The Didget Manager code automatically creates one of these markers when the chamber is created, mounted, or dismounted. Applications like backup programs and virus scanners can create them when they start and when they finish. Any application can create a Time Stamp Marker at any time.

When a Marker Didget is created, the current value of the chamber's event counter is stored in that Marker's creation event counter field (just like it is whenever any other kind of Didget is created). In addition, the Didget Manager queries the system clock and stores the current date and time value also in the Marker Didget's metadata record. This allows us to know that event 1000 occurred at 10:00 am on June 4, 2011 and event 2000 occurred two days later at 1:00 (or at least that what the system clock said the times were). Even if the system clock values are not accurate, the order of events always stay intact.

The Didget Manager will not only create these Marker Didgets whenever an application specifically commands it, it can also be set to do it automatically by using Policy Didgets (another type of special "Managed Didget" that I will detail in a later post). A user or application could create a policy that commands the Didget Manager to automatically create a "Time Stamp" Marker Didget every 15 minutes. Likewise, a policy could direct it to create a "New Month" Marker every time the Didget Manger detects that a new month has began.

Marker Didgets can be used in queries to find Didgets that have been created, modified, or accessed either before, after or between Markers. For example, I could query for a list of all Photo Didgets that were created before the chamber was last mounted. I could ask for a list of all Document Didgets that have been accessed since the last backup or last virus scan. I could ask for a list of all Software Didgets that were created after the New Year Marker in 2010 but before the New Year Marker in 2011.

No comments:

Post a Comment