c# wpf adobe pdf reader : Extract page from pdf acrobat application SDK tool html wpf .net online ames-mss060-part153

LiFS:AnAttribute-RichFileSystemforStorageClassMemories
SashaAmes
NikhilBobb
KevinM.Greenan
OwenS.Hofmann
MarkW.Storer
CarlosMaltzahn
EthanL.Miller
ScottA.Brandt
StorageSystemsResearchCenter
ComputerScienceDepartment
UniversityofCalifornia,SantaCruz
Abstract
Asthenumberandvarietyoffilesstoredandaccessedby
atypicaluserhasdramaticallyincreased,existingfilesys -
temstructureshavebeguntofailasamechanismforman-
agingalloftheinformationcontainedinthosefiles.Many
applications—emailclients,multimediamanagementap-
plications, and d desktop search engines s are examples—
havebeenforcedtodeveloptheirownrichermetadata
infrastructures.Whileeffective,thesesolutionsaregener-
allynon-standard,non-portable,non-sharableacrossap-
plications,usersorplatforms,proprietary,andpotentially
inefficient. Intheinterestofprovidingarich,efficient,
sharedfilesystemmetadatainfrastructure,wehavedevel-
opedtheLinkingFileSystem(LiFS).Takingadvantage
ofnon-volatilestorageclassmemories, LiFSsupportsa
widevarietyofuserandapplicationmetadataneedswhile
efficientlysupportingtraditionalfilesystemoperations.
1 Introduction
Filesysteminterfaceshavechangedrelativelylittleinthe
threedecadessincetheUNIXfilesystemwasfirstintro-
duced. Metadatainstandardfilesystemsincludesdirec-
toryhierarchiesandsomefixedper-fileattributesinclud-
ingfilename,permissions,size,andaccess/modification
times.Whileprimitive,theseinterfaceshaveservedwell.
Inthesametimeframe,demandsonthestoragesubsys-
temhaveincreasedbothquantitativelyandqualitatively.
Storagesystemshavegrown,theamountofstorageac-
cessedbyindividualusershasincreased,andthevariety
ofdatastoredhasgrowndramatically. General-purpose
filesystemsarenowusedtostoretremendousvolumesof
textdocuments,webpages,applicationprograms,email
files,calendars,contacts,musicfiles,movies,andmany
othertypesofdata.Althoughcurrentfilesystemsarerel-
ativelyeffectiveatreliablystoringthedata,theincreasing
sizeandcomplexityoftheinformationstoredhasmade
managementandretrievaloftheinformationproblematic.
Simplystated,withsomuchinformation,itisdifficultto
findwhatonereallywants. Thisproblemhasbeenad-
dressedonthewebwiththedevelopmentofsearchen-
gines,anditisnowoftenhardertofindinformationon
one'sownharddrivethanontheweb.
To address this s shortcoming, , application developers
havebeenforcedtodeveloptheirownmetadatainfras-
tructures. Emailapplications,digitalphotoalbums,dig-
italmusicapplications,desktopsearchapplications,and
manyothershavetheirownfilesystemmetadatatoenable
theorganizing,searching,browsing,viewing/playing,an-
notating, andgenerally y working withspecifictypes s of
files. Manyoftheseapplicationshavespecial-purpose
codefordealingwiththespecificpropertiesofthetypeof
datatheymanage,buttheyalsoincludecodethatisnot
data-specificfororganizing, annotating, , browsing, etc.
Becausethiscodewasdevelopedaspartofanapplication,
itrarelyadherestoanystandard,isoftennotportable,it
isdifficulttosharebetweenapplications,users,orplat-
forms,itistypicallyownedbythecompanythatdevel-
opedit,anditispotentiallyinefficient.
Keyfunctionsoftheoperatingsystemaretoefficiently
provideservicesthatareusedbyavarietyofapplications,
to abstract awaylow-level details byproviding a use-
fulhigh-levelAPI,andtofacilitatesharingofresources
usedbymultipleusersandapplications. Thewidevari-
etyofapplicationsdevelopingtheirownfilesystemmeta-
datainfrastructureshowstheneedforthisinfrastructure
tobeprovidedbythefilesystem. Recently,researchers
(ourselves included) ) havetaken steps s in n that direction
byincludingadditionalper-filemetadataintheformof
key
,
value
pairs. While useful, this is inadequate to
support the needs of the wide variety of applications de-
scribedabove.
We present the Linking File System (LiFS). In addi-
tion to the standard file system operations, LiFS pro-
vides searchable application-defined file attributes and at -
tributed links between files. File attributes are in the form
of application-defined
key
,
value
pairs. Links are ex-
plicit relationships between files thatcan themselves have
attributes expressed as
key
,
value
pairs to express the na-
Extract page from pdf acrobat - application SDK tool:C# PDF Page Extract Library: copy, paste, cut PDF pages in C#.net, ASP.NET, MVC, Ajax, WinForms, WPF
Easy to Use C# Code to Extract PDF Pages, Copy Pages from One PDF File and Paste into Others
www.rasteredge.com
Extract page from pdf acrobat - application SDK tool:VB.NET PDF Page Extract Library: copy, paste, cut PDF pages in vb.net, ASP.NET, MVC, Ajax, WinForms, WPF
Detailed VB.NET Guide for Extracting Pages from Microsoft PDF Doc
www.rasteredge.com
ture of the relationship created by the link. These simple
additions dramatically change the nature of file systems,
enabling a wide variety of operations, providing a rich,
shared metadata infrastructure,and allowing applications
to focus on managing application-specific data instead of
managing things thatare best managedby the file system.
In LiFS, all files may contain data and links to other
files. Thus, a traditional data file is one with contents and
nolinks,and atraditionaldirectoryis onewithnocontents
anddirectorycontainmentlinks toother files. Many more
interesting examples are possible. For example, a .c file
can contain links to the .h files it includes. An executable
can contain links to its source .c files, the compiler used
to generate it, and the library files on which it depends.
Adocument can contain a link to the application used to
edit and view it. With respect to the application-specific
infrastructures mentionedabove,an email client,a digital
photo album, and a music player now all need only pro-
vide a GUI for managing their specific type of data and
manipulatingthe attributes ofand relationshipsamongthe
files they each manage, and the file system can take care
of storing the attributes and relationships and efficiently
supportingtheir manipulation, search,and otheractions.
LiFS is enabled by storage class memories—non-
volatile,byte-addressable RAM—by making the reading,
writing,indexing,and searchingofsuchrichmetadatafast
and efficient. Our prototype is designed with MRAM in
mind,but is implementedinLinuxusing standardDRAM.
Our results demonstrate that the performance of LiFS
is comparable to, if not better than, that of other Linux
file systems, while providing far richer metadata seman-
tics. As a proof-of-conceptwe have implemented a sim-
ple browser that functions alternatively as a file system
browser, an email browser, a digital photo browser, or a
music browser, depending upon the files and links con-
tained in the file system hierarchy it is exploring. The
following sections examine some motivating examples in
more detail, discuss the LiFS design, present the details
of our LiFS implementation, and show the performance
ofLiFSin various scenarios.
2 Motivating Examples
Relational links and attributes are surprisingly useful. In
this sectionwewill illustratetheirutility in findingand o r-
ganizing information and in coping with change in com-
putinginfrastructure. These areas are ofparticularinterest
in the context of rapid growth of personal and enterprise-
level data and the emergence of utility computingrequir-
ing scalable IT managementtechnologies.
2.1 Information Management
2.1.1 Searching
Finding data on the vast World-wide Web is often eas-
ier than finding the same content on a local hard drive.
The same search engine technology that does well on
the Internet typically performs poorly when applied to
enterprise-level file systems. To our knowledge both of
these statements are only based on anecdotal albeit com-
mon evidence but can be plausibly explained: web links
convey relevance and semantic informationthat turns out
to be very useful for searching and presenting search re-
sults [36]. However, traditional file systems only convey
relationships among files through the hierarchical direc-
torysystem.
Hierarchical directories are actually a compromise be-
tweenthe need ofusers to organizetheirdata on one hand
and file system designers who aim to reduce the cost of
maintaining metadata on the other. This dearth of rela-
tionships between files is the primary reason that finding
data in enterprise-wide file systems or even in local file
systems appears to be harder than onthe Internet.
There is in fact a wealth of explicit and implicit re-
lationships among files. Because hierarchical directo-
ries make it difficult to express explicit relationships,th is
information often ends up being stored in application-
specific files and obscured by proprietary file formats.
There are also implicit relationships such as provenance,
applicationanddata dependencies,as well ascontextsthat
may span applications; this information is typically not
recorded at all. However, maintaining provenance and
contextrelationships enablespowerfulsearchcapabilities.
For example, two downloaded files that are in some way
related on the web,e.g., originating from the same web
site, normally are strippedfrom theircontext when stored
on alocal file system. Provenancepreserves theirrelation-
ships and provides important clues to context-sensitive
searches.
The history of Internetsearch engines shows a progres-
sion of increasingly sophisticated ways of mining rela-
tionships, extending successful searching even to docu-
ments with content obscured by proprietary formats. The
introduction of rich relationships for files will allow the
successful use of advanced search technologies within
personal orenterprise-wide file systems.
2.1.2 Repository Sharing
Because applications are often the sole maintainer of
meaningful relationships among files, repositories are of-
ten partitioned. As a result, each repository can only
be accessed by one application and relationships that
span repositories are hard to represent. A good exam-
ple is the common fact that notes, email, calendar en-
application SDK tool:.NET PDF Document Viewing, Annotation, Conversion & Processing
Extract bookmark & outlines. Extract hyperlink inside PDF. PDF Write. Print. Support for all the print modes in Acrobat PDF. Print only specified page ranges.
www.rasteredge.com
application SDK tool:C# PDF Converter Library SDK to convert PDF to other file formats
using other external third-party dependencies like Adobe Acrobat. to image or document, or from PDF document to other file formats, like multi-page TIFF file
www.rasteredge.com
tries, and instant message conversations each have their
own application-specific repositories with no mechanism
to represent relationships between, for example, an email
and a calendar entry. Some commercial personal in-
formation systems such as Microsoft Outlook [31], and
othersystems currently underdevelopmentsuch as Chan-
dler [34] and Haystack [38] try to alleviate this problem
by combining traditionally separate repositories into one
application-specific repository. However, this approach
only alleviates repository partitioning rather than solving
the problem.
Another disadvantage of maintaining relationships on
the applicationlevel is that itmakesintegration amongap-
plications unnecessarily hard: To maintain data relation-
ships across applications, each application has to know
howtocommunicatewith anotherapplication's APItoac-
cess and manipulate data in the other application's repos-
itory. Some alleviation ofthisn:mscaling problemis of-
feredby“glue”languages suchasApple'sAppleScript[4]
andmorerecent Automator[5],which are designedtoen-
able endusers to automate commontasks spanningmulti-
ple applications. However, the resulting scripts still inter-
act with data repositories via the API of applications and
quickly become obsolete due to API changes from new
versions or substitutions of applications.
LiFS, on the other hand, provides a file-centric (as op-
posed toapplication-centric)infrastructurethatallows ap-
plications to not only store files but to insert relationship
information directly into the file system's metadata. All
applications that take advantage of LiFS relational links
and attributes automatically share one repository and in-
tegration among applications only needs to interact with
the file system's API.
2.1.3 Navigation
Rich relationships between files require more sophis-
ticated navigation tools than a traditional file system
browser. File systembrowsers are specialized fortravers-
ing hierarchies but are ill-suited for navigating non-
hierarchical graph structures with different kinds oflinks.
Web browsers, on the other hand, are designed to navi-
gate hypertext graphs and have developed mechanisms to
handle a variety of link types. For example, a web page
can contain image source links that are immediately re-
solved to inline images while anchors are not resolved
but displayed as clickable text. Other examples of link
types are references to frames,style sheets, ormore com-
plicatedJavascript constructs that allow asynchronous re-
quests for updates without reloading the web page, such
as those usedby Google's Gmail,Maps,and Suggest.
Recent web browser designs offer a high degree of ex-
tensibility and the ability to render sophisticated user in-
terfaces. We believe that this evolution of web browsers
is not a coincidence but was both possible and necessary
because oftheWeb's complexrelational linkingstructure.
There is no one good way to display complex structures.
Instead, more orless specialized interfaces forinteracting
with these structures are adopted as these complex struc-
tures become commonplace. We are faced with a similar
situationwhen designingfile systembrowsers once we in-
troduce complex linking structures as in LiFS.
The need to render a wide variety of structures has led
to powerful architectures, culminating in Mozilla [45],
that offer a very flexible and fast layout engine
(Gecko [44]) and extensible component architecture that
loads the entire specification ofa userinterfacefromfiles.
This user interface specification framework is referred to
as XML User interface Language (XUL [47]). It is pow-
erful enough to fully specify the user interface of Firefox
andThunderbird,twoinstances ofMozilla,oneforbrows-
ing the web and one for managing email. Furthermore,
XUL's sister eXtensible Bindings Language (XBL [46]),
allows dynamicmodificationofparts ofthe userinterface.
Significant in the context of LiFS is the fact that XUL
presents a fully implemented framework that allows the
linking of file structures to specify how to display these
structures. Itis nowconceivableto integrate formerlyseg-
regated navigation and management activities regarding
notes, email, instant messages, calendar entries, and soft-
waredevelopmentprojectsinto one“file systembrowser”.
Interestingly, the relationship between XUL compo-
nents (UI content, skin, and scripts) is specified in RDF
files [48]. These RDF files can be directly translated into
LiFS linking structures. Furthermore, XUL populates the
user interface by specifying queries to one or more RDF
data sources. The Mozilla component architecture allows
the creation of new RDF data sources. We are in the
process ofimplementinga componentthat provides LiFS
linking structures and file attributes as RDF data source.
In summary,byprovidingrelationallinks wecan lever-
age file systemnavigationinLiFSwithWebbrowsertech-
nologies and use these technologies to combine file sys-
tem content in ways that were not possible before because
of repository partitioning andapplicationsthat are hard to
integrate.
2.2 Infrastructure Change Management
Infrastructurechangecan,and often does,destroythe use-
fulness of data. However, infrastructures change all the
time: softwareandhardwaregetupgradedorreplacedand
achange as small asa singleupgradeofanapplication can
render data useless. This process of continual change is
the primary reason fordata obsolescence and the number
one threat to digital preservation [11]. A special case of
infrastructurechangeoccurs when data is migrated. In the
application SDK tool:C# powerpoint - PowerPoint Conversion & Rendering in C#.NET
without using other external third-party dependencies like Adobe Acrobat. PowerPoint to PDF Conversion. This page will tell you how to use XDoc.PowerPoint SDK
www.rasteredge.com
application SDK tool:C# Word - Word Conversion in C#.NET
independently, without using other external third-party dependencies like Adobe Acrobat. Word to PDF Conversion. This page will tell you how to use XDoc.Word
www.rasteredge.com
following section we will illustrate how relational links
can make infrastructure change more manageable.
2.2.1 Obsolescence
Users oftendiscoverdata obsolescence when it is too late.
Atypical example is someone who has to amend the tax
return for the year 2001 while filing for 2003 and has
changed computing platforms sometime in 2002. While
changing platforms, the user copies the file for the 2001
tax return to the new platform not realizing that each tax
yearand each computing platform requires a separate ap-
plication. Two years later the user is unable to read the
2001 file because the retroactively purchased application
for 2001 cannot access 2001 files generated on the old
platform. The user is left with trying to reconstruct the
former infrastructure which might be more difficult than
recreating the 2001 file. Thus, the 2001 data was essen-
tially lost.
The example illustrates that even well within typical
record life cycles it is difficult to anticipate the conse-
quences of infrastructurechangeintime unless the depen-
dencies ofdata are made explicit. One way to address the
rapidrate ofchangeis tointroduceanotherapplicationfor
managing the context of data by keeping track of which
application version created what data. However, such an
application would be as exposed to obsolescence as any
other application. File systems, on the other hand, have
historically enjoyed low obsolescence and are therefore
bettersuited to manage dependenciesoverlongertimepe-
riods.
In LiFS we can represent the dependencies in this ex-
ample with relational links. This allows the generation
of a detailed list of consequencesbefore deleting an ap-
plication or changingthe infrastructure in other ways that
mightcause damage.
2.2.2 Migration
To continue with the tax return example, recall that the
key failure that led to obsolete data was migrating tax
data from one platform to another without realizing (for
two years)that not all dependencieson the target platform
were satisfied. To solve this problem, the source platform
has to communicate data dependencies to the target plat-
form and the target platform needs to figure out how to
satisfy these dependencies. This functionality is similar
to popular open source package managers which package
recognize whatother packagesneedto be downloadedfor
agiven packagein orderforthe software to function.
Importandexport ofLiFSmetadataforcommunication
of dependencies between file systems is still ongoing re-
search. We anticipate that metadata will be exported as
RDF, and that the import of RDF into metadata will in-
volve a resolution process that either generates requests
formissing files or generates alerts for non-satisfiable de-
pendencies.
3 File System Design
3.1 Basic Goals
We have designed LiFS with the goal of providing at-
tributed relationships between files and enhanced meta-
data with noperceptible performanceoverhead compared
to traditionalfilesystems. We assume thatthestoragesys-
tem LiFS runs on will include a high-bandwidth, higher
latency componentwithlarge amounts of storage (such as
ahard disk), and a lower bandwidth, low-latency compo-
nent with a small amount of storage proportional to the
size of the larger storage. This lower bandwidth, low-
latency componentcould be anytype of byte addressable,
non-volatile memory such as magnetic RAM [12] or any
otherstorageclass memorytechnology. The largercapac-
ity, higher latency storage is used to hold the user data
stored in the file system, while traditional and enhanced
metadata resides on the smaller,faster storage class mem-
ory.
Three specific features of the file system that allow
us to reach our design goals are named links between
files, attributes on files, and attributes on links. Attribut es
are composedof
key
,
value
pairs such as
author
,
john
.
Files are named according to the name of the link by
which they are accessed. For instance if there is a link
namedbar fromsource file foo, the target file is accessed
as bar. Multiple links betweentwo files may exist as long
as they are disambiguated by a unique set of attributes.
Multiple links are useful when there are multiple users of
on a system,andmorethan one userorapplicationwishes
to have a link between two files with their own set of at-
tributes.
In LiFS, the concept of a set of links from a source
file replaces that of a directory. For example, if a file
work/document.txt links to a file picture.jpeg, a user
can change directories to work/document.txt and find
picture.jpegin the listing. Traditionaldirectories areem-
ulated via zero byte files with links to all member files.
Forbackwardscompatibility,alegacy application mayset
aspecial STAT attribute on afile in ordertoaccess that file
as a directory,orvice versa.
To offerthis new functionality,we propose severalnew
systemcalls,showninTable1,tomanipulatelinks andat-
tributes onlinks. Thenewsystemcalls have a syntax very
similar to that ofcurrent calls tomanipulateand get infor-
mation about directories, links, and extended attributes.
Forfile attributes,we implementthestandard getxattrand
setxattrextended attribute calls.
application SDK tool:C# Windows Viewer - Image and Document Conversion & Rendering in
standard image and document in .NET class applications independently, without using other external third-party dependencies like Adobe Acrobat. Convert to PDF.
www.rasteredge.com
application SDK tool:VB.NET PDF: How to Create Watermark on PDF Document within
or image (such as business's logo) on any desired PDF page. And with our PDF Watermark Creator, users need no external application plugin, like Adobe Acrobat.
www.rasteredge.com
Systemcall
Function
rellink
Create a new relational link be-
tween files
rmlink
Remove a relational link between
files
setlinkattr
Set attributesonanexistinglinkbe-
tween files
openlinkset
Returns an identifier for a set of
links froma sourcefile
readlinkset
Fills in standard directory entry
structure with link name and at-
tributes for the nextlink in a set
Table 1: New file system calls
3.2 In-Memory Data Structures
Traditional file system data structures are optimized for
accessing both data and metadata on a high-latency disk.
In contrast, we designed the file system data structures in
LiFS to takeadvantage of lowlatency storage class mem-
ories. Traditional inodes have been augmented by link
nodes (lnodes), attribute nodes (anodes)and extentnodes
(enodes). Because memory access is very cheap, lnodes,
anodes and enodes are arranged in linked lists, allowing
for trivial insertionand deletion.
Our file system uses a hash table which eliminates du-
plicate storage of strings. The first time a string is used in
LiFS, it is added to the table. When an identical string is
later used, a lookup returns a pointer to the string in the
string table. A reference count is kept for each string so
that unused strings do not remain in memory. The string
table is used to optimize string comparisons and searches
in the file system. Strings for which there are entries in
the string table can be tested for equality with a pointer
comparison rather than comparing string data. Addition-
ally, if a string is not in the string table we know that any
search on that string in the metadata will not be satisfied.
All data structures necessary for file system usage are
referenced from the supernode, shown in Figure 2. The
supernode is storedat the beginningofnon-volatilemem-
ory. The supernodereferencesthe stringtable,a bitmapof
allocated blocks, the inode table, and the first free inode.
The list of free inodes is embedded within the inode ta-
ble itself, with each free inode pointing to the next. Each
entry in the inode table stores traditional metadata about
afile such as mode and size as well as a pointer to three
linkedlists: anlset, aset, andan eset.
Links in LiFS are maintained in an lnode structure. As
shown in Figure 3, anlset contains a linkedlist oflnodes,
each of which contains a source inode, destination inode
and a set of attributes. The set ofattributes is a pointer to
an attribute set, oraset, shown in Figure 4. An aset con-
tains a linked list of anodes,eachofwhichhas a pointerto
the stringtableentryforthekeyand value of thatattribute.
supernode
diskBitmap
stringTable
inodeTable
freeList
lset
aset
eset
inode #0   
inode #1   
linkSet
attribSet
extentSet
inode #2   
inode #3   
inode #4   
inode table
Figure 2: Structure ofthe AnonFSsupernode
lset
last
first
lnode
src
dest
attribSet
lnode
src
dest
attribSet
Figure 3: A set of links from a file in AnonFS
aset
last
first
anode
key
value
anode
key
value
"author"
"chefsteve"
"editor"
string table
Figure 4: Aset of attributes in AnonFS
LiFS attempts to allocate disk space in extents—
sequential series of blocks. An extent set, oreset, shown
in Figure5,containsa linkedlistofenodes,each of which
specifies thelimits ofa single extent. When LiFSgrows a
file, it attempts togrowthelast extent if possible. If this i s
not possible,LiFS allocates a new extentandcorrespond-
ing enode. Free space is foundby scanning the bitmap of
allocated blocks contained in the supernode using first fit.
4 Implementation
ThenovelfeaturesofLiFSsuchas relational links require
modifications to the Linux Kernel. In Linux, the VFS
(Virtual File System)layerprovides access to file systems
for user mode programs. We added both kernel system
calls and VFSfunctions as required forournewfunction-
ality. All new system calls were based on the syntax of
similar existing operations.
application SDK tool:VB.NET PowerPoint: VB Code to Draw and Create Annotation on PPT
other documents are compatible, including PDF, TIFF, MS platform-friendly, this .NET PPT page annotating component more plug-ins needed like Acrobat or Adobe
www.rasteredge.com
application SDK tool:C# Excel - Excel Conversion & Rendering in C#.NET
independently, without using other external third-party dependencies like Adobe Acrobat. Excel to PDF Conversion. This page will tell you how to use XDoc.Excel
www.rasteredge.com
eset
last
first
enode
extent
enode
extent
Figure 5: AnonFS extent system for disk allocation
client application
user space daemon
Linux VFS
user space
kernel space
FUSE kernel module
Figure 6: The relationship between FUSE and the
FUSE/AnonFS userspace daemon
Our development process was made easier by use of
FUSE (File system in User Space). FUSE is a userspace
library and Linux kernel module that directs VFS calls
to a userspace daemon. Implementing LiFS in userspace
through FUSE freed us from the complexities of kernel
development,albeitwithconsiderableoverhead.Wemod-
ified FUSE to match ourchanges to the Linux VFS in or-
derto support the new functionality in LiFS. Once again,
the similarity in syntax and functionto existing interfaces
aided in development. As Figure 6 shows, LiFS resides
in a userspace daemon thatcommunicates with the FUSE
kernel module through a file in the Linux proc file sys-
tem. Bothournew calls and standard file system calls are
passed to the kernelvia this channel.
For this paper we were not able to procure sufficient
quantities of a non-volatile, byte-writable storage class
memory;instead we used system DRAM.The major con-
sequence ofthis approachis that manyoperations will run
faster than they would in storage class memories. In the
future, we will compensate for this speed up with arti-
ficial delays. The ability to model slower storage class
memories usingDRAM will allow us to simulate the per-
formance of LiFS across a wide variety of non-volatile
storage.
We assume that a storage class memory would be
mapped into an arbitrary segment of the system address
space. To imitate this mapping,we allocated several hun-
dred megabytes of system memory exclusively for LiFS
data structures. This memory is locked to prevent it from
being swapped out, based on the assumption that LiFS
will have enough storage class memory to hold all the file
system's metadata. All memory within this space is allo-
cated using a custom allocator. The allocator allows relo-
cation to arbitrary address spaces, anticipating the possi-
bility that a storage class memory could be mapped into
adifferent part of the system memory address space, per-
haps after the system was rebooted or the memory was
moved to a new machine. Since our metadata data struc-
tures are each a fixed size, we exploit this characteristic
by optimizing our custom allocator to preallocate several
pools of differentconstant size chunks. On memory allo-
cation, a chunk of memoryis retrieved from a pool of the
appropriatesize. Ondeallocation,thechunk is returned to
its pool. This allows for very quickturnaroundtimes.
Lookup operations in LiFS require resolution over all
links as opposed to solely being resolved over directory
structures. Consequently, lookups involve traversing a
series of inodes and lnodes beginning at the root inode.
Lookup is an iterative process which scans all links orig-
inating at its current node. If a link matches the corre-
sponding part of the input pathname, then the target of
that link becomes the currentnode. If no matching link is
found,an erroris returned.
We have implemented two optimizations to speed up
lookups. The first optimization checks that the current
pathcomponentis in the LiFSstringtable; ifitis notthere
then it can besafelyconcludedthat the lookup will not be
successful. The second optimization is a lookup cache
which stores full pathname to inode number mappings.
Because there is no need for persistence in this cache, it
is stored in DRAM as opposed to a storage class memory
which stores all other LiFS data structures. The lookup
cache is filled on successful lookups. Conversely, before
thelookupoperationbegins,a requestis madetothe cache
forthe appropiatepathname to inode mapping.
The core LiFS code has 3,400 lines of C code. Mod-
ifications to the FUSE kernel module and userspace li-
braries required additional code, but these changes were
necessitated by FUSE and would not be part of an in-
kernel implementation. The small size of our implemen-
tation may be attributedto the simplicityof storing all file
metadata as in-memory data structures. That the speed
of such a simple implementation can compete with more
application SDK tool:JPEG to PDF Converter | Convert JPEG to PDF, Convert PDF to JPEG
It can be used standalone. JPEG to PDF Converter is able to convert image files to PDF directly without the software Adobe Acrobat Reader for conversion.
www.rasteredge.com
application SDK tool:PDF to WORD Converter | Convert PDF to Word, Convert Word to PDF
PDF to Word Converter has accurate output, and PDF to Word Converter doesn't need the support of Adobe Acrobat & Microsoft Word.
www.rasteredge.com
File System
Create Files
Read Files
LiFS with FUSE
1.043
0.720
ext2 with FUSE
1.445
1.012
XFS with FUSE
3.998
1.050
Table 7: Create and read time, in seconds, for 15,620
zero-byte files (k
=
5,d
=
5,n
=
4). Timesshownare
the arithmetic mean of five testruns.
File System
Create Files
Read Files
LiFS with FUSE
12.195
2.027
ext2 with FUSE
2.613
1.679
XFS with FUSE
4.871
1.836
Table 8: Create and read time, in seconds, for 15,620
files (k
=
5,d
=
5,n
=
4)ofsize384bytes.Timesshown
are the arithmetic meanof five test runs.
optimized file systems such as ext2 (5,500 lines of code)
demonstrates the power ofstoring metadata in a fast byte
writable memory.
The simplicityofourimplementationandits speed sug-
gest the potential for significant performance improve-
ments with additional optimization. We already optimize
performanceand storage requirements using the stringta-
ble and other data structures which are not feasible in tra-
ditional disk-basedfile systems. We also plan to improve
scalability of LiFS by replacing the linked lists prevalent
in our implementationwith balanced trees.
5 Results and Performance
LiFS was implemented and evaluated on a pair of Sun
workstations running the Linux kernel 2.6.9-ac11. Each
systemwas configuredwithanAMDOpteron150proces-
sor running at 2400MHz and one gigabyte of RAM. For
testing, LiFS was compared with the XFS and ext2 file
system versions included with the Linux kernel. Bench-
mark testing was automated using Python version 2.3.4,
gawk 3.1.3 and GCC 3.4.2. All of the following tests are
run on freshly created file systems since the focus of this
paper is on the performance of in-memorydata structures
and not on disk sub-system performance.
5.1 Standard File System Operations
In order to compare the baseline performance of LiFS,
ext2andXFS,we used aset ofsix standardfile systemop-
erations: creating directories,creating files, reading fil es,
settingextendedattributes on files, retrievingextendeda t-
tributes from files and removing directories. Systematic
tests of these operations on each file system enabled a
faircomparisonbetweenLiFS,ext2 and XFS.Each of our
tests was run in kernel,through FUSE,on RAM-disk and
through FUSE on RAM-disk. LiFS is currently not run-
ning in the kernel and XFScannot be created on a RAM-
disk, thus these three scenarios (LiFS in kernel, XFS on
aRAM-disk, and XFS via FUSE on a RAM-disk) were
omitted. To compare these file systems, we created com-
pletek-ary trees ofdepthd, withnfiles perdirectoryeach
containinga extended attributes.
Table 7 shows LiFS performance forcreatingand read-
ing zerobyte files. Itis clear that LiFSis competitive with
ext2 throughFUSE and XFS throughFUSE in both tests.
Table 8 shows the same tests for files 384 bytes in size.
Theseresults show that LiFS is stillcompetitive withext2
and XFS in the area of file reads but falls behind in file
creation. This is due to the extentallocation scheme used
in thecurrentimplementation of LiFS. Foreach extent al-
location, the current implementation searches the list of
free blocks sequentially, starting fromthe beginning. The
results from these two tests indicate that a significantper-
formance gain can be expected from an optimized extent
allocationalgorithm.
Figures 9(a) and 9(b) show the performance of LiFS,
ext2,and XFS creating and retrieving extended attributes
on 15,620 files ( k
=
5,d
=
5,n
=
4). Figure 9(a) shows
the running time for two attributes set on each file, while
figure 9(b) shows the running times for twenty attributes
per file. In both cases, LiFS performs better than ext2
and XFS through FUSE. When setting twenty attributes
per file, LiFS takes roughly 70% of the time required by
ext2 under FUSE, while requiring about 73% of the time
needed by ext2 to retrieve attributes. These figures also
show that the running times for setting and getting file
attributesscale wellinLiFSas comparedtoext2 andXFS.
Directory tree creationperformance was tested bygen-
erating directory trees for various values ofk andd. Ta-
ble 10 shows the results of the test, demonstrating that
LiFSis comparableto ext2 and XFS. The runningtime of
directory creation scales linearly with the number of di-
rectories. This result is comparable to ext2 and XFS. In
addition,LiFS is faster than both ext2 through FUSE and
XFSthrough FUSE.
Figure 11 shows the performance of ext2 and LiFSun-
der FUSE and FUSE+RAM-disk. We were unable to cre-
ate and mount an XFS file system on a RAM-disk, thus
XFSis omitted. Sincethe file systemis recreated foreach
test, the first iteration was working with a cold cache. To
avoidextreme shifts inouraverages,we discardedthefirst
iteration and averaged over the remaining four. The re-
sults displayedin Figure 11 were taken from 4 runs of the
6file system operations over 111,110 directories with 1
zero-byte file per directory ( k
=
10,d
=
6,n
=
1). It is
clear from the tests of ext2 that a great deal of overhead
is incurred when all of the operations are performed on
disk. Because the operations performed in figure 11 use
(a) Setting and getting file attributes on 15,620 files ( k
=
5,
d
=
5,n
=
4,a
=
2). The times are in seconds and averaged
over 5 runs. RD indicates file system on RAM-disk. Note
thattheXFSrunstoset attributesbothtookover 21 seconds;
thegraph iscutoff at5 seconds to show details for theother
runs.
(b) Setting and getting file attributes on 15,620 files ( k
=
5,
d
=
5,n
=
4,a
=
20). Thetimes arein secondsandaveraged
over 5 runs. RD indicates file systemon RAM-disk. Again,
XFS, both with and withoutFUSE, was much slower, requir-
ing over 109 seconds to complete the set attributes bench-
mark. The graph was cut off to show detail for the other file
systems.
Figure 9: Time required to set and retrieve attributes
indifferent file systems.
Numberof Directories
File System
3,905 19,607 111,110
LiFS withFUSE
0.140 0.7882
4.292
ext2 with FUSE
0.226 1.2315
8.550
XFSwith FUSE
0.710 3.3193
25.285
Table 10: Create time, in seconds, for directory trees
ofvarious sizes. Times shown are the arithmetic mean
offive test runs.
0
19
38
57
76
95
114
133
AnonFS.ramdisk.fuse
AnonFS.fuse 
ext2.ramdisk.fuse
ext2.fuse
GetAttr
SetAttr
CreateFiles
CreateDirs
ReadFiles
Remove Dir
Figure 11: Running times of the 6 file system opera-
tions for ext2andAnonFSthroughFUSE. Results are
averaged over 4 runs on a 111,110 directory tree with
1zero-byte file per directory(k
=
10,d
=
6,n
=
1).
metadata exclusively, LiFS performs better than ext2 on
RAM-disk in all cases.
5.2 LiFS Specific Operations
Performance testing of the LiFS specific operations fo-
cused on three operations: creating a link between two
files, creating attributes for links and removing links. To
test the performance of these operations, we created a di-
rectory tree and constructed a random graph, where the
vertices are files and the edges are attributed links. A di-
rectory tree is built in the same manner as in our other
tests. The links are then created using a random number
generatorand a list of all of the files in the directory tree.
We tested the performanceoflink andlink attributecre-
ationon a directory tree having 15,620files ( k
=
5,d
=
5,
n
=
4). After creating the tree, 15,620 links are created
between randomlyselected files. Table 12shows the time
requiredto performa variety oflink operations for differ-
ent numbers of link attributes. The running times shown
in Table 12 are averaged over five runs. Link creation is
aseparate operation from the attribute creation and thus
the average runningtime is not affected by the number of
attributes.
The time required to remove links, shown in Table 12,
demonstrates the results of a data-structure design choice
in the version of LiFS used for testing. When removing
alink between two files, a
key
,
value
pair is specified
to unambiguously identify a link. This is due to the fact
that LiFS allows for multiple links to be made between
the same two files. The
key
,
value
pairs are currently
stored in a linked list data structure and thus attribute re-
trieval must, on average, search through half of the link's
key
,
value
pairs. This results in the increased time re-
Attributes per Link
Operation
2
30
Create Links
1.073
1.054
Create Attributes
1.148
2.751
Remove Links
1.086
1.288
Table 12: Time in seconds to create 15,620 random
links over a directory tree (k
=
5,d
=
5,n
=
4)with
2and 30 attributes on eachlink.
File System
Avg(sec)
ext2
22.52
ext2through FUSE
23.40
ext2through FUSE on RAM-disk
23.95
LiFSthrough FUSE
24.28
LiFSthrough FUSE on RAM-disk
23.75
XFS
23.20
XFS through FUSE
23.49
Table 13: Compile times for OpenSSH4.1 (inseconds)
on a variety of file systems. Times reflect the arith-
metic mean of five trial runs.
quiredtodelete a linkwith 30attributes versus a link with
only 2 attributes.
5.3 SSH Compile Performance
To demonstrate the performance of LiFS in a practical
scenario, we compiled OpenSSH version 4.1 using GCC
3.4.2. As Table 13 demonstrates, LiFS running through
FUSE is competitive with other file systems in tests both
with and without a RAM-disk. Compiling OpenSSH on
aLiFS file system running though FUSE took 24.28 sec-
onds. Ext2 through FUSE took 23.40 seconds and XFS
through FUSE required23.49. In a complex series of op-
erations,such as compiling a non-trivialsource tree,com-
pletion time is notstrictlyboundedby the file system. Our
results show that in such a scenario the extended capabil-
ities of LiFS do not incur an overhead that introduces a
new bottleneck tothe system.
The OpenSSH compile times show a relatively minor
performance hit when running through FUSE. This is to
be expected, as compiling a source tree is not bound by
disk performance. A more dramatic example of perfor-
mance gained by eliminating the FUSE layeris shown in
Table 14. Reading files without the FUSE layer was over
3.3 times faster for both XFS and ext2. For file and di-
rectory tree creation the ext2 file system showed a much
more dramatic performance gain compared to XFS. It is
therefore difficult to speculate on the exact performance
gain that can be expected by eliminating the FUSE layer
inLiFS.However,wecanassumebasedonourtest results
that the gain wouldbe nontrivial.
Another source of potential performance increases for
Operation
ext2-FUSE
ext2
Speedup
Create Tree
0.2262
0.080
2.828
Create Files
2.613
1.146
2.280
Read Files
1.679
0.474
3.542
Operation
XFS-FUSE
XFS
Speedup
Create Tree
0.709
0.650
1.091
Create Files
4.872
4.282
1.138
Read Files
1.837
0.541
3.396
Table 14: Speedup ratios for selected operations com-
paring file systems through FUSE versus the same file
system withouta FUSE layer. Times shownare arethe
arithmetic meanof five test runs.
LiFS involves the data structures utilized in the current
implementation. The version of LiFS utilized in the test-
ing presented here makes extensive use of linked lists.
This includes frequently accessed information such as at-
tribute lists. This will obviously incur a performance
penalty whenaccessingan attribute as,onaverage,halfof
the list must be traversed. This behavior is demonstrated
in the amount of time required to remove a link as shown
in Table 12. There is no design restriction which prevents
the use of balanced trees in place of linked lists. Thus a
performance increase would be expected by transitioning
fromlinked list data structures to balanced tree data struc-
tures.
5.4 Discussion
We have shownthat the runningtimes formetadata-based
operations in LiFS are faster than ext2 and XFS, while
those requiring disk allocation are slower. These results
are to be expected because our metadata structures reside
in memory and the disk-based data structures are not yet
optimized. The LiFS-specific operations regarding link
and link-attribute creation have also shown to scale well
and run in a reasonable amount of time despite our unop-
timized implementation. We have shown that LiFS per-
forms well in a real-world situation, by comparing the
running times of a OpenSSH build on LiFS, ext2 and
XFS.These results indicatethatLiFS canbe used in place
of most existing file systems without incurringadditional
overhead.In this section we have also discussed the over-
head associatedwith FUSE.We expect that animplemen-
tation of LiFS running in-kernel with optimized disk al-
location algorithms be significantly faster than tradition al
file systems. In addition, the new operations introduced
by LiFS should be similar in speed to existingoperations.
6 Related Work
The concepts we use in the current and previous designs
forLiFSborrowfromvarious research areas rangingfrom
semantic file systems to databases and the Web [2]. We
first look at file systems with queryable metadata, such
as semantic file systems, and file systems designed to run
in nonvolatile memory. We then touch upon upcoming
advancedcommercial systems. Finally we look at the Se-
mantic Web and archiving, and how they try to convey
knowledge more accurately and forthe long term.
6.1 Semantic and Other Queryable File
Systems
The Semantic File System [21] was originallydesignedto
provide flexible associative access to files. File attribute s,
expressed as
key
,
value
pairs, are extracted automati-
cally with file type-specific transducers. A major feature
ofthis work is the concept ofvirtualdirectories,in which
auser makes an attribute-basedquery and the system cre-
ates a set of symbolic links to the files in the result set,
providing access that crosses the directory hierarchy. A
similar file system, Sedar [29], is a peer-to-peer archival
file system with semantic retrieval. Sedar introduces the
idea of semantic hashing to facilitate semantic searching
and reduce storage andperformance costs.
The Inversion File System[33] uses a database to store
both file data and metadata. The database also provides
transaction protection, fine-grained time travel, and in-
stantaneous crash recovery. Each file is identified by a
unique ID, but also has a name and directory associated
with it. Moreover,Gupta,etal.[22] cite the difficulty of
managing different but related sets of files as motivation
for their fan-out unification file system, in which fan-out
unification refers to merging two directories, and implic-
itly, entries in a directoryare treatedas members of a set.
The Logic File System (LISFS) uses a database to sup-
port queries for sets of files in the system [35]. Database
tables are composed of mappings from keywords to ob-
jects. The contents of a directory is the set of objects that
meets the criteria ofthe relation in a query.
Like the above mentioned file systems, the use of
attributes in LiFS allows a user to perform expressive
queries to locate files. However,these file systems all use
secondary storage for metadata, either with or without a
database, and must operate under such performance con-
straints. Additionally, none contain a linking mechanism
that supports attributes, thus allowing inter-file relatio n-
ships that canexpress the structureofthe Web orestablish
data provenance and history.
6.2 In-Memory File Systems
Douglis,etal. compared various storage alternatives for
mobile computers and foundthat flash memory exhibited
low power consumption while still providing good read
and acceptable write performance [16]. Their focus how-
ever was on power consumption and assumed traditional
file system functionality.
Conquest [50] utilizes persistent RAM for storage of
metadata and small files. Unlike HeRMES and LiFS,
which plan to utilize MRAM, Conquest has explored the
use of battery-backed DRAM as its form of persistent
RAM. The eNVy system and the work of Kawaguchi
et al.exploredtheuseofflashmemoryasaprimarynon-
volatile memory storage system [52, 24]. All of these
these systems, however, present a traditional file system
that lacks the advanced file system features facilitated by
utilizing persistentRAM.The HeRMESsystem[32] pro-
posed that magnetic RAM (MRAM) be used to store file
system metadata, and proposed different metadata struc-
tures to take advantage of MRAM; however, HeRMES
was not implemented, so many of the ideas remained
untested.
File system on persistent memory presents a new set
of challenges compared to magnetic disk storage. To
this end much research has been performed to overcome
these challenges. David Lowell's Rio Vista project pro-
vides atomicityformemoryaccess operations in the form
of transactions [27] while the Journaling Flash File Sys-
tem (JFFS) takes a slightly different approach with a
log-structured file system for flash memory [51]. Edel,
et al.[17]notedthatmetadataoverheadforafilesystem
is 1–2percentandsuggestedthe space requirements could
be reduced usingvarious compressionschemes and algo-
rithms, demonstrating that inode storage space could be
reduced by an order of magnitude. They also found that
there was no significant difference in performance com-
pared to non-compressed metadata.
Database performance has also been an area that re-
searchers have hopedto improve throughpersistent mem-
ory. Molina and Salem have explored various ways that
memory residence optimization could improve data ac-
cess performance [20].
6.3 Advanced Commercial File Systems
WinFS is Microsoft's in-development file system, for
which they have published a preliminary description of
planned features
1
. WinFS appears to be a marriage of a
database for metadata and NTFS for file stream perfor-
mance. WinFS treats the contents of the file system as
Itemsthatcoverafullrangeofgranularityfromsimple
descriptions to collections such as folders. The database
backing allows SQL-type queries, XPATH searches [14],
and the use of Microsoft's OPATH, a query language de-
signed for a directed acyclic graphs [39].
1
This
comes
with
the
caveat
that
all
is
sub-
ject to
change.
Further information
is available at
http://longhorn.msdn.microsoft.com/portal
nav.htm
Documents you may be interested
Documents you may be interested