Zbr's days.
←March→
Sun Mon Tue Wed Thu Fri Sat
            1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31          
←2008→
Months
Jan Feb Mar
Apr May Jun
Jul Aug Sep
Oct Nov Dec

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

Fri, 14 Mar 2008

Why binary trees are bad. New cache structure for pohmelfs.

I already found experimentally that write-through cache scales very badly, even noticebly worse than without cache at all for some workloads, so an ideal solution does not involve any kind of write-through operations notably no synchronous commands, which require immediate response.
This means that inode numbers will differ on client and server, so there should be some kind of tracked dependency between them so that operations on different machines can be done in sync. Initial though was to use binary tree to store pointers to appropriate inodes, which would be indexed on server and clients by combination of hashes of inode (direntry) and its parent data. Even embedded systems can easily have millions of inodes, so choice was thought to be correct from the first point of view. Now I think different since there is a serious problem with indexing of such a tree.
Since the only information common to both client and server is object name it should be used as a key, maybe not name directly, but its hash, that does not matter at this point. Here comes a problem with binary tree choice: in binary tree there is no connection between real parent in the filesystem and parent in the binary tree, so there will be serious problems when we will put two different object with the same name into binary tree - there will be a conflict. To solve this problem we should use some information about where this object is placed, i.e. information about its parent directory. Using parent name hash as a part of the key in the binary tree does not solve problem too, since there might exist multiple directories with the same name and the same object in it. We could solve the problem by putting into key hash of the object's name and hash of parents key (which in turn is hash of the name and hash of its parent key), so this recursive hashing would end up at the highest level (i.e. root directory). This works, but there might be scalability problem with the following issues:

  • server has to either cache opened directories or reopen it one-by-one when accessing an object
  • when object is moved/renamed all keys of its children and parent has to be changed
which is unacceptible. So new solution was thought of.

So far I have two ideas:
  • kind of radix tree
  • multi-layer hash tables indexed by double name hash
While the former is kind of obvious, the latter is quite interesting but very simple idea. Consider that each directory has a hash table of its children, it is indexed by double hash of child's name. We need double hash to remove possibility of collision (I can not prove mathematically (maybe only yet) that there are two hashes which will not allow simultaneous collision in both, but feel quite strongly that such hash pairs exist) and to use them in network commands. Commands can be optimised either to use full path if it is short enough (just sent a path string during writeback or readpage as a path to where data belongs) or use an array of hashes of the path elements instead of '/' separated names. Hash tables actually have to be changed to different data structure capable of hosting not only small hash values, but full 32 or 64 bit hashes. It can be a binary tree or judy array, something similar to what was used in unified socket storage. The former looks a bit excessive.
Using such approach it is possible to lookup an object with O(k) operations where 'k' is number of directories in a path, very usually it is smaller than 10, which for binary tree corresponds to as much as 1024 inodes, which is too small for the real system.
This approach (especially when full path is being sent) allows to eliminate mentioned above scalability problems.
Implementation start is scheduled for today, but I have to think about details first.

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

Kate wrote at 2008-03-14 20:33:

The property of not allowing simultaneous collisions in two different hashes is definitely not true of several cryptographic hashes such as SHA1 and MD5. In fact deliberately finding a matching pair of collisions is not even a much higher work factor than finding a single one. There may be non-cryptographically insecure pairs of hashes that have the property of making two matching collisions very unlikely, but if it's impossible than the combination of the two must have a unique mapping for every initial data set. At that point I'm not sure of the value of using a hash.

Zbr wrote at 2008-03-15 00:27:

Yes, I'm pretty sure that probability of the _simultaneous_ collision in sha1 _and_ md5 for given pair of texts is extremely small, but it is not equal to zero for the most of the hash pairs out there. It is equal to multiplication of both probabilities along (sha1 and md5). Yes, it looks possible, but I'm still not convinced that there are no two hashes, which will _not_ simultaneously provide collisions for any two given texts.

I can add string size limitation into the equation to make things even more complex for collisions.

Kate wrote at 2008-03-16 00:13:

Places to start reading if you want them: http://www.schneier.com/book-practical.html http://www.schneier.com/blog/archives/2005/06/sha_cryptanalys.html#c6917 http://www.freedom-to-tinker.com/index.php?p=661#comment-2523

Note that this is prior to the more recent breaks and several of the statements have been shown to be unduly optimistic, but it's a good place to start. The true situation (at least from a security standpoint) is much worse. Some of these points are unlikely to directly effect the chance of a birthday paradox match in both patches, but they do indicate that the probability is likely to be significantly higher than the multiplication intuitive analysis suggests.

The output of a hash can only be shorter than its input while maintaining a unique mapping if functions as a compression function. It also seems suggestive that if the combination of two hash functions is more secure

I know of no cryptographically secure hash with unique mapping, but they may exist. The question then is why you should use a hash if you want full collision avoidance and it's not reducing the size of your input. If you're willing to sacrifice one or the other, it may work better for certain algorithms. The combination of two hashes can reduce the probability of a collision, but not by anywhere near the naive estimate.

Reducing input size may make deliberately finding collisions more difficult, but if there are any collisions in the allowable input you may be increasing the likelihood of hitting them accidentally.

Zbr wrote at 2008-03-16 02:07:

It looks like we talk about completely different things. Let me clarify my idea first. It is of course possible to create two inputs that will give the same hash output, it is a basic nature of the surjective transformation which hash function is, and although there are no known two inputs for sha1, they do exist and just yet to be found. The same task for md5 is already solved. Interested reader can check my small steps in this direction at http://tservice.net.ru/~s0mbre/blog/devel/math/hash/index.html

Two hash approach I described is a bit different. Let's suppose that we have input I1 and I2 which produce the same H output. In my approach the same I1 and I2 have to produce the same hash output for completely different hash function 'h'. I believe that there are hashes which are constructed the way which prevent any two inputs to _simultaneously_ give collision in both hashes. It is of course is not a mathematically correct thought, but even in terms of _probability_ it is _very_ unlikely condition no matter what techique is used to obtain collision. Birthday paradox does not work here, since we have not two persons with the same age, but two persons with the same age and hair colour (or weight or whatever).

This is a _multiplication_ of probabilities, it is very small, but yet not zero. Adding here additional limit to the size of the input limits input set even more.

It is similar to the following approach: let's suppose we have not hash functions, but usual operations in some group with additional flag. For example sum and subtraction of two numbers in 2^32 field (i.e. with wrapping). If operation happens to wrap, then additional flag is set. In this case there are no two input numbers which will produce both the same sum and sub values without flag being set at least in single operation. So, we have our condition met. It is obvious that additional flag is a main stone in this approach, but I believe the same thing exist for hashes (sum and sub in a limited group is actually a hash, but input size is a serious issue in the practical example like pohmelfs).

I do agree that from first point of view it is possible to have two simultaneous collisions in two different hashes, although with extremely small probability, but I'm still not convinced that no two hashes can be specially constructed to eliminate such condition.

Please solve this captcha to be allowed to post (need to reload in a minute): 28 + 1

Comments are closed for this story.