Venti

Venti is a network storage system that permanently stores data blocks. The 160 -bit SHA-1 hash of the block ( called score ) is used for addressing of the data. This ensures that the same data blocks are stored only once, even if it is written more than once, since the same block also have the same address. However, blocks can not be removed. Venti is thus suitable for eternal archives and backups. Venti is mostly with the archive programs vac and vtstore, or fossil - a file system that provides permanent Snapshots - used.

History

Venti was developed by Sean Quinlan and Sean Dorward at Bell Labs. It appeared in the Plan 9 distribution in 2002. Development was continued by Russ Cox, who implemented the majority of new and developed a library for Venti - optimized data structures (files, directories, metadata). Venti is available both in the Plan9 distribution as well as a port for GNU / Linux and FreeBSD (as part of Plan 9 from User Space).

Details

Venti is a userspace daemon. Clients connect to via TCP and communicate via a simple RPC protocol. The main RPC messages are as follows:

  • Read ( score, type), supplies the data block at the appropriate score and type
  • Write ( data, type), stores a block of data with a given type. The score is composed of the calculated SHA-1 hash code and the type.

The data to be stored blocks shall not be less than 512 bytes or larger than 56 kB. A client wants to store larger files, it decomposed in this large up to 56 kB blocks and stores the resulting scores in a suitable data structure again in the grip handle. For example, used to store a Fossil Hashtree large files. Venti itself does not care about the content or structure of the stored data, it only stores the type of the data block.

The Venti design has some interesting consequences:

  • Since all write operations are permanent, that is, only adding new data (which is a very simple implementation, so less risk of data loss caused by bugs, enables ), also can not file system fragmentation occur.
  • Clients can check the correctness of the server: the score of the returned data must always match the requested score. As SHA -1 is a cryptographically - secure hash is, therefore, not only technical defects but also forgery attempts are revealed.
  • Data can not be overwritten. If a score is present, and its associated data are available.
  • Little need for user authentication: the data can not be tampered with or destroyed and can only be read if the matching score is known. A threat is possibly the fact that an attacker fills the space.
  • Compression is possible without complicated disk structures.
  • Incremental Backup separate media (eg CDROM / DVD, tape, network) is very simple.
  • Redundant, automatically synchronizing Venti implementations are simple and possible without adjustment to the clients.

The data blocks are stored in files of fixed size - called Arenas - stored, typically disks or partitions, as in a RAID array. The individual Arenas are thereby usually sized so that they can be readily applied to other media (eg CD / DVD) or magnetic tape write. All Arenas, taken together, form the data log. Another set of files making up the index, the scores on specific items within the data log maps. The data structure of the index is a Hashtable with a fixed bucket size. Venti relies on the random distribution of hash codes, so that the buckets are not overfilled. Since each index lookup costs one disk seek, it makes sense to distribute the index number of small discs with short access time. The strict division into Datalog and index has another advantage: the index can be reconstructed in case of data loss.

Hash collisions

A basic principle of information theory, the pigeonhole principle states that if a function that maps a large amount of A to a small amount of B, this map is not one-one and reversible. Thus, there are multiple elements of A, which are mapped to the same element of B. Theoretically, there are a lot of different blocks of data with the same hash code - this is also called collision.

Venti but does not deal with this question. It is argued that, with a SHA1 hash of the risk of a (random) collision is infinitesimal, even in order of exabytes. In 2005 there were, however, significant progress to reduce the computational effort for the creation of artificial SHA1 collisions ( yet it remains enormously costly ).

Plan 9 from Bell Labs Daemon (computing)
800462
de