Network Working Group J. Kunze
Internet-Draft M. Haye
Expires: May 29, 2009 E. Hetzner
M. Reyes
California Digital Library
C. Snavely
University of Michigan Library IT
Core Services
November 25, 2008
Pairtrees for Object Storage (V0.1)
http://www.ietf.org/internet-drafts/draft-kunze-pairtree-01.txt
Status of this Memo
By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on May 29, 2009.
Copyright Notice
Copyright (C) The IETF Trust (2008).
Kunze, et al. Expires May 29, 2009 [Page 1]
Internet-Draft Pairtree November 2008
Abstract
This document specifies Pairtree, a filesystem hierarchy for holding
objects that are located within that hierarchy by mapping identifier
strings to object directory (or folder) paths two characters at a
time. If an object directory (folder) holds all the files, and
nothing but the files, that comprise the object, a "pairtree" can be
imported by a system that knows nothing about the nature or structure
of the objects but can still deliver any object's files by requested
identifier. The mapping is reversible, so the importing system can
also walk the pairtree and reliably enumerate all the contained
object identifiers. To the extent that object dependencies are
stored inside the pairtree (e.g., fast indexes stored outside contain
only derivative data), simple or complex collections built on top of
pairtrees can recover from index failures and reconstruct a
collection view simply by walking the trees. Pairtrees have the
advantage that many object operations, including backup and restore,
can be performed with native operating system tools.
Kunze, et al. Expires May 29, 2009 [Page 2]
Internet-Draft Pairtree November 2008
1. The basic pairtree algorithm
The pairtree algorithm maps an arbitrary UTF-8 [RFC3629] encoded
identifier string into a filesystem directory path based on
successive pairs of characters, and also defines the reverse mapping
(from pathname to identifier).
In this document the word "directory" is used interchangeably with
the word "folder" and all examples conform to Unix-based filesystem
conventions which should tranlate easily to Windows conventions after
substituting the path separator ('\' instead of '/'). Pairtree
places no limitations on file and path lengths, so implementors
thinking about maximal interoperation may wish to consider the issues
listed in the Interoperability section of this document.
The mapping from identifier string to path has two parts. First, the
string is cleaned by converting characters that would be illegal or
especially problemmatic in Unix or Windows filesystems. The cleaned
string is then split into pairs of characters, each of which becomes
a directory name in a filesystem path: successive pairs map to
successive path components until there are no characters left, with
the last component being either a 1- or 2-character directory name.
The resulting path is known as a _pairpath_, or _ppath_.
abcd -> ab/cd/
abcdefg -> ab/cd/ef/g/
12-986xy4 -> 12/-9/86/xy/4/
Armed with specific knowledge of a given namespace's identifier
distribution, one might achieve more balanced or efficient trees by
mapping to paths from character groupings other than successive
pairs. Pairtree assumes that this sort of optimization, however,
being tailored to individual and transient namespace conditions, is
often less important than having a single generalized and shareable
mapping. It uses pairs of characters to achieve hierarchies that
exhibit a reasonable balance of path length and fanout (number of
probable entries in any component directory).
Kunze, et al. Expires May 29, 2009 [Page 3]
Internet-Draft Pairtree November 2008
2. Pairpath termination and object encapsulation
A ppath (pairpath) terminates when it reaches an object. A little
jargon helps explain this. A _shorty_ is a 1- or 2-character
directory name, or any file or directory name that begins with
"pairtree" (these are reserved for future use). A ppath consists of
a sequence of "shorties" ending in a non-shorty, such as a
3-character directory name or the 2-character file name "xy". The
pairtree below contains two objects with identifiers "abcd" and
"abcde".
ab/
|
\--- cd/
|
|--- foo/
| | README.txt
| | thumbnail.gif
| |
| |--- master_images/
| | | ...
| | ...
| |
| \--- gh/
|
\--- e/
|
\--- bar/
| metadata
| 54321.wav
| index.html
An object is reached when a non-shorty is detected. An object is
_properly encapsulated_ if it is entirely contained in a non-shorty
directory that is the immediate child of a shorty directory, in other
words, if the 1- or 2-char directory name ending the object's ppath
contains exactly one non-shorty directory that holds all the object's
descendants. The two objects "abcd" and "abcde" above are properly
encapsulated. Any shorty directory found at the same level as the
non-shorty extends the pairtree. So while the "foo/" directory above
does not subsume "e/" at the same level, by encapsulation, it does
subsume the "gh/" underneath it (i.e., "gh/" is invisible to the
pairtree algorithm, at least on a first pass).
Practice will vary according to local custom as to how to name the
encapsulating object directory beneath that last shorty. Its name is
completely independent of the object identifier. For example, every
object directory in a pairtree could have the uniform name "thingy".
Kunze, et al. Expires May 29, 2009 [Page 4]
Internet-Draft Pairtree November 2008
It is common for the directory name to be a terminal substring of the
object identifier, as in:
id: 13030_45xqv_793842495
ppath: 13/03/0_/45/xq/v_/79/38/42/49/5/793842495
All objects should be properly encapsulated. If an object is
detected that is _improperly encapsulated_, that is, when a ppath
ends with a shorty directory that contains more than one non-shorty,
the detecting system should take corrective action. In this
situation, also known as a "split end", all those non-shorties
(directories and files) are considered to belong to one object (not
properly encapsulated) identified by the containing ppath. Excluding
shorties from the object permits one identifier to be a substring of
another (e.g., "abcd" and "abcde" can co-exist in a pairtree), and
defining ppath termination in this way prevents "hidden riders", or
data residing in a pairtree that is not contained or accounted for in
any object. Here is an example of an improperly encapsulated object
named "bent".
be/
|
\--- nt/ [ split end: two files, no encapsulation ]
| README.txt
| report.pdf
|
\--- ef/
| ...
If a "split end" is encountered, an importing system is encouraged to
normalize it by creating a single object directory called "obj" and
pushing the non-shorties in question underneath it, as in:
be/
|
\--- nt/
|
|--- obj/ [ split end repaired with "obj" directory ]
| | README.txt
| | report.pdf
|
\--- ef/
| ...
Kunze, et al. Expires May 29, 2009 [Page 5]
Internet-Draft Pairtree November 2008
3. Identifier string cleaning
Prior to splitting into character pairs, identifier strings are
cleaned in two separate steps. One step would be simpler, but
pairtree is designed so that commonly used characters in reasonably
opaque identifiers (e.g., not containing natural language words,
phrases, or hints) result in reasonably short and familiar-looking
paths. For completeness, the pairtree algorithm specifies what to do
with all possible UTF-8 characters, and relies for this on a kind of
URL hex-encoding. To avoid conflict with URLs, pairtree hex-encoding
is introduced with the '^' character instead of '%'.
First, the identifier string is cleaned of characters that are
expected to occur rarely in object identifiers but that would cause
certain known problems for file systems. In this step, every UTF-8
octet outside the range of visible ASCII (94 characters with
hexadecimal codes 21-7e) [ASCII], as well as the following visible
ASCII characters,
" hex 22 < hex 3c \ hex 5c
* hex 2a = hex 3d ^ hex 5e
+ hex 2b > hex 3e | hex 7c
, hex 2c ? hex 3f
must be converted to their corresponding 3-character hexadecimal
encoding, ^hh, where ^ is a circumflex and hh is two hex digits. For
example, ' ' (space) is converted to ^20 and '*' to ^2a.
In the second step, the following single-character to single-
character conversions must be done.
/ -> =
: -> +
. -> ,
These are characters that occur quite commonly in opaque identifiers
but present special problems for filesystems. This step avoids
requiring them to be hex encoded (hence expanded to three
characters), which keeps the typical ppath reasonably short. Here
are examples of identifier strings after cleaning and after ppath
mapping.
Kunze, et al. Expires May 29, 2009 [Page 6]
Internet-Draft Pairtree November 2008
id: ark:/13030/xt12t3
-> ark+=13030=xt12t3
-> ar/k+/=1/30/30/=x/t1/2t/3/
id: http://n2t.info/urn:nbn:se:kb:repos-1
-> http+==n2t,info=urn+nbn+se+kb+repos-1
-> ht/tp/+=/=n/2t/,i/nf/o=/ur/n+/nb/n+/se/+k/b+/re/po/s-/1/
id: what-the-*@?#!^!?
-> what-the-^2a@^3f#!^5e!^3f
-> wh/at/-t/he/-^/2a/@^/3f/#!/^5/e!/^3/f/
After this character cleaning procedure, directory names resulting
from splitting the string into character pairs will be legal and not
terribly inconvenient for mainstream Unix and Windows systems, for
their command interpreters, and as web-exposed URL paths.
Kunze, et al. Expires May 29, 2009 [Page 7]
Internet-Draft Pairtree November 2008
4. Pairpath initiation
The top of a pairtree hierarchy is signaled by the presence of a
directory called "pairtree_root". There may be other filenames
beginning with "pairtree" accompanying it, as in the example below.
Lines of file content, when shown, appear in parentheses beneath the
file name.
current_directory/
| pairtree_version0_1 [which version of pairtree]
| ( This directory conforms to Pairtree Version 0.1. Updated spec: )
| ( http://www.cdlib.org/inside/diglib/pairtree/pairtreespec.html )
|
| pairtree_prefix
| ( http://n2t.info/ark:/13030/xt2 )
|
\--- pairtree_root/
|--- aa/
| |--- cd/
| | |--- foo/
| | | | README.txt
| | | | thumbnail.gif
| | ...
| |--- ab/ ...
| |--- af/ ...
| |--- ag/ ...
| ...
|--- ab/ ...
...
\--- zz/ ...
| ...
The "pairtree_prefix" contains a string that should be prepended to
every identifier inferred from the pairtree rooted at
"pairtree_root". This may be used to reduce path lengths when every
identifier in a given pairtree shares the same initial substring. In
the example above, the pairpath "/aa/cd/" would thus correspond to
the identifier "http://n2t.info/ark:/13030/xt2aacd".
Kunze, et al. Expires May 29, 2009 [Page 8]
Internet-Draft Pairtree November 2008
5. Pairtree benefits
Pairtree can be used with any object identifier, but its real
strength comes when two main assumptions are also in effect. The
first assumption is that every component on which an object depends
will be stored in the filesystem. Increasingly, digital library
systems recognize that the risk of scattering components among
databases and files can be reduced when all primary data is kept in
non-volatile storage that can be backed up and manipulated using
core, ubiquitous operating system tools. While database indexes are
important for supporting fast or complex query execution, this pre-
condition merely requires that those indexes hold secondary copies of
object components (e.g., metadata).
The second assumption is that all the components of an object, and
only the components of that object, are stored in an object's
directory. Thus an object's directory contains no components
belonging to another object. Of course complex objects will still
contain other objects, and possibly other pairtrees, but such object
containment is not visible to the pairtree algorithm except with a
recursive pass.
With these two pre-conditions met, a pairtree can be imported by a
system that knows nothing about the nature or structure of the
objects but can still deliver any object's files by requested
identifier. The mapping is reversible, so the importing system can
also walk the pairtree and reliably enumerate all the contained
object identifiers. To the extent that object dependencies are
stored inside the pairtree, simple or complex collections built on
top of pairtrees can recover from index failures and reconstruct a
collection catalog simply by walking the trees. Finally, pairtrees
have the advantage that many object operations, including backup and
restore, can be performed with native operating system tools.
Kunze, et al. Expires May 29, 2009 [Page 9]
Internet-Draft Pairtree November 2008
6. Interoperability: Windows and Unix File Naming
Besides the fundamental difference between path separators ('\' and
'/'), generally, Windows filesystems have more limitations than Unix
filesystems. Windows path names have a maximum of 255 characters,
and none of these characters may be used in a path component:
< > : " / | ? *
Windows also reserves the following names: CON, PRN, AUX, NUL, COM1,
COM2, COM3, COM4, COM5, COM6, COM7, COM8, COM9, LPT1, LPT2, LPT3,
LPT4, LPT5, LPT6, LPT7, LPT8, and LPT9. See [MSFNAM] for more
information.
Kunze, et al. Expires May 29, 2009 [Page 10]
Internet-Draft Pairtree November 2008
7. Security Considerations
Pairtree poses no direct risk to computers and networks. As a
filesystem format, pairtree is capable of holding files that might
contain malicious executable content, but it is no more vulnerable in
this regard than formats such as TAR and ZIP.
Kunze, et al. Expires May 29, 2009 [Page 11]
Internet-Draft Pairtree November 2008
Appendix A. Sample Implementation
There is a [PAIRTREE] Perl module at CPAN the implements two
mappings. The routine, id2ppath, maps an identifier to a pairpath,
and another routine, ppath2id, performs the inverse mapping. The
usage synopsis follows.
use File::Pairtree; # imports routines into a Perl script
id2ppath($id); # returns pairpath corresponding to $id
ppath2id($path); # returns id corresponding to $path
Kunze, et al. Expires May 29, 2009 [Page 12]
Internet-Draft Pairtree November 2008
8. References
[ASCII] "Coded Character Set -- 7-bit American Standard Code for
Information Interchange, ANSI X3.4", 1986.
[MSFNAM] Microsoft, "Naming a File", 2008,
<http://msdn2.microsoft.com/en-us/library/aa365247.aspx>.
[PAIRTREE]
Kunze, "File::Pairtree Perl Module", November 2008, <http:
//search.cpan.org/~jak/Pairtree-0.2/lib/File/Pairtree.pm>.
[RFC3629] Yergeau, F., "UTF-8, a transformation format of ISO
10646", STD 63, RFC 3629, November 2003.
Kunze, et al. Expires May 29, 2009 [Page 13]
Internet-Draft Pairtree November 2008
Authors' Addresses
John A. Kunze
California Digital Library
415 20th St, 4th Floor
Oakland, CA 94612
US
Fax: +1 510-893-5212
Email: jak@ucop.edu
Martin Haye
California Digital Library
415 20th St, 4th Floor
Oakland, CA 94612
US
Fax: +1 503-234-3581
Email: martin.haye@ucop.edu
Erik Hetzner
California Digital Library
415 20th St, 4th Floor
Oakland, CA 94612
US
Fax: +1 503-234-3581
Email: erik.hetzner@ucop.edu
Mark Reyes
California Digital Library
415 20th St, 4th Floor
Oakland, CA 94612
US
Fax: +1 503-234-3581
Email: mark.reyes@ucop.edu
Kunze, et al. Expires May 29, 2009 [Page 14]
Internet-Draft Pairtree November 2008
Cory Snavely
University of Michigan Library IT Core Services
920 N University Ave, 300D Hatcher Library N
Ann Arbor, MI 48109
US
Fax: +1 734-647-6897
Email: csnavely@umich.edu
Kunze, et al. Expires May 29, 2009 [Page 15]
Internet-Draft Pairtree November 2008
Full Copyright Statement
Copyright (C) The IETF Trust (2008).
This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors
retain all their rights.
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at
ietf-ipr@ietf.org.
Acknowledgment
Funding for the RFC Editor function is provided by the IETF
Administrative Support Activity (IASA).
Kunze, et al. Expires May 29, 2009 [Page 16]