{"thread":{"id":"3416","subject":"[RFC] Using GIT techniques to backup and synchronize file systems - replica","startedAt":"2006-02-21T13:21:19Z","lastAt":"2006-02-21T13:21:19Z","messageCount":1,"participants":["Herbert Nachtnebel"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"16501","messageId":"2B5D02300B16934F8F8491F19E7775D52D7A2B@centaurus.agcad.local","threadId":"3416","inReplyTo":null,"subject":"[RFC] Using GIT techniques to backup and synchronize file systems - replica","fromName":"Herbert Nachtnebel","fromEmail":"herbert.nachtnebel@tuwien.ac.at","sentAt":"2006-02-21T13:21:19Z","receivedAt":"2006-02-21T13:21:19Z","isPatch":false,"sender":{"key":"herbert.nachtnebel@tuwien.ac.at","avatar":null},"body":"Hi,\n\nin the last weeks some ideas were floated here on the list to make git\nusable not only for source code tracking, but also for synchronizing\nmail storage folders or even complete file systems. Time to throw some\ncode to the list:\n\nhttp://members.chello.at/replica/replica-20060220-1.tar.gz\n\nIn advance of the description of the code, I want to point out some\ninteresting properties of git. Git has some similarities with two\ndistinct application areas: backup and synchronisation. Consider the\nobject database alone, it contains snapshots in time of the state of the\nfile system - exactly the same what a backup application does.\nCurrently, git only holds a subset of the complete meta data of the\nfiles in it's database and should gain some support for directory meta\ndata, non-regular files, statically linked files, and sparse files. But\nthen it would be comparable to tar or other backup tools.\n\nRegarding the second point, synchronisation with others is clearly what\ngit is all about. Furthermore, in contrast to synchronising file systems\nlike coda, intermezzo and what ever they are called, git's merging tools\nare far more sophisticated. In fact too sophisticated for synchronizing\nfile systems. On file systems merging on the level of files is fully\nsufficient and without additional knowledge over the properties and\nmeaning of the individual files even dangerous! Combining these two\npoints, it is self-evident that git is more than a source code control\nsystem and folks are looking for ways to use it in other ways.\n\nA little drawback of git sacrifices the portability to other\narchitectures: the frequent use of scripting languages to implement\nimportant parts of functionality. Of course, for git that's an advantage\nsince the development is so much faster. But for a porting git to\narchitectures beside Unix, it's a real problem. I for one would love to\nuse it to synchronize between Sun, Linux and Windows machines in our\ndepartment. Additional, when git is used for synchronizing large\ndatasets, the scripts may easily become a performance bottleneck. I\nrealize that it is nearly impossible to change git to not depend on\nscripting in the near future but for the application I have in mind, I\nwould like to solve that; that's the cause I started to playing around\nwith the code presented above.\n\nSpeaking of performance, looking on the index file handling code I\nsuspect that it is not fast enough to handle really large datasets. For\ninstance, reading an index file is O(N) since it is reading in each\nindividual dataset and interprets it then. The same applies to\noperations on the index file - a pointer to each dataset is held in a\nlinear array which must be manipulated when inserting or deleting a\ndataset - or writing out the index file. I expect that that could be\nimproved if the layout of the index file is changed slightly;  each\ndataset should have the same size. And as Linus has recently shown, more\nspeed improvements could be gained if merging is handled directly on\ntree files instead of in the index: more evidence to play around with\nsome code.\n\nBut one difference in the usage pattern between the source code version\ncontrol and backup/synchronizing requires some basic changes to the git\nalgorithms which I suspect will not be acceptable and therefore requires\na distinct implementation: when checking in source code, it is known\nthat the files checked in do not change on disc. In the case of backup\nand synchronization such garanties can _not_ be made. Such an\napplication should be a background task, hence stopping the generation\nof new data or altering existing data is generally no option. But it's\ninteresting that the git techniques are a natural solution to this\nproblem: the index file together with the object database allows to\nsplit the task needed to synchronize with other sides into three phases.\nFirst, updating the index from the file system and altering the object\ndatabase, then merging the _constant_ index file with the other sides\nand finally, updating the file system (may be altered in the mean time)\nwith the updates stored in the index file, but not altering changed data\nin the file system. What does this change in git? Only one basic\nassumption. The size of blobs are stored in the blob header and in git\nit is assumed, that this size is correct. In the backup/synchronization\nusage case this can not be held. During reading-in data files into the\nobject database they may change their size on disk and the header of the\nblob may become out of sync. But this should be tolerated.\n\nIn summary, using git techniques for backup and synchronisation is an\ninteresting possibility, if some shortcomings could be solved. First, it\nshould handle all file types like tar handles them. Second, the merging\ntools should be simplified; merging on file level is sufficient: when\nconflicts occure tell the user, but don't try to merge automatically.\nThird, it would be fine if it would be completely implemented in C to\nmake it easily portable. Forth, it should handle any amount of data\nefficiently and should be able to synchronize arbitrarily contents\nbetween synchronization partners; of course even complete git\nrepositories (another hint that that what I have in mind should be\nrealized outside of git).\n\nAnd there we go, the presented application, replica, tries to realize\nthe above points. It is ment to be a distributed synchronization tool.\nThink of it as a two-way rsync with a permanent state (therefore\nminimizing the workload on the servers). What is implemented so far?\nWell, not that much: reading in a filesystem into the object database\nand generating tree (filenames converted to unicode) and commit objects\nand some debugging code. Therefore, synchronization with other sides is\ncomming next, but I think, you should be made aware about my current\nefforts. One difference to git is the index file handling; it may become\ninteresting also for git itself. I have tried to implement it in a\nsimple but efficient way. Basically, may version of the index file is\nbuilt up of AVL trees with an 1:1 relationship to the directory tree\nstore on disk. In difference to git, also directory entries representing\nsubdirectories are held in the index file together with their meta data.\nHence, even empty directories may be handled as expected by the user.\n\nI want to highlight the realisation of the AVL trees. The most\ninteresting property of them is that they are position independent. One\nis able to map the index file into the memory space and then use it\ndirectly without changing any values in it. Hence, reading the index\nfile and writing it out is essentially O(1); well, neglecting the time\nneeded to read the contents from disk or writing it out of course. All\nAVL tree pointers are not pointers per se, but are realized as offsets\nto their neighbors. I think (and hope), this implementation may prove\nuseful to be used in git also.\n\nHerbert.\n\nPS.: Sorry about this long posting but hopefully, some may find my work\ninteresting.\n"}]}