Strata 0.0.19

Delayed Write

You now have the option to delay the flush of entry writes. Previously, each insert or delete entry would open, write and close the log. The close of the log would ensure that the contents had been flushed. Now you can delay the close until either you move to the next page or you unlock lock the Cursor your using to write.

This means that Cursor.unlock now takes a callback. There is an assertion in Cursor.unlock that will assert that a callback is provided help locate invocations of Cursor.unlock that have not been updated.

You specify the write strategy at creation by specifying a writeStage property of either "entry", "leaf" or "tree". The "entry" write stage will flush each entry that is inserted or deleted. The "leaf" write stage will flush when a Cursor moves to the next page or unlocks. The "tree" write stage will flush when Strata.close is called.

By flush I mean that there a final flush of all open files. If there is back-pressure on a file stream during writing, Strata will wait until the stream is drained.

Staccato and Journalist

Two new projects were created to support Strata.

Staccato is an adaptor for a Node.js stream that allows you to write to the stream using error-first callbacks instead of using the EventEmitter interface.

Strata exposes an error-first callback interface for writing entries. Staccato encapsulates the translation from error-first callback to write with drain events. If the underlying stream advises the caller to drain, the Staccato's error first write callback will wait for the drain event before invoking the callback.

Journalist is a least-recently used cache of open file streams. Journalist helps to encapsulate the three logging strategies. It is based on the new Magazine.

Magazine Eviction Iterator

Magazine is the least-recently used cacheMagazine now exposes an eviction iterator. We now use this to evict pages from our least-recently used cache instead of the naive purge method.

Issue by Issue

• Use external Magazine iterator. #365.
• Implement per-entry flush of writes. #364.
• Upgrade Cadence to 0.0.37. #360.
• Use Staccato. #362. #363.
• Implement gather helper as a proper Cadence function. #361.
• Upgrade Cadence to #360.
• Implement per-tree flush of writes. #359.
• Implement per-leaf flush of writes. #358.
• Split footer out of insert and delete. #356.
• Extract file I/O to a separate module. #355.
• Extract record formatting to own function. #354.
• Rename conversion to object function to vivify. #352.
• Use assert in tests. #351.
• Upgrade Proof to 0.0.45. #350.

Strata 0.0.17

Upgrade Proof

Get a later version of Proof and Cadence to ensure that the test helpers used by other modules work with the latest Proof and Cadence.

Issue by Issue

• Release version 0.0.17. #343.
• Upgrade Proof to 0.0.44. #342.
• Upgrade Proof to 0.0.43. #341.
• Add Cadence as dependency for testing. #340.
• Remove "url" from package.json. #339.

Strata 0.0.16

Upgrade Proof

Upgraded Proof to 0.0.41.

Issue by Issue

• Release version 0.0.16. #338.
• Upgrade Proof to 0.0.14. #337.

Strata 0.0.15

Underlying Record Size

Return the underlying record size. This is used by Locket to generate an approximate size. It is inexpensive to provide the underlying record size, and it can be ignored if it is not needed by an application.

Issue by Issue

• setImmediate switch is ignored. #335.
• Obtain underlying record size. #321.
• Update LICENSE date range. #320.

Strata 0.0.12

LGPL 3.0

As the sole author of this work, I have decided to release it under LGPL 3.0.

Issue by Issue

• Release version 0.0.12. #325.
• Upgrade Sequester to 0.0.6. #324.
• Upgrade Magazine to 0.0.7. #323.
• Add LGPL 3.0. #322.

Strata 0.0.11

Set Immediate

Replace process.nextTick with setImmediate everywhere. Rename the nextTick property passed to the constructor to setImmediate. Use setImmediate in the tests.

Additionally, upgrade the target version for Travis CI to 0.10 since it is the version that alterted nextTick.

Issue by Issue

• Rename the nextTick property to setImmediate. #319.
• Replace process.nextTick with setImmediate in tests. #318.
• Release version 0.0.11. #317.
• Use setImmediate instead of nextTick. #316.
• Build with 0.10 on Travis CI. #315.

Strata 0.0.4

Rock Strata, Gardiners Greek, East Malvern by Alpha

Removing the JSONSize Falsework

Demarius Chrite removed an assertion against the modification of the records returned by Strata's iterators. If a user had changed the JSON size -- the string length of an object once it has been serialized using JSON.stringify -- then an assertion would be triggered the next time the leaf page that contained the record was locked. Locket was triggering this assertion when it assigned a placeholder transactionId property to the records stored in a table that didn't store a transactionId.

This assertion was removed because the application should be allowed to take advantage of the MRU cache of pages and the their objects. When a page is purged from the cache, all of its objects are purged form the cache. If the application has any housekeeping to go with an object, it should also be purged when the page is purged. Easiest way to accomplish this? Tuck some of that data into object returned to you from the Strata iterator.

The assertion was a falsework to ensure that Strata itself was not mutating the records it was storing, but we can't have that assertion and allow the user to piggyback on the MRU, so we've gotten rid of that assertion.

See #118.

Subtle Shared Lock Continuation Bug

When continuing operations waiting on a shared lock, we iterated over the the array of waiting functions using forEach, invoking those functions. Some of those functions called unlock before the nextTick and in doing so, removed themselves from the array of functions participating in the shared lock. This it he same array of the aforementioned forEach. Mutating that array cased the forEach to get confused and skip functions.

We now copy the array with slice() before calling forEach.

This bug was discovered when the lock was extracted to Sequester.

See: #116. bigeasy/sequester#15.

Installing Strata 0.0.4

npm install b-tree

Issue by Issue

• Stop monitoring stringified object size. #118.
• unlock needs to slice the array before continuing callbacks. #116.
• Upgrade Proof to 0.0.32. #114.

Strata 0.0.3

Far-Off Buttes by BrotherMagneto

Installing Strata 0.0.3

npm install b-tree

Directory Now In options

Moved the sparate directory argument into the options hash. It doesn't look right to have the options hash optional. Most of those options do not go unspecified in any serious application of Strata.

Support for Random Inserts

If you have a list your merging into the tree, but you've not sorted it, you can still have a go at inserting the next item in your list into the current page under your cursor. Previously, Strata would assert that the inserted record's key was greater than the key of the current leaf page, but now it is not so shrill. It returns an error, a -1 to let you know that the key belongs in a leaf page to the left of the current page. That's useful if you're table scanning for reasons detailed in the Which Way To Go section below.

Increased Liveness of Inserts

Peek right gets key and immediately releases lock.

The peek at the right leaf page on insert to resolve ambiguity about the proper page for a key that greater than the greatest key in the leaf page no longer obtains and holds an exclusive lock. Instead it get key using a shared lock and immediately releases the shared lock.

The key of the right leaf page might change. It might get deleted. If it is deleted it is now a ghost. That ghost might get exorcised (permanently deleted) This would change the key of the right sibling leaf page, making the results for our of inclusion different. It would seem that different is bad, so let's hold that write lock because I fear change. We all do.

The key value for the leaf page is the first record in the key page. It is therefore, the least value of that key page. When you exorcise a ghost of a leaf page, the key value can only increase. If the leaf page key of the right leaf page changes it does not invalidate any of the tests performed against the deleted value. They are all still less than the key of the right leaf page.

After we cache the key of the right leaf page and the key of the right leaf page changes, subsequent tests might falsely report that a record does not belong on the current page. When this happens, the user is going to descend the tree again to find the correct leaf page, which is always a safe bet. It's a missed opportunity to insert the record while we're there, but it's not going to cause corruption. It's likely going to be rare and we've decided that descents are cheap and the path we take when in doubt.

This is an increase in liveness. Leaf page mutation will only ever hold and exclusive lock on a single leaf page. It will only occasionally obtain an additional shared lock and then release it immediately.

Cursor.insert Let's You Know Which Way To Go

There is case where we fail because our cached key says we fail, but we're navigating with a sorted list of items to insert and delete, so we advance to the next leaf page hoping to see if we can insert there, but we're told we fail again. If we've chosen a table scan for our approach we will continue to fail until we get to the end of the tree.

The more likely approach means that after two failures we will descend again, but if you need to know for certain we now simply return an integer to indicate failed, on that let's you know which way to go. If you advanced to the next page because an insert failed, but then it says it fails again because the key is to low, you know you lost a race and need to stop your table scan and descend again using the key that's causing the confusion.

Issue By Issue

• Upgrade Proof to 0.0.31. #113.
• Return an comparative integer from Cursor.insert. #112.
• Peek of next page during insert with read lock, release immediately. #111.
• Mutator should return false if index is to low instead of asserting. #110.
• All Strata constructor options should be in the options hash. #109.
• Fix aspect ratio of README.md image. #108.

Up Next / Strata 0.0.4

The next exciting update for Strata will be the release of Locket a pure-JavaScript b-tree implementation of a LevelUP backend. Whatever Locket wants Locket gets. Then, when Locket is built, I'll be using LevelUp unit tests and benchmarks for choose the next actions for Strata.

Have a look at the discussion that inspired Locket to get a feel for where we're going.