About TODO Blog RSS Old blog Projects Gallery Notes

Thu, 29 Nov 2007

The 21'th netchannels release.

Netchanel is a peer-to-peer protocol agnostic communication channel between hardware and users. It uses unified cache to store channels, allows to allocate buffers for data from userspace mapped area or from other preallocated set of pages (like VFS cache). All protocol processing happens in process context.

Users of the system can be for example userspace - it allows to receive and send traffic from the wire without any kernel interference, to implement own protocols and offload its processing to the hardware.

This idea was originally proposed and implemented by Van Jacobson. This patchset (with userspace netowrk stack) is a logical continuation of the idea with move to the full peer-to-peer processing.

One of its users is userspace network stack.

Short changelog:

• fixed queue length usage
• fixed dst release path. Both problems reported by Salvatore Del Popolo (delpopolo_dit.unitn.it)
• removed nat user

/devel/networking :: Link / Comments (0)

B(something)-tree vs. RB-tree.

This simple benchmarks test btree vs rbtree search and insert speeds, when nodes are allocated in memory.
Btree is (likely) a b+tree where each data node is located at the bottom layer (probably it is a bit different, algorithm does not strickly follow rules described in btree papers. 1 million entries were inserted or searched in the tree.
Graphs below show speed of the given operation depending on number of keys in the btree node (when number of keys is smaller than 20 linear search ofthe key is used, otherwise binary search).



B(something)-0tree vs. RB-tree. Search speed.



B(something)-0tree vs. RB-tree. Insert speed.

As you see, btree search is about 2-2.5 times slower than rbtree. This can be clearly described by the fact, that rbtree contains data in each node, while btree only in the lowest nodes, so each btree search requires to travel over all layers (this is roughly equal to log2(number of keys in each node)) multiplied by number of keys in each node (in the worst case), while rbtree needs to perform the same amount of searches only in the worst case, while generally it requires about 2 times less traverses.

Btree insert speed can be even slightly faster than rbtree, since during insertion tree grows from low levels and each new allocation reserves space for several keys, thus greatly reducing number of needed splits or rotations.

I will run the same tests for the case, when all nodes are allocated from disk storage, which should show clear win of the btree approach.
Stay tuned.

/devel/fs :: Link / Comments (0)

Astonishingly screwed tapeworm.

New release of the distributed storage subsystem. This is maintenance release and includes bug fixes only.

Short changelog:

• use node's size in sectors instead of bytes
• fixed old/new ages for the first node. Error spotted by Matthew Hodgson (matthew_mxtelecom.com)
• fixed debug printk declaration
• new name

/devel/dst :: Link / Comments (4)