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, . [PAIRTREE] Kunze, "File::Pairtree Perl Module", November 2008, . [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]