About TODO Blog RSS Old blog Projects Gallery Notes

Fri, 26 Oct 2007

Climbing evening.

That was bloody perfect traing - although I did not that many traces (actually only two - one quite old with a jump, and new one, which I really wanted to complete on-sight, but failed, since tired a bit waiting for another climber, who was on the way), although quite a lot of bouldering-like starts from new traces.
Although my foot is still quite strongly aching, it does not hurt me when I climb, although I can not say that about process of getting shoes off - that is a real crap...
But nevertheless it was good - I think I'm slowly getting my old shape back, so eventually I will in a good form, today's training showed just that.

/life :: Link / Comments (0)

Ok, the nearest development plan.

There are two companies, which wanted to work with me on distributed storage - both keep silence, I dissapointed about that, but can not and do not want to blame them of course. It theirs business...

So, while part of the brain thinks about interesting on-disk filesystem layout, most of it I decided to devote to the following problem:
let's suppose, that we have a map of objects (only points - 2d coordinates of number of dots), and small piece of it, possibly with different scale and rotated against some unknown point.

The problem is to find, what part of the original map this piece from.
I'm pretty sure this is not a trivial problem, and likely there are some solutions out there, but I want to invent my own.

Stay tuned.

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

Byte range locking algorithm.

I've completed and tested it with one million users writing to the same 100 Mb area with random offsets and sizes - that was done of course in simulator, without actual writing, since its main goal is to determine lock contention and its avoidance.
Unfortunately this simulation can not say about real performance of such approach, since there are no timings for each write and cost of waiting for completion, so I will either extend this test to support tree of timers or will postpone this until there is a real filesystem to test on.

Right now I'm thinking more about how on-disk structures should be organized for the maximum performance.

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

Crypto analysis.

Dr. Bernstein offers a prize for his cipher analysis: no matter if it is full ($1k prize was awarded for 5-round differential crypto analysis of Salsa20 cipher) or complete, first it should be interesting. I personally like Dr. Bernstein not very much for his code licenses, hard communications and some times self-conceit (likely because I have the same 'problems', except license :), but he is a real hacker - he does for fun (and money, which I believe is not an issue) interesting for himself things.

Some time ago I even knew what is that, I tried to perform different cryptoanalysis (trivial of course), and likely will return to this topics eventually: time is the only limiting factor here.

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

Byte range locking.

Last couple of days I wroked on the tricky algorithm for byte-range locking, which is especially interesting for distributed systems.

Consider the input, which contains of the ordered number of items (for example usual file - ordered set of bytes), and (potentially huge) number of users, who wants to read or write to the arbitrary contiguous areas of the input (like number of threads wants to read or write to the same file with random offsets and data size). Without proper byte-range locking this scenario clearly shows a bottleneck with locking contention.

My algorithm is quite simple - each user requests an ability to write to its area and during that write it locks only it, any subsequent write to the non-overlapping area will be performed in parallel with other writes, writing in case of overlaping regions will suspend second write (which overlaps with current one) until current one is completed. Second write will grab a lock (actually there are no locks, but a tree of permitted writes) for the region maxed of two overlapped regions (i.e. theirs concatenations), so that third write, which overlaps with one of the first two (current or subsequent) would be postponed too. When underlying write is completed, it schedules subsequent write, which in turn will schedule other subsequent write to the overlapping region. Thus all writes become asynchronous and writes to the non-overlapped regions will be perfomed in parallel. This does not match POSIX semantic (since writes to the overlapped regions are postponed and performed in order, writes to the other regions can be completed earlier), but in any given time any read from given region will return correct data for that region.

This problem especially rises when number of threads write to the same file on the different nodes, which can not rely on local page locking (line in Linux VFS).

There are some problems with the algorithm though - it uses (sometimes) too long recursive calls, which should be eliminated before used in real life. That is what I'm working on right now.

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