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

Wed, 08 Oct 2008

This day has come.

• The new distributed locking subsystem. Locks were prepared to be byte-range, but since all Linux filesystems lock the whole inode, it was decided to lock the whole object during writing. Actual messages being sent for locking/cache coherency protocol are byte-range, but because the whole inode is locked, lock is cached, so range actually is equal to inode->i_size. One can simultaneously write into the same page via different offsets from different client, and every time file will be coherent on all clients which do it and on the server itself.
• Documentation update. Fixed by Adam Langley (agl_imperialviolet.org)
• Add/del/show commands patch from Varun Chandramohan (varunc_linux.vnet.ibm.com)
• Bug fixes and cleanups.

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

Tue, 07 Oct 2008

POHMELFS locking testing.

So far it produced not bad results. But not good either. I see locking messages and they are in the right order and file content is not damaged, but clients frequently give up on timeout waiting for lock to be granted. Since locking release process requires inode to be unlocked (so it could be found and locked by the thread, which received network packet), this indeed may take too long on slow media and disks, since locking has to wait until data is written, for example wait for writeback completion or page reading, if they were note in the cache yet.

I tested POHMELFS locks in Xen domains, where network speed is limited by 3 MB/s and writing one million (or ten millions, that may be the point) 8-byte entries at different offsets (sequential step of 128 bytes) took more than 50 seconds, so 5 seconds default lock timeout could be not enough.

That's the theory, in practice I need to test different timeouts and actually run on real machines, but here comes another problem. I have three quite fast SMP machines with lots of RAM connected over gigabit ethernet, which can be used whatever I like. But...
The first one was essentially killed by tbench regression testing. They all have long history of problems with disks or SCSI controllers, now it happens again: the first machine boots only with single 2.6.22 Debian kernel, anything else (including vanilla 2.6.22) fails to read data from the software raid partition, although disks are detected correctly.
Another machine is actively used by aforementioned tbench regression testing, it takes quite long time to boot it and run tests, so things are slow enough.
And the last one is used to control IPMI, since it is the only way I have to reboot them, so when I managed to freeze all three, I needed to contact people who needed to contact people, who needed to hard reset machines in datacenter and put them into BIOS, since existing KVM switches are stupid enough not to respond to keyboard when machine died.

So, I'm a bit forced to spread efforts in several different directions, but nevertheless there is a little bit of time for the new things:

$ ./elliptics -c ./elliptics.conf 
2008-10-07 01:03:39.430198 12778 Logging has been started.
2008-10-07 01:03:39.430559 12778 Successfully initialized 'sha1' hash.
2008-10-07 01:03:39.430641 12778 Node id: b551803fd74ff5590ed38f6ce8a10a2e577b2a9e
2008-10-07 01:03:39.431076 12778 Server is now listening at 127.0.0.1:1025.

$ cat elliptics.conf 
#
# This is a simple config file for the elliptics network.
# Note, that spaces are skipped before and after the '=' delimiter.
#

log = /dev/stdout

hash = sha1
id = This is id string

#numeric_id = 1234567890abcdefffffffffffffffffffffffa
 
root = /tmp
addr = 127.0.0.1:1025:2
#addr = ::1:1025:10

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

Thu, 02 Oct 2008

POHMELFS got new locking subsystem.

I've completed a small rewrite of the distributed locks in POHMELFS. They can be byte-range, but since Linux VFS locks the whole inode during writing, I decided first to implement simpler apporach, so although clients send byte-range locks, server locks the whole object.

If there is a simultaneous writing to the object, only one writer is allowed at a time. Write locks are grabbed at write time, read locks at read time. Writing is still handled via writeback, so all caching facilities persist. Locks are 'cached', i.e. if inode was locked and no one else tried to update it, no new lock messages are sent between server and client. Lock release message (initiated by another client, who wants to start writing into the same file) forces inode writeback on the current lock owner.

I've started a testing process, so far quite trivial, but I plan to write a simple application, which will simultaneously write into the same file from different clients into different offsets (like first client writes each second byte, second client writes each third byte and so on) and check the result. If everything is ok, I will release a new version this weekend and start implementation of the really cool distributed facilities I plan to have in POHMELFS. It will be first implemented as a library, so that anyone could use it to create a distributed storage without patching a kernel (but with own API though, I do not want to mess with FUSE).

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

Sat, 27 Sep 2008

POHMELFS cache coherency protocol.

Finally it looks like there are no killing bugs or noticebly bad features in the distributed storage, yesterday I pushed a change to drop wrong debug, which may resulted in a crash, also couple of comment cleanups are waiting to be pushed, and likely that's it. It will be the last release, if there will be no new feature requests or bugs found.

So, I switched back to the POHMELFS development from DST.
To be really cool in cache coherency collisions, POHMELFS requires new locking/coherency mechanism, which I implement similar to MOESI cache coherency protocol. Which basically means a floating lock for given object, which may be owned by only one client at a time not counting readers, they just receive a message, that theirs data is not valid anymore.

First, I changed userspace management of the inode cache: now there is only single tree of all objects, which were ever opened by any client. When client disconnects or drop inode locally, it is removed from the server's cache also.
Next, there will be a special command to acicure grab/release a lock, which is only being sent by writers. When writer starts its dirty job of damaging shared data, it sends a lock grab message to the server with requested range, which in turn is broadcasted to the other writers, only single writer is allowed to own given area. Then server proceeds with its usual tasks of cooking or waiting for IO. Eventually owner of the lock decides to release it, for example after above message from the server it can flush data to the server and send lock release message or just on its own. So server checks if given area is now free and sends lock comepltion message to the requester. New owner receives the message, mark inode as own and starts writing there. Any subsequent writing, if inode is marked as owned, does not end up with additional lock message.

So far looks doable, but I only completed what is called 'first' above :)
If there will be no major problems with other project, I plan to complete this part quickly and move furward.

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

Thu, 11 Sep 2008

POHMELFS development process.

I completed design (without implementation yet :) of the new locking (or cache coherency mechanism, it does not really matter) for the shared objects in the POHMELFS.

It is somewhat close to the MOSI (even MOESI) cache coherency protocol, used in modern CPUs, although also differs a bit because of the nature of the POHMELFS server. It can provide byte-range locking for any object, but so far I will only implement per-file locking (i.e. the whole file will be 'locked' or 'owned' when client performs a write, even if another client could write to the different location in the same object), and if scalability will not be good enough, it can be extended (not that complex though). Since all in-kernel filesystems lock the whole inode when performing a write, this should not be a big problem.
This approach requires to change POHMELFS server's directory cache, but I never liked existing one, since it looks a bit over engineered.

If things will go smooth, I will complete it tomorrow before flying to the kernel summit (saturday early morning), since idea is really not very complex as long as I expect implementation to be.

Meanwhile, DST got a fix for the incredibly stupid bug I made, even do not want to call this 'bug', it is likely a tricky created blindness by the electrons moving things around in my monitor. They forced me not to see an obvious place to lock access to, which resulted in a nasty oopses. Patch is already in the git tree.

There is another one though: when some SCSI device is being exported and client performs a write, request has somehow zero req->nr_phys_segments field (which should be initialized from block IO request), which catches a BUG_ON() in the scsi code. I'm working on it right now.

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

Mon, 25 Aug 2008

POHMELFS configuration extension.

I've committed changes from Varun Chandramohan (varunc_linux.vnet.ibm.com) which extends POHMELFS to support ADD/REMOVE/SHOW configuration groups.

Configuration group is a global object inside pohmelfs core, which contains information about servers to work with and various configuration parameters. When administrator mounts new pohmelfs filesystem, he or she has to setup appropriate configuration group and use its index as mount option parameter. There is special configuration utility for this purpose inside POHMELFS userspace package.

Now it is possible not only to add or remove groups, but also to show them to the administrator.
I've pushed chages into the kernel and userspace GIT trees.

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

Sat, 26 Jul 2008

New POHMELFS release.

This release was fully made by other developers. Thanks a lot for your work.
I only updated some trivial bits and fixed bug in the server.

Short changelog:

• Documentation update by Adam Langley (agl_imperialviolet.org). Now one can read properly spelled POHMELFS design.
• Server and configuration utility IPv6 support by Varun Chandramohan (varunc_linux.vnet.ibm.com). Kernel client does not need this changes, since it supports any protocol. Now one can create POHMELFS cluster over IPv6.
• Server bug fix and small documentation update by me.

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

Fri, 25 Jul 2008

This was supposed to be a new POHMELFS release day.

I accumulated patches from Varun Chandramohan of IBM Linux center, which add IPv6 support to the POHMELFS server and configuration utility. Kernel client does not need it, since it works with any kind of addresses (by design).
I also wanted to add documentation update from Adam Langley, but apparently I accidentally deleted his patches, so release is being postponed a bit.

Meanwhile I made some little progress at DST development side. Added trivial configuration bits and started to develop cryptography part, mainly configuration (which I will copy from POHMELFS) and thread pool subsystem.
The latter is rather simple patch, which will allow to create a thread pool, to add/remove threads on demand and to queueu a work to the pool. In theory this can be a generic enough patch to be used by other users (I even saw some kind of topic proposal for kernel summit), but so far I'm not going to push it separately from DST. Main goal of this system is crypto processing of the BIOs for the distributed storage.

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

Tue, 22 Jul 2008

POHMELFS distributed facilities design notes.

Since I'm quite busy with VISA/hotel/tickets and overall preparations for Kernel Summit, there is no development progress, but it should be completed very soon I think, and so I will write here some design notes I have in mind about how POHMELFS server will be designed. It is not a finished draft, but somewhat a rough direction paint.

POHMELFS will utilize distributed hash table approach, i.e. storage will support ability to get an obect based on some key attached to it. In a local filessytem we already work with hash table: directory lookup is no more than lookup for inode object based on its name, i.e. lookup for the value based on attached key. And although key in this case is not created based on object itself (like hash of the content or some other function), it still is a (turn on your imagination here) table lookup.

Cloud of POHMELFS servers will utilize similar approach. Consider a single server in the system. When it joins the cloud (I ommit this proccess for now, and will describe it below) first time, it is empty, so it gets some unique id, either via administrator steps or randomly, or it just waits in the queue to be filled with new data, so it will get id at that time, it does not matter for now how it gets its id, but this id is propagated to some cloud of its neighbours (or if it would be a bittorrent or napster to the main server).
There are two ideas on how to treat this ID: either as a part of the filename, or as a nameless pointer in the abstract namespace, I will show below that actually it does not matter.

Now, let's check what will happen when user wants to perform some IO on given file.
Every file access actually happen to inode, stored on disk. In our case it can be stored somewhere we do not know yet where, so we need to perform a lookup to get address of the node in cluster which contains our data. In existing schemas like bittorrent or Lustre there is a server (or small cloud of servers) which contain mapping information about where this or that object is placed in data cloud, so simple lookup to this server(s) return needed info. This approach does not scale to really lots of nodes and is failure-prone.
Instead I consider completely distributed metadata storage. Let's check how system will lookup the whole path in our case.

Each path starts from the root directory, which is '/', which in turn is a id in the global namespace (or hash from this string or whatever else mapping), so we first need to lookup a node, which is responsible to content of this directory. Each node contains routes only to the very limited set neighbour nodes (in various designs this number varys, but idea lays in the fact, that node, performing lookup, does not know which node contains needed info). Gnutella system just broadcasted this lookup request to all of its neighbours, so each one broadcasted it to its neighbours and so on until one of the system replied, that it contains needed info. Amount of unneded broadcasts killed Gnutella next day after Napster was closed.
So, this approach does not scale, and instead we need to map needed directory into node address in a more intelligent way. There are at least two the most appealing design choices: ring-based structure implemted in CHORD and multidimensional torus implemented in CAN.
Right now it does not matter, let's assume that we found a node, which has information about content of the needed directory. When we have that data, we can find next node (or this info can be cached on 'parent' directory node) and so on until get node, which is resposible for storing content of the needed object.

When new node joins the cloud it connects to one or another known node (provided either in public service or by administrator) and sends there information about its available space, gets ID and just waits until some client connects to it and start writing a data.
When node joins with some content, which was written to it by the system before, or written by local users bypassing distributed mechanism, node has to tell this information to the node, which holds parent directory. This information should be stored in each directory it exports, or it can be provided by administrator, for example this node exports dir '/zbr' which is actually a subdir of '/home', so node will lookup '/home' directory content owner and update its records, that now it contains new dir. There is a problem here: what if there is already another node, which also claims to have dir '/zbr' in '/home'? This can be handled via attached to each object extended attribute, which will tell us the last modification date, so system can select either the last modified '/zbr' dir or that node, which contains dir with the biggest number of the same replicas. It can be setup by administrator.

Main advantage of this joining scheme is the fact, that we actually do not need to know content of any object in the exported directory, we publish only high-level object, which may or may not contain some inner file or dir. Thus we do not need to hash millions of files in the exported directory and publish them one by one, we do not need to store information about each inner object, no need attach full path to each object and so on.

When we will decide to split the same object between multiple node, we will need to introduce not only name based lookup, but also extend it to the offset inside the object. This can be done by introducing ssytem wide 'block size', so each file is actually set of blocks of given size, so when we found a node, resposible for storing information about directory, where it is located, this node can also contain information where each part of the object was stored.

Looks quite simple, but... Devil is in the details.
I obviously missed some bits in the design (and I created it in mind during talk being under 'impression' of the greece spirit while talking with asm@, who suggested to look at Kademlia project), like redundancy management of the nodes, splitting of the node content between multiple nodes and other bits, but it is one of the first drafts, so things can be changed if needed.

Stay tuned, I will be very soon back to development process (DST first :), since paper work for kernel summit travel seems to reach its end.

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

Mon, 07 Jul 2008

New POHMELFS release.

Irish 'Clontarf' and Scotch 'Grant's' helped to rule this release out.

This POHMELFS release features include:

• Strong cryptography support. One can encrypt whole data channel (except headers) and/or hash/digest it. System will try to autoconfigure itself and if server does not support requested algorithms, mount will either fail (if special mount option is specified) or disable appropriate algorithm usage.
• Bug fixes.

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

POHMELFS crypto processing performance.

If you expected a miracle, it did not happen, so I just present a picture, where I compared plain async in-kernel NFS server (no encryption, no checksumming) versus POHMELFS, which performed SHA1 hashing and AES-128-CBC encryption of the whole data channel.
Block size used in iozone test is 8KB, filesize - 8GB, 1GB of RAM.

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

Sun, 06 Jul 2008

Multithreaded POHMELFS crypto processing.

Meanwhile having a rest from various celebrations, I managed to complete receiving multhreaded crypto processing in POHMELFS.
So far it was only tested in debug environment (i.e. zillions of logs and overall miserable performance), but it shows, that different threads pick up the work, both on sending and receiving directions.
There is a limitation though: the same crypto threads are used both for receiving and transmit pathes, so it is possible to saturate them all for example for receiving, so sending will stall. If there are unsufficient crypto threads, waiting for RX crypto processing can take too long, so watchdog transmit scanner will fire up and complete transactions with errors. One can work this around by specifying big enough number of crypto threads or long enough transaction scanning timeout, both are provided via mount option.

I would like to test it in more production-like environment and perform various stresses on it, but I'm far from my working place, so can not do it right now. Which means release will be postponed for tomorrow (if testing will not show regressions or bugs).

This will not be last feature release though: for example POHMELFS does not support extended attributes and ACLs, there is no header checksum (although there is a reserved 32-but field) there may be some features in different areas too, but I do not hurry to implement them, since I need something to put into future POHMELFS changelogs. I think sending the same kernel patch with different words about userspace server changes is not the way to go, so there should be some kernel changes too :)

I will draw up some design notes on how I plan to implement POHMELFS server, and namely how distributed facilities will be done, so far I have quite clear picture in mind, but it needs to be worked out 'on paper' to find rough corners.

Stay tuned!

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

Thu, 03 Jul 2008

POHMELFS crypto support has been completed.

kernel$ git commit -a
Created commit b07e3ed: Added crypto support.
 9 files changed, 1534 insertions(+), 221 deletions(-)
 create mode 100644 fs/pohmelfs/crypto.c

fserver$ git commit -a -m "Aded crypto support."
Created commit f916b2f: Aded crypto support.
 3 files changed, 788 insertions(+), 94 deletions(-)

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

Wed, 02 Jul 2008

POHMELFS crypto: feel incredibly stupid.

First, POHMELFS does need to have encryption. Because I plan to use distributed hash table approach in server (well, consider POHMELFS kernel client as a kind of bittorrent filesystem client), and as in any non-centralized system, content transferred via uncontrolled data channels has to be encrypted.

But... I'm incredibly stupid: I implemented encryption and decryption in place, i.e. VFS page is being encrypted prior to be written to the servers, so subsequent reading leads to... Yes, it reads encrypted content.
To fix this issue I plan to encrypt data into different pages and send them, leaving VFS ones as is. There are two approaches I consider:

• allocate and send pages at writeback time - we want to send 5 pages, so allocate 5 pages, encrypt data into them and broadcast them to all needed servers.
• allocate (potentially large) pool of pages at mount time per crypto thread and encrypt data into them. This will have about zero run-time overhead for VFS, except slightly delayed because of encryption write completion.

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

Mon, 30 Jun 2008

Filesystem development rumors.

Rumor number one. SWsoft aka Parallels actively searches for Linux kernel hackers in lead Moscow universities, namely MSU and MIPT. I saw theirs posters, where among other (wanted) requirements there is distributed filesystem knowledge.

Rumor number two. Alexey Kuznetsov (if you do not know, its the guy who wrote major part of linux network stack, namely TCP/UDP/IP and socket implementations, and although there was lots of changes in the stack since then, I think it will not be an exaggeration to call him the author), who also worked on Virtuozzo and OpenVZ (and its interesting VFS parts, which AFAICS are not in kernel, maybe yet), so he works on some filesystem too. The last time we 'confronted' was couple of years ago, when I first time implemented netchannels and tried to convince network community (and namely Alexey Kuznetsov and David Miller) that netchannel idea worth further investigation and implementation. IIRC I did not succeed, although results were very impressive.
Let's see what will happen with filesystems :)

Rumor number three. SWsoft recently started to actively search for kernel hacker for 'new interesting open source project'. They always searched for kernel programmers, but never told anything about projects, now something changed.

Rumor number four. OpenVZ and Virtuozzo have serious problems with NFS (especially when server dies), probably because of very ugly NFS protocol (yes it is), so its hard to properly virtualize it (or not?). There are no alternatives for NFS right now in major productions, but you all know about POHMELFS which right now can be used as really good replacement.

Rumor number five. SWsoft has long history of PHD defences (at least in MIPT) based on theoretical FS called TorFS (namely Tormasov FileSystem), year ago it was still not very alive project in practice, but I heard that it was very impressive in theory. This rumor exists really many years.

So, I have a quite clear picture, that SWsoft started development of the new distributed filesystem, which is aimed at first to replace NFS in virtualized environments. I can also imagine very interesting distributed parallel facilities needed for virtualized systems. And they try to attract lots of people to the project as long as really heavy artillery like Alexey Kuznetsov.

Which basically means, that sooner or later my development will meet strong concurency from this company, which has lots of really good professionals.
And that's very interesting and cool :)

P.S. or it may be a complete bullshit and delirium of my fevered consciousness.

And one fact about POHMELFS: today I finished client support for padded crypto processing of all requests and started to work out server bits, I expect to finish it in a day or around, so new release is very close.

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

Sat, 28 Jun 2008

Need to rethink POHMELFS crypto a bit.

1. Because of encryption problem - data to be encrypted has to be blocksize aligned, so some informaion about padding has to be added into network command as long as crypto data size.

2. IV generation. I decided to extend network command and put there 64 bit IV for given packet. using simple sequence number is enough to protect against repeat message attack.

3. Encryption/hashing data. I decided not to ecnrypt/hash network headers, and only do it for transmitted data. If transaction contains several commands, data for all commands will be encrypted/hashed, in case of hash, signle digest/hmac will be generated and placed into transaction header.

4. It is possible, that I will add strong header checksum, which will be generated only for header and placed into special field. It will be calculated assuming checksum field is zero. This step is optional so far, but network header has 32 reserved bits, which can be used for it.

Right now hashing and encryption work, but are not checked on server (although generated), because of crypto alignment ugliness I decided to rethink approach a bit.
Evolution process in action...

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

Thu, 26 Jun 2008

POHMELFS server got initial crypto processing capabilities.

POHMELFS server is able to handshake hash/cipher names and operation modes, to initialize appropriate algorithms and perfrom basic operations (like more generic hash_update() instead of different functions with different arguments used to hash data depending on operation mode, either simple digest or hmac: EVP_DigestUpdate()/HMAC_Update(). I'm working on the right way of doing crypto processing, since how it is done right now is a bit hairy, i.e. without serious changes in the code.
I already hate OpenSSL API: EVP_get_cipherbyname(), EVP_MD_CTX, EVP_DigestFinal_ex(). It looks like above functions were written by three different persons and they never actually talked to each other about how to make them look similar... But it is a minor issue of course.

So, when things are settled down, I will make a new release, likely it will see the light this week.

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

Wed, 25 Jun 2008

POHMELFS input crypto processing engine is ready for testing.

But testing can not be done without appropriate server support, which is now the main task. POHMELFS uses lazy crypto engine - each network state (it represents connection between client and one server) contains number of fields used exclusively for semi-lockless input data processing (it locks state when performs actual reading, but does not hold that lock when processing incoming messages, since it is the only path, which receives data), now it also has crypto information about how to manage reply messages (they include read page reply for example), so it does not queue work to be done by crypto threads, but does that itself instead. It may or may not be the bottleneck of the input path, tests will provide facts, so far I do not have plans to change it, but it can be done of course if performance will suck.

After I finish crypto processing in both client (it has been written, but requires lots of testing with server) and server (just have started to recall how to work with OpenSSL. Well, I've read how HMAC works in OpenSSL, found it to be simple enough and then started to read how to parse binary data in LISP :) But anything which is interesting for me now, ends up in good results for all other projects), I will switch to something different for a while.
Some voices in the brain ask to be spread it in lots of interesting directions :)

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

POHMELFS crypto performance.

I've ran read/reread and write/rewrite tests as described in previous run, now with HMAC(SHA1) of all outgoing transactions (note, that reading response data is not yet encrypted and does not contain digital signature, server also does not support neither operation), essentially only writing should be affected by this, but I also ran reading tests for compelteness.

Results show zero performance overhead of the full data SHA1 hashing, but note that quite fast machines were used (2 3Ghz Xeons (2 physical and 2 logical CPUs, HT enabled) with 1 GB of RAM). All the time only two crypto threads were actively hashing data, since there are only two pdflush threads on this machine.





Writing is even faster with hashing, but results drifted around, so essentially performance is the same.

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

Mon, 23 Jun 2008

POHMELFS client got initial part of multithreaded crypto/checksum processing.

So far it only includes encryption and hash calculation for outgoing transactions. System has (mount option) number of threads per superblock, which are responsible for encryption/hashing (each thread has own crypto structure, so there are no additional allocations in the fast path, although I think they would not harm performance since should be small enough fraction on top of crypto processing overhead) and subsequent data sending, so original caller (like writeback/readahead code) will not block if there are ready threads, otherwise it will wait until some thread finishes its current crypto work.

I decided to implement kind of continuation for such transactions, when network sending code (which is supposed to be started after crypto processing) will be invoked from those threads, which performed crypto operations, and not returning back to originall caller context. For massively multiqueue NICs that should be a benefit, but so far I did not test its performance.
Next step is receiving crypto support and userspace changes.

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

Crypto processing in POHMELFS. OpenSSL vs GNU TLS.

If I did not miss something, GNU TLS (I never worked with it) supports very limited amount of ciphers and hashes, so it is not appropriate for filesystem data protection layer.
According to its documentation GNU TLS only supports AES, RC4 and 3DES ciphers and SHA1 and MD5 hashes. There is also only CBC chaining mode and several hash/cipher schemes.

So, POHMELFS server will use OpenSSL for data protection. Sooner or later OpenSSL will get hardware crypto support on Linux too (well, Linux crypto stack should first implement userspace API, which does not exist yet, although there is a work by Loc Ho from AMCC to add such support).

So far I decided to implement following protection scheme: checksumm or encryption will cover full transaction data, but will be applied by chunks:

• Transaction 'first-level' data, i.e. header and data immediately placed after transaction header. For all commands except page writing it will be finish.
• For write pages command, each header is generated dynamically and does not exist until data is really being sent, so crypto code will run over all pages and update checksum processing headers and data pages separately. Checkum update should be simple enough, since there are crypto helpers to update and finalize checksum, but encryption is more complex: I requires all chunks to be setup in advance in single scatterlist chain, with dynamic header generation it is too big overhead (it requires not only scatterlist allocation, but also header allocation just for encryption), so encryption will be done separately for headers and pages, and I will have to create some IV propagation scheme (like last bytes of previous unencrypted chunk will become IV for the next chunk, or something like that). I understand, that it may be not very secure approach though.
• Reading data back from server is simpler, since there are no transactions, and data will be encrypted/checksummed like in the first step above. It is possible, that it will force to increase network header structure a bit (32 or 16 bits to store size of the attached checksumm).

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

Thu, 19 Jun 2008

POHMELFS and HMAC/crypto operations.

As I found with distributed storage project, any communication channels, which involve huge amount of data transfers, have to have additional strong checksum embedded in the protocol, since TCP one is not enough in some cases. There are some options, like TCP MD5 signatures or IPsec transformations, but it is not always available.

POHMELFS will include ability to both encrypt whole data channel and/or only digitally sign all messages. This will be implemented on transaction level, so no higher layer code (like reading/writing data functions) will ever be affected.
POHMELFS will also have mount time self-configuration, i.e. client will send to server information about supported capabilities, requested by administrator, and if server does not support some of them (for example it can only do HMAC and not encryption, and both operations were requested at mount time), they will be dropped (and mount failed optionally). In the future it will be possible to extend it with additional flags if needed.

mount is not very convenient command to transfer crypto information (like binary keys) to kernel, so I use the same infrastructure as initial server group initialization (i.e. using POHMELFS existing configuration utility).

Support for HMAC and encryption will force server to depend on OpenSSL, but I do not think it is a problem. In some future time I can write autoconfiguration, which will allow to compile server without crypto support (and thus do not accept encrypted clients and do not check signatures) if there is no OpenSSL.

After crypto operations are implemented (I expect it to be finished this week), I will release as promised new netchannel version (and will remove unneded functionality like NAT), and add some interesting bits (like async processing) into distributed storage, so expect its new release soon too.

Stay tuned!

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

POHMELFS, NFS, Ext4 and XFS in iozone benchmark. Graphs.

Hardware used in testing: 4-way Intel E7520 system (two logical and two physical CPUs) 3Ghz 32 bit Xeons with 1gb of ram, Adaptec AIC7902 Ultra320 SCSI adapter with SEAGATE ST3300007LC 10k rpm 300 Gb testing disk. Its linear reading speed is about 90 MB/s.

Software used in testing: 2.6.25 kernels (on server and client), in-kernel async NFS server, userspace POHMELFS server.

Tests were performed with 8gb files (amount of ram was reduced to 1gb to eliminate caching influence) with different (from 8 to 1024 KB) record size. I ran write/rewrite, read/reread and random read and write tests.

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

CRFS got metadata cache coherency support.

Zach Brown has committed cache coherency support into CRFS repository.
Cache coherency protocol works by broadcasting special messages from server, and each client invalidates appropriate inodes (and dentries if needed) before sending back a reply.
POHMELFS uses a bit different mechanism: client does not send acks back to server, so all such messages are kind of advisory-only, but I did not yet complete (well, I did not even think about this problem this week) locking design, so it can change.

Main problem with sync cache coherency support is its absolute non-scalability. While number of sage cases might require such behaviour, I expect that if not major, but noticeble part of users do not want perfromance degradation as a price for posix-like coherency expectation. This approach is worse that write-through cache, since there is whole round-trip of the cache coherency request instead of just data sending during its writing. Single direction sending is faster than sending+waiting, so for me it is still a questionable approach.

I will think a lot of this problem later this week(end), so that solution would satisfy both high-perfomance and safety camps (although at some degree only I think).

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

Fri, 13 Jun 2008

The latest iozone benchmark of POHMELFS, NFS, XFS and Ext4.

1Gb of RAM, 8Gb files. SEAGATE ST3300007LC 10k rpm 300 Gb on Adaptec AIC7902 Ultra320 SCSI adapter.

Performance in KB/s.

NFS:

                                                   random  random
     KB  reclen   write rewrite    read    reread    read   write
8388608       8   53210   57769    24304    24448    1360    4775
8388608      16   54577   57481    23871    24080    2592    7937
8388608      32   54736   56203    24015    24114    4738   12637
8388608      64   52075   54051    23653    23555    7610   18475
8388608     128   52307   54636    23305    23375   13017   26584
8388608     256   52189   53030    23585    23531   15615   34390
8388608     512   52938   54063    23709    23882   17524   42781
8388608    1024   57458   57006    24187    24292   29701   43892

                                                   random  random
     KB  reclen   write rewrite    read    reread    read   write
8388608       8   66473   63721    74232    74288    1103    4953
8388608      16   52604   62339    73423    74259    2001    8438
8388608      32   53278   62283    73497    74115    3360   13849
8388608      64   56931   61370    73135    74077    5076   21063
8388608     128   59419   62743    72736    74122    8068   30279
8388608     256   60861   63094    73284    74554   10848   38869
8388608     512   59438   62081    73329    74441   17290   48722
8388608    1024   62790   62130    73322    74100   27741   46470

                                                   random  random
     KB  reclen   write rewrite    read    reread    read   write
8388608       8   75124   60560    77672    77797    1860    5059
8388608      16   75044   60036    77754    77775    3601    8772
8388608      32   75958   62038    77593    77765    6821   14781
8388608      64   74728   59384    77688    77782   12475   23228
8388608     128   74889   59676    77731    77736   21734   32241
8388608     256   75022   59285    77676    77718   28833   40324
8388608     512   74885   59187    77653    77713   40013   48057
8388608    1024   74838   64217    77796    77765   55100   46104

                                                   random  random
     KB  reclen   write rewrite    read    reread    read   write
8388608       8   72107   73017    77276    77335    1849    5015
8388608      16   72276   73849    77304    77287    3577    8666
8388608      32   72680   73647    77284    77326    6755   14394
8388608      64   71965   74287    77327    77288   12366   22513
8388608     128   72660   73864    77207    77343   21617   31160
8388608     256   72813   74058    77296    77338   28652   42003
8388608     512   72985   73317    77284    77343   40572   50619
8388608    1024   72184   74131    77264    77250   55649   50365

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

New POHMELFS release: doing it wrong fast is at least better than doing it wrong slowly.

Via Ashleigh Brilliant and bits of Tullamore Dew.

Here we go, short changelog for this release:

• Read requests (data read, directory listing, lookup requests) balancing between multiple servers.
• Write requests are sent to multiple servers and completed only when all of them sent an ack.
• Ability to add and/or remove servers from working set at run-time from userspace (via netlink, so the same command can be processed from real network though, but since server does not support it yet, I dropped network part).
• Documentation (overall view and protocol commands)!
• Rename command (oops, forgot it in previous releases :)
• Several new mount options to control client behaviour instead of hardcoded numbers.
• Bug fixes.

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

Wed, 11 Jun 2008

Preparing for the next (last non-bug-fixing?) release.

Essnetially that's it, I belive really most of the features I wanted from network distributed parallel filesystem, which should live in client, are already implemented in POHMELFS.

Client has following (if did not forget something interesting, listed only interesting from parallel point of view) features:

• Automatic failover reconnect to the same server.
• Run-time addition/removal of the servers from the working set (only via userspace command, since server does not support that yet, but addition is trivial).
• Coherent data and metadata cache
• Transactions support. Full failover for all operations. Resending transactions to different servers on timeout or error.
• Load balancing of reading (directory reading and lookups inclusive) requests and simultaneous writing to all servers in current working set.

• Distributed data coherency protocol like PAXOS for server data, stored on multiple machines.
• Ability to mirror data itself on multiple machines.

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

Fri, 06 Jun 2008

POHMELFS development status.

POHMELFS got ability to add/remove servers in run-time (although not via network command, since I do not know, how to test it yet), but via netlink interface. The same message can be passed via network though, so it will be simple to extend.
Also, POHMELFS got readahead support via ->readpages() callback. I removed AIO reading from POHMELFS in favour of readahead and got excellent result in sequential reading: 3-3.5 times faster than NFS and essentially reaching disk IO bandwidth (a bit less though), but random reading dropped to miserable numbers.
Also rewritten reading method should provide better balanced between multiple servers capabilities for the system, but it will not show any benefit in single-threaded iozone benchmark, since it reads data via single call to read(), which gets sequential data access, which in turn is faster than network bandwidth. So multithreaded load should greatly benefit from read balancing, but I did not yet test that.

I ran sequential read/reread, write/rewrite and random read/write tests for XFS, Ext4, NFS (over XFS) and POHMELFS (over XFS) with 1Gb of RAM and 8Gb of test files (to eliminate VFS caching influence) with 8Kb to 1Mb record size.
Results exist in text files in standard iozone output format, but since I'm learning LISP I decided to write a graph generator (via gnuplot) using my very basic knowledge of this language, so nice graph results can take a while...

Also, tomorrow morning I will flight away to my friends marriage and will only return monday 9. I will not have internet access there, only lots of fun.

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

Wed, 04 Jun 2008

Optimized POHMELFS transactions.

Now they eat less memory, and single writing transaction can accumulate up to 1024 pages. This can be further tuned especially for small requests mixed with sync. Currently writing transaction is allocated for its maximum size, and then pages pointers are written to the allocated area, so if number of dirty pages requiring writeback is small, quite lots of space will be wasted.
It is a task for the next optimization, nevertheless currently sequential writing is only limited by disk throughput or network bandwidth in case of multiple servers, since link is shared between machines, so effective bandwidth becomes equal to GigE/number of servers, or about 60 MB/s in my environment with two servers and single client.

Also, reading path was not changed at all (only transaction internals) - there is still no readahead and new transaction is allocated for each page to be read. Nevertheless, see how reading was improved: POHMELFS not only outperformed NFS again, but reached disk bandwidth limit already for 16Kb requsts (almost two times faster than NFS). Table shows IO throughput in KB/s.

                                                    random  random
      KB  reclen   write rewrite    read    reread    read   write
 8388608       8   74058   68392    40130    79509   43588    4818
 8388608      16   62332   66978    73714   122074   42160    8434
 8388608      32   64775   67073   109357   171139  145416   14183
 8388608      64   66962   66602   147350   217323  227962   22257
 8388608     128   67724   67133   185574   266855  321060   32681
 8388608     256   68233   67922   201591   283567  474657   40944
 8388608     512   68339   66514   213513   295995  646897   50303
 8388608    1024   67744   67384   220858   297748  676582   48796

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

Mon, 02 Jun 2008

AppArmor and path-based security approaches vs object bound policies.

- So again, can you offer an alternative?
- Just give up on this dumb idea completely.

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

As promised, let's see shadowed miserable POHMELFS results.

Usually you will not see bad benchmark results for developing technology, but any such result is actually a _very_ good result for work-in-progress and not yet completed system. It allows to see how new proof-of-concept code can be comparable with already completed tuned and optimized system.
Conclusions from such test results in a really superior decisions.

Let's compare iozone read/reread, write/rewrite and random read and write for POHMELFS and NFS with 8Gb test files different record size (from 8Kb to 1Mb) on XFS over the GigE link.
I described hardware and local iozone benchmark results in details previously.

Now its time for network tests.
Async NFS in-kernel server results.

						    random  random
      KB  reclen   write rewrite    read    reread    read   write
 8388608       8   60969   57743    39705    97031  464898    5160
 8388608      16   59925   57402    39045    98269  641388    8827
 8388608      32   58094   55263    39075    94654  775064   14389
 8388608      64   58168   57156    40306    98639  868796   22360
 8388608     128   58908   56573    40392   100018  941509   33211
 8388608     256   59444   56446    40842   102503 1030451   41576
 8388608     512   60280   57686    39835    97879 1042570   49858
 8388608    1024   60817   57886    40886    96646  851175   47993

						    random  random
      KB  reclen   write rewrite    read    reread    read   write
 8388608       8   70073   64232    12518    14817   40334    5079
 8388608      16   63984   67948    31976    19106   41462    8702
 8388608      32   67250   63440    47506    38657   75908   14357
 8388608      64   69970   66198    41899    29566  136294   21385
 8388608     128   69838   68523    76232    33971  222909   30946
 8388608     256   70012   66439    69125    58223  330886   40685
 8388608     512   70946   68291    76460    58738  428881   51001
 8388608    1024   70985   64958    76317    59561  421973   48531

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

Fri, 30 May 2008

Local filesystem randomg read/write performance. POHMELFS parallel testing.

I promised to publish POHMELFS parallel processing results yesterday, even if they are miserable. Unfortunately there are no interesting results at all. In the released version POHMELFS is 32bit only, since it does not have special ->open() callback which forces to open files with O_LARGEFILE flag to support more than 4Gb (actually only 2Gb, since kernel uses signed size_t, which is only 31 bit large) sizes and superblock maximum size is set to 32 bits, so all 32 bit results are not very interesting, since having 2Gb/s random read speed is really stupid sentence, since all reading happend from the cache.

While results with more than 2Gb are... Let me first show you how XFS and Ext3 behave in case of random writes.

A short preface.
Hardware used in testing: 4-way Intel E7520 system (two logical and two physical CPUs) 3Ghz 32 bit Xeons with 8gb of ram, Adaptec AIC7902 Ultra320 SCSI adapter with SEAGATE ST3300007LC 10k rpm 300 Gb testing disk.
Its linear reading speed is about 90 MB/s. Dmesg:

scsi0 : Adaptec AIC79XX PCI-X SCSI HBA DRIVER, Rev 3.0
        <Adaptec AIC7902 Ultra320 SCSI adapter>
        aic7902: Ultra320 Wide Channel A, SCSI Id=7, PCI-X 67-100Mhz, 512 SCBs
scsi 0:0:2:0: Direct-Access     SEAGATE  ST3300007LC      0003 PQ: 0 ANSI: 3
 target0:0:2: asynchronous
scsi0:A:2:0: Tagged Queuing enabled.  Depth 32
 target0:0:2: Beginning Domain Validation
 target0:0:2: wide asynchronous
 target0:0:2: FAST-160 WIDE SCSI 320.0 MB/s DT IU QAS RDSTRM RTI WRFLOW PCOMP (6.25 ns, offset 63)
 target0:0:2: Ending Domain Validation

                                                   random  random
     KB  reclen   write rewrite    read    reread    read   write
8388608       8   73671   64052    77565    80107   35281    5085
8388608      16   74437   66095    77611    80065   66854    8808
8388608      32   74683   66780    77564    80202  121442   14576
8388608      64   74936   66908    77537    80372  215377   22583
8388608     128   74928   68598    77542    80247  339304   32280
8388608     256   73609   69615    77534    80143  365081   40571
8388608     512   73763   69830    77547    80317  420704   48501
8388608    1024   73940   69474    77602    80065  406266   47295

                                                   random  random
     KB  reclen   write rewrite    read    reread    read   write
8388608       8   69593   74200    77324    81340   35538    5088
8388608      16   66745   70038    73676    77271   65715    8704
8388608      32   68253   70320    73652    77258  121690   14469
8388608      64   68421   71291    73653    77042  209629   22005
8388608     128   68438   71340    73658    76988  332021   30381
8388608     256   68921   71254    73651    76912  435586   40683
8388608     512   69079   71728    73551    76815  549136   49298
8388608    1024   66611   71217    73683    76581  552459   49220

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

Wed, 28 May 2008

POHMELFS got read balancing between multiple server and simultaneous write to them.

I hate laziness, but sometimes drop into that hole... So last couple of days I just stupidly wasted by time (well, I read Lisp and failed to find GTK binding for CLISP, made some code and kernel bug fix, but that does not count). Today lazyness started to be really boring, so I made some small progress in POHMELFS parallel processing.

It got ability to send transactions to multiple servers by default and balance reading between them (so far it does it always from the first server, in case of error it switches to second, but it is trivial to change). This was implemented via special routes for each transaction, which are stored per network state, so if one of the servers did not answer, we would not resend data to others. It also makes trees smaller, which should allow faster reading in case of lots pending writing transactions.
Code is in testing stage currently, I will complete read balancing tomorrow and test it against multiple servers on different machines, when data is placed on disk, so that random access would be slow. Having two servers I exect to get linear speed increase. If test will be disk IO bound, it is possible to add multiple servers on the same machine, so that each server would run on its own disk (I have two resonable fast SCSI disks on each testing machine).
Results will be published here of course (well, even if they are miserable :).

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

Sun, 25 May 2008

New POHMELFS release. Full transaction support. Data and metadata cache coherency.

Irish Tullamore Dew helped this POHMELFS release to see the light.

Short changelog:

• Full transaction support for all operations (object creation/removal, data reading and writing). Data reading transactions are not optimal yet and will be improved in the next release (although fast).
• Data and metadata cache coherency support. More details on how this is implemented one can find in appropriate section.
• Transaction timeout based resending. If given transaction did not receive reply after specified timeout, transaction will be resent (possibly to different server).
• Switched writepage path to ->sendpage() which improved performance and robustness of the writing.
• Preliminary support for parallel data processing. Code to write data to multiple servers in parallel and balance reading between them was imported, but is not used right now.
• Fair number of bugfixes.

• Improved reading transactions.
• Server redundancy extensions (ability to store data in multiple locations according to regexp rules, like '*.txt' in /root1 and '*.jpg' in /root1 and /root2.
• Client parallel extensions: ability to write to multiple servers and balance reading between them. Code was imported to the current version, but not enabled yet.
• Client dynamical server reconfiguration: ability to add/remove servers from working set by server command and from userspace.
• Start generic server distribution development.

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

Sat, 24 May 2008

This was supposed to be POHMELFS release day.

But no, it is scheduled for tomorrow because of the very interesting way I decided to implement reading transactions. The way it works right now is quite miserable, so I want to clean things up and make a really good patch.

Page reading code will create single transaction for the bunch of pages and will schedule next one if pages are not yet received instead of waiting for transaction to be completed, and only wait at the very end (if needed). With addition of async copy from receiving kernel thread into reading userspace via copy_to_user() (in todo), this will became the fastest possible way of doing reading over the net I think.

So far changelog contains following items:

• Full transaction support for all operations (object creation/removal, data reading and writing). Data reading transactions are not optimal yet and will be improved in the next release.
• Data and metadata cache coherency support. More details on how this is implemented one can find in devel section.
• Transaction timeout based resending. If given transaction did not receive reply after specified timeout, transaction will be resent (possibly to different server).
• Switched writepage path to ->sendpage() which improved performance and robustness of the writing.
• Fair number of bugfixes.

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

Wed, 21 May 2008

iput() locking in POHMELFS.

iput() is a very tricky call in Linux VFS, besides the fact that it drops inode when its reference counter reached zero, it also waits until all associated pages are flushed to storage too.
POHMELFS uses singler per network state (network connection structure) thread, which only reads async replies from the server, so it is possible, that reply which requres iput() (for example create command reply) will happend in parallel with object removal, so inode will be deleted, but yet not freed. When reply is received and iput() called, it will try to free inode and wait until all associated to its mapping pages are synced. But page sync happens on reply to another command (consider for example several writeback transactions), which can not be processed, since thread is waiting them to be completed. This problem can not be fixed by introducing multiple threads, since each one can be exactly in the same situation simultaneously.

In turn we should not allow to grab inode and free it in the receiving path. This is ok for writeback transactions, since inode can not be freed until pages are synced, so just by holding pages we are able not to lock, but object creation for empty files or directories does not have pages attached, so they have to be synced with special transaction. There still can be a problem with empty file though - some pages can be attached and it can be removed while system waits for creation transaction complete, but actually we do not need to know about that - we shuold not grab inode it all, since transaction already contains all needed into, namely inode number, so we can lookup inode (if it still exist) and mark it as created without need for lock-prone grab/put.

This bit took me last three days, during which POHMELFS moved to non-blocking receiving and timeout-based sending (and returned back), it got scanning 'watchdog' which resends trasactions if they were not acked after some time and eventually dropes them if they still does not get a reply, POHMELFS got couple of new operations supported and likely something else to existing set of features implemented to date (full transaction support for all operations and data and metadata coherency protool were added for the next release).
New release is scheduled for the end of the week, and there is no readpage transaction support yet...
So, stay tuned!

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

Sat, 17 May 2008

POHMELFS got full data and metadata cache coherency support. Transaction support for majority of the commands.

linux-2.6.pohmelfs$ git-diff-tree -r --stat 21549d0a101 master
 fs/pohmelfs/dir.c   |  108 ++++++--------------
 fs/pohmelfs/inode.c |  279 ++++++++++++++++++++++++++++++++++++--------------
 fs/pohmelfs/net.c   |  216 ++++++++++++++++++++++++++++++---------
 fs/pohmelfs/netfs.h |   43 +++++++-
 fs/pohmelfs/trans.c |   55 +++++++++-
 5 files changed, 484 insertions(+), 217 deletions(-)

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

Fri, 16 May 2008

Metadata cache coherency support in POHMELFS.

Client:

$ ls -lai /mnt/test
3 -rw-r--r--  1 root root 94208 2008-05-16 22:27 test
$ sudo chown zbr.zbr /mnt/test 
$ ls -lain /mnt/test
3 -rw-r--r-- 1 2319 1002 94208 2008-05-16 22:27 /mnt/test

fserver_get_client_data: thread: 3085847440, cmd: 8, id: 0, start: 2, size: 94, ext: 0.
fserver_transaction: thread: 3085847440, trans: 0, size: 94, sub: cmd: 10, id: 3, start: 0, size: 70, ext: 6.
fserver_inode_info: path: '/test', size: 94208, mode: 100644, uid: 2319, gid: 1002.

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

Thu, 15 May 2008

POHMELFS distributed plans.

After healthy discussion started after my announcement of the second POHMELFS release, its time to highlight main ideas settled in the thread.

First, POHMELFS will be moved into parallel distributed filesystems, but still being very good as network filesystem. In particular, that will include ability to read data from one of the connected server (not particulary from currently active, how its done right now), writing will happen to all connected servers simultaneously (and transaction will be committed after all servers returned completion acknowledge).

Protocol will be extended to support dynamic addtion and removal of the servers to/from currently connected group. Probably there will be some kind of a status messages for servers (i.e. going offline, do not send me data, or I'm becoming slow, do not read from me and so on). It will be done in addition to cache coherency messages (I'm yet to implement, but because of other tasks, this was a bit postponed, probably to weekend), which will include two types of requests: page invalidation and inode update (that will also mean that POHMELFS will start supporting attributes (maybe even extended), right now it doesn't :). Such cache coherency protocol should scale better than classical MOSI (and its derivatives) and particulary better than pNFS spec proides (leases to operations for some servers), since it is still possible to work in parallel with the same file, especially without any overhead of data processing does not cross different client boundaries, but it has to be tested in practice.

POHMELFS server will be extended to support distributed facilities. Very likely it will be some kind of PAXOS algorithm, although probably in its very limited mode for the beginning. So far it will be really simple, so that I could touch all its corner cases and found optimal development strategy.

All client extensions are rather not that complex, although not always trivial, so that should not take too much time, so probably you will get something interesting soon.
Server extensions will be a bit slower, since I will start essentially from the distributed system ground and gradually move upstairs.

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

Tue, 13 May 2008

New POHMELFS release. Transactions, performance, failover.

Irish Jon Jameson (6 years of experience, really good stuff) brings us this new POHMELFS release.

Main features include:

• Fast transactions. System will wrap all writings into transactions, which will be resent to different (or the same) server in case of failure.
• Failover. It is now possible to provide number of servers to be used in round-robin fasion when one of them dies. System will automatically reconnect to others and send transactions to them.
• Performance. Super fast (close to wire limit) metadata operations over the network. By courtesy of writeback cache and transactions the whole kernel archive can be untarred by 2-3 seconds (including sync) over GigE link (wire limit! Not comparable to NFS).

• Full transaction support for all operations (only writeback is guarded by transactions currently, default network state just reconnects to the same server).
• Data and metadata coherency extensions (in addition to existing commented object creation/removal messages).
• Server redundancy.

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

Mon, 12 May 2008

Fast POHMELFS transactions.

With new transactions and new waiting mechanism (see below) system now untars the whole kernel tree in less than 3 seconds over the GigE link (including subsequent sync, which takes less than second always), while async NFS (remote side is tmpfs in both cases) performs that in a bit more than 30 seconds. In addition POHMELFS write speed is 125 MB/s (wire limit) vs. less than 90 MB/s in NFS (dd from /dev/zero with 1 MB block size and 1000 blocks).

That's what I call a good result.

Transaction mechanism invoked in writeback path is now completely async too, i.e. it does not wait until remote side confirms that transaction was received and processed, but writeback does not drop transactions after sending function returned, instead it stores it in the in-flight storage and proceeds with the next one. Transaction can accumulate up to 90 pages in a single frame.
When reply is received, async thread searches for given transaction and complete it (unlocks page, although it can be done in writeback, since page is being copied, cleanup writeback bits, drops it from appropriate radix tree and drops reference counter). If transaction was not sent due to some error it will be tried to be sent to different servers, if some error was returned from the server, it will be resent to different ones. Since original writeback path does not know about transactions in-flight anymore, any timeout has to be checked by dedicated thread (or workqueue), which will detect too old transactions (by simply checking them from the beginning, since each new transaction has incrased id) and resend them to remote servers.

There is a small problem though - if object size is more than single transaction can accumulate (90 pages), it will be split into several transactions, where first one will contain object creation command and some data to be written, while others will contain only data. If server runs multiple threads per client (default is one though), it is possible that not first transaction will be processed first, so server will write some data into non-existent file, so transaction will fail. There are two ways to fix this isuue: either wait in writeback on client while creation transaction is completed, and then send all others like described above, or add creation command into every subsequent transactions until object is created on the server (special bit is set on local inode in that case). Likely the latter is better case.

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

Wed, 07 May 2008

Fast transactions in POHMELFS.

POHMELFS just switched to faster transactions allocated one-by-one with even smaller overhead (although it does not use kernel_sendpage() for page sending yet, it copies data).
System does not serialize after all transactions are completed (it waits after each one), but with new transaction allocation it is 1.5 times faster: 98MB/s vs. 64MB/s, note that without waiting for transaction completion it gets full wire speed of 125MB/s with 1500 byte MTU. And it is with highmem pages and thus slow kmap() of each one, and unmap after completion. I do not use ->sendpage() since it will force to split proper set of iovecs into mixed calls of kernel_sendmsg() and kernel_sendpage(), which I want to avoid so far. Now it is (again) faster than NFS, but I want to move further.
So, solution is rather trivial: wait until several transactions are completed. There is the whole infrastructure already there - in-flight transaction storage, per-transaction completion and destruction callbacks, proper reference counting and async completion.
Still only writing transactions are used (i.e. reading/lookup and others will not redirected to different servers).
There are some bugs of course, but that's the first development version after all.

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

Mon, 05 May 2008

POHMELFS transaction support. Failover (re)connection to different servers.

POHMELFS just got full transaction support. So far it is only used in ->wrteipages() callback, which is invoked by writeback mechanism. POHMELFS uses lazy transaction support, namely it waits after each transaction, which includes header and data to be written for at most 14 pages, 14 is a magic number of pages, which corresponds to struct pagevec size, used by generic writeback, transaction size is limited by mount option and is 32 pages by default. Performance was dropped from 125 MB/s down to 64 MB/s, which is not acceptible. Main problem is of course waiting for transaction to be completed (i.e. completion message from server). There should not be per transaction waiting, instead writeback has to allocate as much transactions as needed and proceed one after another, and only start waiting for them, when there are no more pages to be written. This is the next task.

Transaction mechanism allows quite simple reconnection to different master servers in case of failure, and rollback of the failed transaction. For example one can provide different number of main servers (which have to be in sync with each other and be able to be synchronized themselfs, or they just can use shared storage), so POHMELFS client will switch between them if current one has failed. System will detect it and reconnect, if reconnect fails, next server will be used and the whole transaction will be resent there.
It is also possible to write transaction to different server on demand (it may or may not to be connected already, but it has to have address structure, so far it is only obtained during pre-mount configuration), which is a prerequistic for parallel data processing. One can create a simple patch to write transactions one after another to severs in round-robing fasion.

Right now only write transactions are used (and can be combined with object creation if needed), read ones are pending as long as multiple parallel transactions (which is not complex, but main task is how to wait them all to be completed, very similar code is used in pohmelfs_aio_read()).

There is also pending task of cache coherency support (server side originated messages to clients, which used the same pages, which another client is writing into, also including metadata coherency messages like uid/gid/inode size and other changes), it is not that complex task, and mostly requires server modifications.

Stay tuned!

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

Fri, 02 May 2008

Design of the POHMELFS transaction model.

It is heavily based on how netlink is implemented in Linux kernel. Besides the fact that it is likely the most ugly and complex protocol among communication models supported by the kernel, it is exactly the most effective, extendible and feature rich one.
This model is based on the attributes, which are embedded into the message. Each attribute has header, which includes size of the attached data. So, one can put effectively unlimited amount of data into any message (limited only by size field and practical assumptions of the communication), and it is possible to create message, which will contain any number of different attributes.
The main problem of the netlink is its padding and alignment ugliness. Protocol tries to get the every bit out of the communication, so there is huge amount of very hairy things there.

I like to drink and (un)fortunately I got pretty bad quality drinks some times, but I'm absolutely sure, when Alexey Kuznetsov designed netlink attrubute alignment policies he had really bad hangover after likely the ever worst crap he drunk.

So, netlink attributes are very ugly, but you can extend it how you like.
The same applies to POHMELFS transactions.

You can put any new attribute into the transaction in a very trivial manner (I worked with netlink alot, even created kernel connector to simplify kernel development side, so I know that taste), although transaction size is limited, it is controlled only by mount option (default is 32 IO vectors each one of PAGE_SIZE (4k on x86) in one transaction).

Thus one can easily implement for example any protocol security labeling, just add new per-packet attribute.

So, it is easily possible to infinitely extend communication protocol with full backward compatibility.

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

Tue, 29 Apr 2008

POHMELFS transactions and ACID.

POHMELFS just got initial transactions support and ability to connect to multiple master servers. Master servers are those, which will say, where data is placed. Essentially they are the same severs which may provide that data, but main server addresses are provided during pre-mount configuration time, and data server addresses will be provided by main servers (if main ones will not want to return data) in run-time.
Also main servers can be used to request data in parallel or to switch between them, when curently active one has failed.

So far it is a theory, practice is rather miserable: POHMELFS client connects to multiple servers, but works with only one. Errors are detected, and switch to the next server can happen, but it is not done. Since there is a serious problem with this approach: neither server nor client support ACID for data being written.

Here we come to transaction introduction: it is multiple commands wrapped into single atomic operation. In case of error during transaction write, the whole one will be resent to different server (or the same one after reconnect). This is rather simple (although transactions are not supported by server and client does not wrap any command into it yet), but it still does not solve ACID problem.

Since POHMELFS has writeback cache, all its writes never reach server, instead writeback is scheduled by the system, and it starts writing pages to the server. Current POHMELFS implementation uses only ->writepage() method, which is invoked for each page. It does not require server to return explicit acknowledge, that page was written, instead it relies to underlying transport protocol (like TCP) to handle guaranteed delivery, so data can be queued somewhere when connection was dropped, so POHMELFS client does not know if data was really written or not. Having per-page acknowledge can fix ACID problem realy trivially, but that may (or may not) end up with severe performance degradataion. As a better solution I consider own ->writepages() implementation, where each transaction will contain multiple pages to be written and thus smaller amount of explicit acks from server to be received, and thus smaller performance degradataion. In case of failure whole transaction has to be resent to different server of course.

Server does not support data mirroring to multiple root directories yet, so actually not too much is implemented from above description, but transactions and multiple server connections exist and soon client will get support for reconnection and proper transaction processing.

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

Sun, 27 Apr 2008

Detailed POHMELFS roadmap.

Transaction support will be added into kernel client. It is possible that it will be exported to userspace (thus it will be synchronous write-through operations).
Also kernel client will get locking support (fcntl() ones first, then more fine-grained ones), this is different from byte-range read/write locking, which will be done on server. It is possible to export it to client too (and will be part of POHMELFS locking API actually, which will be used for fcntl() too).
The simplest case is data invalidation in client's cache (i.e. if one client issued a writeback for given page, it has to be marked as not up-to-date on other clients). Likely it will be done at the beginning of the next week. So far it will be the last cache coherency item. Task is relly simple because of asynchronous processing of all data in kernel client. Server will have to store not only index of directories to watch for object changes there, but also per-object set of pages, read by client, so that appropriate users could be notified, that page is no longer up-to-date and has to be refreshed.

Userspace server will get parallel and distributed facilities. Parallel processing will be done first by allowing lookup and readdir callbacks return inormation about objects, which will contain address of the server where object is actually located, so that server could read, write or check status there. So far the whole file will be stored on a server, i.e. for the first implementation there will not be a possibility to store half of the file on one server and another half on different one. Then it can be extended.
Server will get ability to store data on different root directories (so that client was not able to see shadow copies). There will be simple regexp policies for data storing, for example '*.jpg' has to be stored in root1 and root2, '*.txt' only in root1 and so on. Each root directory can be local or remote mounted one, userspace does not care about this issues.

Main part is already completed: I have a vision of what system has to provide and how it will look like, so with good design of the low-level mechanisms it becomes a doable task for the predictible timeframe.

Stay tuned!

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

Fri, 25 Apr 2008

POHMELFS release.

Vodka and beer together are glad to provide a new POHMELFS release for you.

POHMELFS stands for Parallel Optimized Host Message Exchange Layered File System.

This is a high performance network filesystem with local coherent cache of data and metadata.
Its main goal is distributed parallel processing of data. Network filesystem is a client transport.
POHMELFS protocol was proven to be superior to NFS in lots (if not all, then it is in a roadmap) operations.

Basic POHMELFS features:

• Local coherent (notes 1 and 2) cache for data and metadata.
• Completely async processing of all events (hard and symlinks are the only exceptions) including object creation and data reading.
• Flexible object architecture optimized for network processing. Ability to create long pathes to object and remove arbitrary huge directoris in single network command.
• High performance is one of the main design goals.
• Very fast and scalable multithreaded userspace server. Being in userspace it works with any underlying filesystem and still is much faster than async ni-kernel NFS one.

• Server extension to allow storing data on multiple devices (like creating mirroring), first by saving data in several local directories (think about server, which mounted remote dirs over POHMELFS or NFS, and local dirs).
• Client/server extension to report lookup and readdir requests not only for local destination, but also to different addresses, so that reading/writing could be done from different nodes in parallel.
• Strong authentification and possible data encryption in network channel.
• Extend client to be able to switch between different servers (if one goes down, client automatically reconnects to second and so on).
• Async writing of the data from receiving kernel thread into userspace pages via copy_to_user() (check development tracking blog for results).

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

Thu, 24 Apr 2008

Second POHMELFS release.

Is scheduled for tomorrow, today I have to prepare myself for it. The whole idea and implementation started during fun new year vacations, so I have to repeat process at least at some degree...

This release will not include direct writing to userspace from async thread, since this approach happend to be really non-trivial. What I described for the page fault handling works only for the first fault, when page is populated into the table, it can be referenced and written into and thigs just work. Problem happens when the same page used for the second read (i.e. new try from the userspace, for example if to increase size of written data to more than two pages, 'cat' will use the same two pages to read data). With the second write from the kernel there will be page fault again, although page exists in table, and fault can not be handled (at least its reason will not be removed, since it will happen again and again), since page table entry looks really good for the system, but not for the CPU.
I checked two cases: usual copy_to_user() from kernel on behalf of userspace thread invoked a read syscall, and the same code, but copy was performed from the different thread. Page table entry (pte) looks very similar in both cases (in regards of all flags at least), but fault happens for the second write into the same page always, when thread's mm context was changed to point to original userspace one.
This does not change if userspace thread was or was not scheduled away from its CPU.
Difference from get-user_pages() in this part is mainly the fact, that resulted page is locked in the kernel (by increasing its reference counter at least), but I still want to produce the same behaviour as usual page fault during copy on behalf of userspace thread.
So, I stuck with this problem, but since it is very interesting I will find a solution.

Meanwhile, this release will include following things:

• POHMELFS client. Full client side caching. Async operations for all major events (not including copy_to_user() hack described previously, but just async notifications an copy on behalf of original userspace thread). Support for usual files and directories only, special files like device files or pipes are not interesting at this point, and are quite simple to implement, but so far there is no need for that. Client has support for object creation/removal cache coherency messages.
• POHMELFS userspace server. Onject creation/removal cache coherency messsage broadcasting will be commented out, no locking.

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

Tue, 22 Apr 2008

Cache coherency in POHMELFS. Continue.

While moving home I thought a lot about cache coherency issues. While we belive that NFS has coherent cache, since it is somewhat write-through, its cache actually is not synchronous, since between object creation and moment when other clients see new object really lot of time can run, for example when client, which create an object, has slow link... So, object creation and removal should not be synced to other clients during writeback on one of them, instead clients which are interested in object perform a lookup, which may or may not return object, this is not a race or cache non-coherency, this is usual multithreaded environment without client's synchronization.

What we really care about, is data consistency on the server. When we have multipage write, which overlaps with another write from different client, we should not read data back from the middle of the transactions. Locking the whole file is not an issue, instead proper byte-range (page-range actually) locking has to be implemented. I already have a prototype, but have to check it in real life.

So, other competing projects may or may not follow my way and drop creation/removal/stat coherency from the TODO list (afacs, no one implemented that yet :) based on my analysis and concentrate on server read/write locking.

And I will start some bits of VM hacking: plan is to implement generic enough (well, working on x86 for start :) mechanism to copy data from different (i.e. not that one which started a syscall) thread to userspace, while original one sleeps in syscall, via copy_to_user(). Likely it will be somewhat similar to what I did for zero-copy userspace sniffer and how get_user_pages() work.
Result, which has to be as fast as usual copy_to_user(), otherwise it is not interesting solution, will be used in POHMELFS client and its async reading.

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

Mon, 21 Apr 2008

Cache coherency in POHMELFS.

Example:

Client 1			Client 2
# ls -a /mnt/
. ..
				ls -a /mnt
				. ..
				echo qwe > /mnt/asdasd
				sync
ls -a /mnt/
. .. asdasd
rm -f /mnt/asdasd
sync
ls -a /mnt/
. ..
				dmesg | tail -n1
				pohmelfs_remove_response: parent: 2, path: '//asdasd'.
				ls -a /mnt
				. .. asdasd