About :: TODO :: Blog :: RSS :: Old blog :: Projects :: GIT :: Gallery :: Notes

Sat, 18 Nov 2006

New generic wildcard search design.


Well, it is not new, but it is different from what was described before. And although previous variant has higher lookup speed, it requires too much memory, so it is not acceptible.

New one is quite simple - it will be implemented on top of trie structures. Main feature of tries is that they are quite compact (in case of PATRICIA tries) and allow W^d lookup speed in the worst case, where W is width of the interval in bits (i.e. 32 bits in current netchannels implementation, which does not support IPv6 due to my laziness and absence of requirements feedback from the community), and d is number of dimensions (5 currently), which results in very bad number of 33.5 millions operations in the worst case of (2^W)*(2^d) == 2^(W+d) (137.5 milliards) rules.
Actually with netchannels it will be much smaller since only two dimensions use full 32 bit space (source and destination addresses), while others use either 16 bits (source and destination ports) or 8 bits (protocol number), so it will be something about 2 millions operations.

Basic idea behind tries is following: trie is a simple unbalanced tree each node of which represent only one bit (i'th level of the tree represent bits in i-1 position in the searched value), so it's maximum depth is 32 (in PATRICIA trie several bits can be combined into the same node if there are no other rules, which have different bits in that positions). In that case rule 192.168.0.0 - 192.168.0.255 will be presented as 0b11000000101010000000000000000000(192.168.0.0) - 0b11000000101010000000000011111111(192.168.0.255), so actually trie will be stopped at bit 24 (counted from the most significant one) and the rest will present a wildcard (0-255 in the least significant byte in host order) or it will contain additional nodes if there are additional rules which has bits in that range, for example 192.168.0.0-192.168.0.20.
Each direction is a base for own tree.
Each node contains a pointer to the subtree of the next-dimension tree, where its rule starts. So when each node is examined (i.e. each bit is checked) in the first dimension and bit is found to to belong to some rule, next dimension is checked from the bit position specified in the node and this is being done recursively for each dimension. If in some dimension requested bit is not found in the trie (where it should be by the previous dimension rule), it means that there are no rules for requested values.

In the previous memory-hungry design, if rules do not have ranges but only single tuples (i.e. single source/destination IP address and single ports and protocol), or if all rules present the same range (for example all port rules have the same 1-65535 range), it can not lead to the described problem with memory usage. The more range overlaps rulset has, the more memory such algorithm will use - in theory, when each new rule requires interval split, i.e. when each new rule overlaps with all previous and has additional range (for example when each new rule is slightly bigger than previous one), it is O(d*W*(N^d)) where N is number of rules and d is number of directions, W is width in bits of each dimension (actually it can be hidden by O(), since it is a constant for different set of rules).

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

I wish my day would have 36 hours.


So I could quickly complete flat development, moved my laptop to HP repair (its disk fails after couple of hours of work) and started to work more than currently.

Likely if you do not see entry in the blog, that means that I'm too busy at paid work (or even unavailable at all) to work on my own projects.

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

True asynchronous IO.


All existing AIO - both mainline and kevent based lack major feature - they are not fully asyncronous, i.e. they require synchronous set of steps, some of which can be asynchronous. For example aio_sendfile() requires open of the file descriptor and only then aio_sendfile() call. The same applies to mainline AIO and read/write calls.

My idea is to create real asyncronous IO - i.e. some entity which will describe set of tasks which should be performed asynchronously (from user point of view, although read and write obviously must be done after open and before close), for example syscall which gets as parameter destination socket and local filename (with optional offset and length fields), which will asynchronously from user point of view open a file and transfer requested part to the destination socket and then return opened file descriptor (or it can be closed if requested). Similar mechanism can be done for read/write calls.

This approach as long as asynchronous IO at all requires access to user memory from kernels thread or even interrupt handler (that is where kevent based AIO completes its requests) - it can be done in the way similar to how existing kevent ring buffer implementation and also can use dedicated kernel thread or workqueue to copy data into process memory.

It is very interesting task and should greatly speed up workloads of busy web/ftp and other servers, which can work with a huge number of files and huge number of clients.
I've put it into TODO list.

Someone, please stop the time for several days, so I could create some really good things for the universe.

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