Future for Mimir: C
Background:
Mimir is a distributed file system that we created for our Senior Design. It used FreePastry which is written in Java and overall was fairly successful. Files could be saved, retrieved, deleted. There was user authentication and overall it worked OK in a stable environment. One of the issues that it had however was speed issues doing the encoding and interacting with the network stack. The encoding issue had a lot to do with java performing extra casting for the XOR operations that were key to our erasure code. The network issues were mostly due to not being fully asynchronous and how we were using the network. The network proved to be a large problem particularly with saving a file though also with retrieving a file. After first trying to use the overlay network directly for saving a file we resorted to polling the network for the nodes and then sending the data through a direct tcp socket to the individual connections. This was an issue because we had to 1 open a lot of connections and 2 loop over them to save the data.
Update:
Since then i have come up with a way to distribute the file evenly over all of the nodes without incurring a bottleneck at the top of a tree. To do this when a node wants to send a file out it picks a random ID in the ID space and also selects it’s compliment( ie if the id space is a circle the node 180 degrees from it.) The node then sends half of the blocks of data to node A and half to node B. node A and be split up their half of the circle into halves and each half then repeats this until they pick themselves for a given node(ie they are the only node in their remaining id range.
This has some benefits first it means that the originating node has to do fewer lookups to save the file and does not need to know anything about the sate of the network. Secondly as long as the node id’s are evenly distributed in the space the file will be evenly distributed.
n the downside this means that the speed of saving the file is determened by the speed of the originating node to nodes A and B. However our design case is for LANs so this should not be an issue and we should beable to better saturate the network.
Note: There is no reason to limit the tree to be binary it could be split into any number of pie pieces.
To help achieve this as well as even grater speed we are planing to use Chimera which is the successor to Tapestry and is written in C. This will allow us to perform the XOR operations using various processor optimizations as well as assembly if needed without the pain of the Java C bridge. In addition this should make our code much smaller!
No commentsFinal Design Report/Notebook
Sorry i lost the signed version and unsigned versions of our team contract.
Also as usual all of our documentation can be found at http://compsciguy.homeftp.org/svn/srdesign/Documentation
No comments
Results and Graphs
Here are a few charts of our progress we have made. In the first chart we show what we had at the beginning of our development in the second chart we show where we are now. The y axis was how much data was used to rebuild and the x axis is the trial number.
As you can see in the first chart we have a lot of points above the 50% mark meaning that if we lost half the data we would not be able to rebuild. In the second chart you can see there are none over that mark. The points tend to be somewhat normally distributed meaning even in the second chart there is a chance that it would take more data to rebuild but we can say with certainty of 99.9998 (from experimental data) that we can rebuild with 50% data loss.
The changes made to the robust soliton distribution are extensions from ones done at Helsinki and at UC Santa Barbara in that we added at least one spike and changed the initial low degree from 1 to 3. We hope to be publishing more on this later.
As for speed here are the results for 1mb with just local encoding/decoding times are in seconds and throughput is in MB/s. Also Throughput is calculated by dividing the initial size of 1mb by the speed in both cases. this means that for each case our network usage would be more since we are creating 4 times the original size in data.
| Encode Time | Decode Time | |
| Average | 0.077298816 | 0.024007306 |
| StDev | 0.004464512 | 0.002501727 |
| Total Time | 77.298816 | 24.007306 |
| MIN | 0.068047 | 0.016083 |
| MAX | 0.124591 | 0.037237 |
| AVE THROUGPUT | 12.93680876 | 41.6539865 |
No comments
Status Update
It has been a long time since we have updated and we figure it’s time for a status update.The first question i’d like to answer is what have we been doing with our time. The answer is of course being code monkeys. In our last post we said that it worked but there was still a lot of work to do. Of that work we now have message authentication and moved all of the configurations into one file. Also lots of cleaning has been done with more to do. The final improvement is in usability. Users and Storage Nodes will be able to automatically register. This means that installation will be extremely easy just drop some files and change the configuration a little and wuala. Speaking of Wua.la I’d like to take some time to talk about our “Competitors”. Of them there really are only two one is RobuSTore and the other is Wuala. First lets talk about RobuSTore they are the closest thing to our project and are from UC SD. They use LT Codes like our project does and have some of the same goals. What is different is that they are concerned mostly with speed and want some redundancy on top of that, and are also concerned with large files on a pre configured network. They do not use multicast or peer to peer systems (or so it appears) and they know where all the bits of data are. This is different from our goals. We hope to have a fast system yes but we want a dynamic system on unreliable dynamically configured networks with unreliable disks and computers in a word Byzantine. The reason for this is that we want to replace SANS and NAS with peoples laptops and PC’s not with cheaper servers. We also want the network to be flexible and work in a peer to peer way so that it can recover from individual network failures.Wuala on the other hand is very different they use ReedSolomon encoding which while an optimal erasure code is much more computationally complex and would slow down storage. Also ReedSolomon does not scale with the number of nodes in a dynamic way it needs pre defined variables to encode and decode thus is not Rate-less like LT Codes are. It also works in a peer to peer system though. However it is designed to be a “web service” instead of something a company could have for their personal use. It is also designed to be very distributed and has no central meta data storage which would not work for companies who need to know who saved what and get access to it. Also by the end of the quarter we will have a paper we will try to get published.
No commentsIt’s Alive
Great news we have gotten the system to work. It is still a little slow taking about 30 seconds to save a file and anywhere from 0.5 seconds to 45 seconds to retrieve a file, depending on size. Currently the system supports listing storing and removing files as well as creating directories.
It seems to perform better with more nodes on the network and is more reliable then (in a quick connect and ensure message sense not in a data integrity sense). We do however have lots of work still. We need to be-able to split up files into multiple parts so we can store lager files more effectively, ensure all of the certificate based authentication is working correctly and encrypt the file before sending it. The final encryption will probably be done last so that there is the least amount hinging upon it but it will be easy to implement since the encoding code can take any stream we need only to create a encrypted file stream, one such stream is actually already created and part of the pastry utilities.
Of key importance to our project is testing.To get closer to our goal of testing this on somewhat realistic systems we need to make it much easier to deploy and configure to do this we have made it use a variety of configuration files and we are working on creating an installer program to do most of the work for us in this regard aswell. However many of our tests will be done with unit tests some basic ones have already been created and will be expanded upon.
No comments
