Venti
Encyclopedia
Venti is a network storage system that permanently stores data blocks. A 160-bit SHA-1 hash of the data (called score by Venti) acts as the address of the data. This enforces a write-once policy since no other data block can be found with the same address: the addresses of multiple writes of the same data are identical, so duplicate data is easily identified and the data block is stored only once. Data blocks cannot be removed, making it ideal for permanent or backup storage. Venti is typically used with Fossil
to provide a file system with permanent snapshots.
. It appeared in the Plan 9
distribution in 2002. Development has been continued by Russ Cox who has reimplemented most of the server, written a library for creating datastructures (files, directories and meta-data) to store in Venti and implemented optimizations. Venti is available both in the Plan 9 distribution and for Linux
and FreeBSD
as part of Plan 9 from User Space
. Venti is included as part of Inferno
with accompanying modules for access.
There is a Go
set of programs to build your own Venti servers. Included are examples using different kinds of backend storage.
daemon
. Clients connect to Venti over TCP and communicate using a simple RPC
-protocol. The most important messages of the protocol are listed below. Note that there is no message to delete an address or modify data at a given address.
The data block stored by Venti must be greater than 512 bytes in length and smaller than 56 kilobytes. So, if a Venti user/client wants to store larger data blocks, it has to make a datastructure (which can be stored in Venti). For example, Fossil
uses hash tree
s to store large files. Venti itself is not concerned with the contents of a data block; it does however store the type of a data block.
The design of Venti has some interesting consequences:
The data blocks are stored on hard drives. The disks making up the available storage, typically a RAID 5 configuration, is called the data log. This data log is split up in smaller pieces called arenas, which are sized so they can be written to other media such as CD
/DVD
or magnetic tape
. Another set of hard drives is used for the index, which maps scores to addresses in the data log. The data structure used for the index is a hash table
with fixed-sized buckets
. Venti relies on the scores to be randomly distributed so buckets do not fill up. Since each lookup costs one disk seek time, an index usually consists of multiple small SCSI
hard drives with low access time
.
, Plan 9 from User Space
, Inferno
and any other clients that implement the Venti protocol can all be used interchangeably to store and retrieve data.
is the pigeonhole principle, which states that if set A contains more values than set B, then for any function that maps A to B there will be members of B that are associated with more than one member of set A. In the case of Venti, the set of possible SHA-1 hashes is obviously smaller than the set of all possible blocks that could be stored in the filesystem, and thus a hash collision
is possible.
The risk of accidental hash collision in a 160-bit hash is very small, even for exabytes of data. Historically, however, many hash functions become increasingly vulnerable to malicious hash collisions due to both cryptographic and computational advances .
Venti does not address the issue of hash collisions; as of this time, it is still computationally infeasible to find collisions in SHA-1, but it may become necessary for Venti to switch to a different hash function at some point in the future.
Fossil (file system)
Fossil is the default file system in Plan 9 from Bell Labs. It serves the network protocol 9P and runs as a user space daemon, like most Plan 9 file servers. Fossil is different from most other file systems due to its snapshot/archival feature. It can take snapshots of the entire file system on...
to provide a file system with permanent snapshots.
History
Venti was designed and implemented by Sean Quinlan and Sean Dorward at Bell LabsBell Labs
Bell Laboratories is the research and development subsidiary of the French-owned Alcatel-Lucent and previously of the American Telephone & Telegraph Company , half-owned through its Western Electric manufacturing subsidiary.Bell Laboratories operates its...
. It appeared in the Plan 9
Plan 9 from Bell Labs
Plan 9 from Bell Labs is a distributed operating system. It was developed primarily for research purposes as the successor to Unix by the Computing Sciences Research Center at Bell Labs between the mid-1980s and 2002...
distribution in 2002. Development has been continued by Russ Cox who has reimplemented most of the server, written a library for creating datastructures (files, directories and meta-data) to store in Venti and implemented optimizations. Venti is available both in the Plan 9 distribution and for Linux
Linux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...
and FreeBSD
FreeBSD
FreeBSD is a free Unix-like operating system descended from AT&T UNIX via BSD UNIX. Although for legal reasons FreeBSD cannot be called “UNIX”, as the direct descendant of BSD UNIX , FreeBSD’s internals and system APIs are UNIX-compliant...
as part of Plan 9 from User Space
Plan 9 from User Space
Plan 9 from User Space is a port of many Plan 9 from Bell Labs libraries and applications to Unix-like operating systems...
. Venti is included as part of Inferno
Inferno (operating system)
Inferno is a distributed operating system started at Bell Labs, but is now developed and maintained by Vita Nuova Holdings as free software. Inferno was based on the experience gained with Plan 9 from Bell Labs, and the further research of Bell Labs into operating systems, languages, on-the-fly...
with accompanying modules for access.
There is a Go
Go (programming language)
Go is a compiled, garbage-collected, concurrent programming language developed by Google Inc.The initial design of Go was started in September 2007 by Robert Griesemer, Rob Pike, and Ken Thompson. Go was officially announced in November 2009. In May 2010, Rob Pike publicly stated that Go was being...
set of programs to build your own Venti servers. Included are examples using different kinds of backend storage.
Details
Venti is a user spaceUser space
A conventional computer operating system usually segregates virtual memory into kernel space and user space. Kernel space is strictly reserved for running the kernel, kernel extensions, and most device drivers...
daemon
Daemon (computer software)
In Unix and other multitasking computer operating systems, a daemon is a computer program that runs as a background process, rather than being under the direct control of an interactive user...
. Clients connect to Venti over TCP and communicate using a simple RPC
Remote procedure call
In computer science, a remote procedure call is an inter-process communication that allows a computer program to cause a subroutine or procedure to execute in another address space without the programmer explicitly coding the details for this remote interaction...
-protocol. The most important messages of the protocol are listed below. Note that there is no message to delete an address or modify data at a given address.
- read(score, type), returns the data identified by score and type
- write(data, type), stores data at the address calculated by SHA-1 hashing data, combined with type.
The data block stored by Venti must be greater than 512 bytes in length and smaller than 56 kilobytes. So, if a Venti user/client wants to store larger data blocks, it has to make a datastructure (which can be stored in Venti). For example, Fossil
Fossil (file system)
Fossil is the default file system in Plan 9 from Bell Labs. It serves the network protocol 9P and runs as a user space daemon, like most Plan 9 file servers. Fossil is different from most other file systems due to its snapshot/archival feature. It can take snapshots of the entire file system on...
uses hash tree
Hash tree
In cryptography and computer science Hash trees or Merkle trees are a type of data structure which contains a tree of summary information about a larger piece of data – for instance a file – used to verify its contents. Hash trees are a combination of hash lists and hash chaining, which in turn are...
s to store large files. Venti itself is not concerned with the contents of a data block; it does however store the type of a data block.
The design of Venti has some interesting consequences:
- Since writes are permanent, the file system is append-only (which allows for a simple implementation with lower chance of data-destroying bugs); no file system fragmentationFragmentation (computer)In computer storage, fragmentation is a phenomenon in which storage space is used inefficiently, reducing storage capacity and in most cases reducing the performance. The term is also used to denote the wasted space itself....
occurs. - Clients can verify the correctness of the server: the score of the returned data should be the same as the address requested. Since SHA-1 is a cryptographically secure hash, it is computationally infeasible to fabricate data.
- Data cannot be overwritten. If an address is already present, the data is already present.
- There is little need for user authentication: Data cannot be deleted, and can be read only if the score is known. The only potential problem is a user filling up the disks.
- Data can be compressed without making the disk structure complicated.
The data blocks are stored on hard drives. The disks making up the available storage, typically a RAID 5 configuration, is called the data log. This data log is split up in smaller pieces called arenas, which are sized so they can be written to other media such as CD
Compact Disc
The Compact Disc is an optical disc used to store digital data. It was originally developed to store and playback sound recordings exclusively, but later expanded to encompass data storage , write-once audio and data storage , rewritable media , Video Compact Discs , Super Video Compact Discs ,...
/DVD
DVD
A DVD is an optical disc storage media format, invented and developed by Philips, Sony, Toshiba, and Panasonic in 1995. DVDs offer higher storage capacity than Compact Discs while having the same dimensions....
or magnetic tape
Magnetic tape
Magnetic tape is a medium for magnetic recording, made of a thin magnetizable coating on a long, narrow strip of plastic. It was developed in Germany, based on magnetic wire recording. Devices that record and play back audio and video using magnetic tape are tape recorders and video tape recorders...
. Another set of hard drives is used for the index, which maps scores to addresses in the data log. The data structure used for the index is a hash table
Hash table
In computer science, a hash table or hash map is a data structure that uses a hash function to map identifying values, known as keys , to their associated values . Thus, a hash table implements an associative array...
with fixed-sized buckets
Bucket (computing)
In computing, the term bucket can have several meanings. It is used both as a live metaphor, and as a generally accepted technical term in some specialised areas. A bucket is most commonly a type of data buffer or a type of document in which data is divided into regions.-Features of a...
. Venti relies on the scores to be randomly distributed so buckets do not fill up. Since each lookup costs one disk seek time, an index usually consists of multiple small SCSI
SCSI
Small Computer System Interface is a set of standards for physically connecting and transferring data between computers and peripheral devices. The SCSI standards define commands, protocols, and electrical and optical interfaces. SCSI is most commonly used for hard disks and tape drives, but it...
hard drives with low access time
Access time
Access time is the time delay or latency between a request to an electronic system, and the access being completed or the requested data returned....
.
Usage
The Venti server may be used by clients in several ways. The Plan 9 operating system makes use of Venti for daily archival snapshots of the file system. These copies of the main filesystem can be mounted as a filetree of full copies organized by date. The utility programs 'vac' and 'unvac' can be used to store and retrieve data from a Venti server in the form of individual files or as a directory and its contents. 'Vacfs' allows browsing of the data associated with a vac score without full retrieval of all remotely stored data. Data and index scores can be duplicated between Venti servers using 'rdarena' and 'wrarena'. Plan 9 from Bell LabsPlan 9 from Bell Labs
Plan 9 from Bell Labs is a distributed operating system. It was developed primarily for research purposes as the successor to Unix by the Computing Sciences Research Center at Bell Labs between the mid-1980s and 2002...
, Plan 9 from User Space
Plan 9 from User Space
Plan 9 from User Space is a port of many Plan 9 from Bell Labs libraries and applications to Unix-like operating systems...
, Inferno
Inferno (operating system)
Inferno is a distributed operating system started at Bell Labs, but is now developed and maintained by Vita Nuova Holdings as free software. Inferno was based on the experience gained with Plan 9 from Bell Labs, and the further research of Bell Labs into operating systems, languages, on-the-fly...
and any other clients that implement the Venti protocol can all be used interchangeably to store and retrieve data.
Hash collisions
A basic principle of information theoryInformation theory
Information theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental limits on signal processing operations such as compressing data and on reliably storing and...
is the pigeonhole principle, which states that if set A contains more values than set B, then for any function that maps A to B there will be members of B that are associated with more than one member of set A. In the case of Venti, the set of possible SHA-1 hashes is obviously smaller than the set of all possible blocks that could be stored in the filesystem, and thus a hash collision
Hash collision
Not to be confused with wireless packet collision.In computer science, a collision or clash is a situation that occurs when two distinct pieces of data have the same hash value, checksum, fingerprint, or cryptographic digest....
is possible.
The risk of accidental hash collision in a 160-bit hash is very small, even for exabytes of data. Historically, however, many hash functions become increasingly vulnerable to malicious hash collisions due to both cryptographic and computational advances .
Venti does not address the issue of hash collisions; as of this time, it is still computationally infeasible to find collisions in SHA-1, but it may become necessary for Venti to switch to a different hash function at some point in the future.
See also
- FossilFossil (file system)Fossil is the default file system in Plan 9 from Bell Labs. It serves the network protocol 9P and runs as a user space daemon, like most Plan 9 file servers. Fossil is different from most other file systems due to its snapshot/archival feature. It can take snapshots of the entire file system on...
- snapshot file system that uses Venti for permanent storage - Plan 9 from User SpacePlan 9 from User SpacePlan 9 from User Space is a port of many Plan 9 from Bell Labs libraries and applications to Unix-like operating systems...
External links
- Venti: a new approach to archival storage, paper describing Venti.
- New Venti manual page (overview), section 7 venti manual page including general description and storage format.
- New Venti manual page (server), section 8 venti server manual page.
- New Venti manual page (tools), section 1 venti utilities manual page.
- Go code for implementing clients and servers.
- Venti module in Limbo for Inferno , kindly brought to life thanks to the Google Summer of Code.