Volume Data: 993,441 files Volume Size: 17,179,869,184 bytes underlay overlay time fetches bytes msec/fr ext2 posix 600.002 28,687 4.96403E+08 250.649 ext2 hayfs 600.001 44,704 7.71776E+08 183.010 ext2 nibfs 600.002 44,360 7.66797E+08 195.582 none nibfs 600.000 46,491 8.03576E+08 216.952
NIBFS over ext2 offers 55% speedup over posix.
Volume Data: 496,722 files Volume Size: 8,589,934,592 underlay overlay time fetches bytes msec/fr vs psoix ext2 posix 600.002 36,141 6.24755E+08 153.138 1.00000 ext2 hayfs 600.001 51,257 8.86077E+08 159.981 1.41825 ext2 nibfs 600.000 50,686 8.78318E+08 168.631 1.40245 none nibfs 600.001 50,941 8.80336E+08 193.034 1.40951 xfs posix 600.000 35,686 6.17575E+08 135.529 1.00000 xfs hayfs 600.000 50,589 8.73876E+08 162.515 1.41761 xfs nibfs 600.000 51,432 8.90027E+08 171.802 1.44124 reiser posix 600.000 43,788 7.57544E+08 32.151 1.00000 reiser hayfs 600.000 51,517 8.90208E+08 154.624 1.17651 reiser nibfs 600.003 51,014 8.81863E+08 164.888 1.16502
I am still disappointed by the lack of speedup when using no underlying filesystem. I suspect that this is due to the i-node meta-data being cached by the operating system when the volume is first opened.
Volume Data: 248,361 files Volume Size: 4,294,967,296 underlay overlay time fetches bytes msec/fr vs psoix ext2 posix 60.000 3,937 6.76426E+07 120.248 1.00000 ext2 hayfs 60.000 6,003 1.04302E+08 145.734 1.52477 ext2 nibfs 60.000 5,912 1.02162E+08 150.897 1.50165 none nibfs 60.001 5,340 9.23046E+07 191.841 1.35636 xfs posix 600.001 45,241 7.82266E+08 44.483 1.00000 xfs hayfs 600.000 58,868 1.01682E+09 136.545 1.30121 xfs nibfs 600.001 58,105 1.00484E+09 144.866 1.28434 reiser posix 600.002 50,454 8.72211E+08 5.205 1.00000 reiser hayfs 600.000 58,025 1.00311E+09 133.468 1.15006 reiser nibfs 600.000 57,645 9.96119E+08 141.392 1.14253
NIBFS is slightly slower than HAYFS, but I think that this is within the margin for error. More tests will verify this. The significance of this difference should decrease as the volume size grows and the processes become more I/O bound.
I am suspicious of the "no underlying FS" data. It should be faster than ext2. The direct block level disk access has been giving me problems for a long time, and I believe that it is the source of most of my script failures.
I originally ported everything to Linux due to it's "a device is a file" promise for ease of direct access. This has proven to be less than true....
I have some initial data for a 1 MB volume. These numbers aren't meaningful, they were mostly in place to ensure that my test scripts were working correctly. I'm going to use them as a baseline to look for significance in differences from larger test sets. I don't expect to see meaningful trends for volumes less than 2GB, and the usage scenarios suggest minimum volume sizes of 10GB.
Volume Data: 63 Files size underlay overlay time fetches bytes msec/fr 1,048,576 ext2 posix 60.0014 133,170 2.30208E+09 4.50525 1,048,576 ext2 hayfs 60.0007 135,290 2.34126E+09 4.43462 1,048,576 ext2 nibfs 60.0001 122,100 2.11192E+09 4.91278 1,048,576 none nibfs 60.0006 123,281 2.13362E+09 4.86837
These figures are a little misleading. NIBFS is shown to be the slowest, but this is probably due to NIBFS trading lower space requirements for higher time requirements -- which are not benificial at these sizes. All of the filesystems were at 100% CPU utilization as all of the test data fit easily into cache. When I have gotten larger test sets to run, NIBFS uses less than 10% CPU, spending all of it's time in I/O wait (which justified the design goal of minimizing seeks).
I'm having major problems with data collection. It's been one problem after another. Whenever I run a single test manually, everything works perfectly. Every time that I've tried to run a collection of tests, they fail for one reason or another. Large files won't be made correctly (fixed last night); a processes won't be killed (and will therefore hold a file handle, will prevent unmounting of my test volume, which will stop the progress of the tests); everything will appear to work correctly, but the test transcript will reveal that 0 bytes were transferred, and the fetch count will be double what it should be; the script will hang for no apparent reason; the script will be stuck for several hours, then resume for no apparent reason; or the newest one, the machine will completely lock overnight.
Because of these problems, I've pretty much lost every reason for originally writing the app in C, or running it on linux.
I'm proceeding to write the report without data, in the hopes that by the time that I'm done, I will have some data that worked.
I've abandoned testing on NTFS. Linux support is very poor, and the data which I have gathered from it so far is several orders of magnitude slower than ext2. Furthermore, large cluster sizes on NTFS are a full order of magnitude slower than small clusters, which is the opposite of the expected. I've decided that the limitations of Linux make these results meaningless.
I've spent the better part of the last three or four days trying to track down a cross-platform large file support issue.
I could not create a nibfs or hayfs file on ext2 that was larger than 2 GB through my drivers (and I did not advance to trying other filesystems). But, I had a test case that was creating a 5GB sparse file on ext2. It took me forever to track down. I traced the code right down to the call to pwrite() in both cases, everything looked identical on input, but the output differed. One would treat the off_t as 64 bit, the other would silently wrap it around to 32 bits. All compiler flags were identical (thanks to my build script). What made it worse is that this bug only occurred in Linux. It worked fine under Windows.
I finally had a moment of insight when I wrote another test case that would hack nibfs and make it's next-free-space pointer advance beyond 4GB, then try to store a file. This one failed. I realized that my original "test case" was in a .cpp file, and that my filesystem drivers were all in .c files. This meant that my test case was being compiled by g++, whereas my production code was being compiled by gcc. A quick dummy test outside of the project revealed that g++ supported large files properly, but gcc did not.
I tried changing my default compiler to g++ for everything, but a long list of errors made me backtrack. A few dozen googles turned up this: Large file support - Linux/gcc. I had always had the -D_FILE_OFFSET_BITS=64 flag, I had tried the -D_LARGEFILE_SOURCE flag (to no avail). I had never seen the -D_GNU_SOURCE flag. It was not mentioned on the Large File Support in Linux page, which had been my touchstone throughout the ordeal. Adding it fixed my problem.
I'm having a lot of problems with cross platform issues. Mostly type related. I kinda wish I had done it in java now...
I've had to stop using some defined types.
There's issues around uint32_t, for some reason, I can't make structs containing them. I've replaced all of the uint32_t with u_int32_t, which seems more portable. They generate warnings, but they run and pass tests.
Another issue was that I had used off_t in a few places that weren't really offsets, but were explicitly 64 bit numbers. I have replaced all of these with u_int64_t.
Finally, I have to compile with the -D_FILE_OFFSET_BITS=64 flag to enable offsets to be 64 bit to support volumes greater than 2 GB.
To make sure that nibfs and hayfs had the best opportunities to test well, I needed a dedicate partition that could be erased between each test run.
My test platform is my old development machine. An AMD Athlon 1Ghz with 1GB of memory and an 80GB UDMA5 hard disk. The disk is partitioned with a 47GB (sda4) dedicated partition for the test files. I would have liked to have used a more modern system for testing, but my resources are currently limited.
The test partition is cleared between each run with the follow commands:
unmount /dev/sda4 dd if=/dev/zero of=/dev/sda4 bs=1M count=16
The tests are conducted under three file systems:
The default linux filessytem with the following parameters (to reflect a "normal" filesystem)
mkfs.ext2 -b 4096 /dev/sda4
A server oriented filesystem.
mkfs.xfs -b size=4096 /dev/sda4
Linux will not mount XFS filesystems with larger block sizes.
The Windows filesystem with default cluster sizes.
mkfs.ntfs -f -c 4096 -I /dev/sda4
the Windows filesystem with large cluster sizes.
mkfs.ntfs -f -c 65536 -I /dev/sda4
A physical device with no underlying file system. (This can only be used by nibfs since it does not rely on any filesystem services.)
The ext2, xfs, and ntfs filesystems are mounted with the following options:
mount
-o noatime,nodiratime,noauto,noexec,nomand,rw
/dev/sda4 /tmp/httpd
The created filesystem is populated with test data through a tailored script for each overlaid filesystem type.
Populating the filesystems with test data takes a very long time. Because of this, I am currently using test volumes of 1MB, 1GB, 4GB, and 8GB.
Since this project was inspired by web-archival systems, I've written a test harness that follows the same usage model.
The test data is three image files of sizes 12KB, 19KB, and 21KB (chosen to represent tha average size of images are reportedly stored on image archival systems). These files are repeatedly placed into the test file systems until it reaches the desired sized. A volume that exceeds 4 GB should be tested to ensure no limits on volume sizes.
The testing application is a simple, multi-threaded, HTTP web server. The webserver is constructed to receive requests for files stored in on of the test filesystems and to retrieve them. Files are piped between the filesystem and the request socket with no copy of data to user space.
The test driver is an HTTP load generator, http_load (1, 2). The generator creates a number of concurrent HTTP requests, and measures the capacity of the web server.
| nibfs vs hayfs | nibfs vs posixfs | |
| fetches / second | same | better |
| bytes / second | same | better |
| msecs / connect | same | same |
| msecs / first-response | worse | ??? |
| processor utilization | ??? | ??? |
| memory use | better | same |
I've implemented three filesystems for testing/comparison purposes: nibfs (the subject of this research), hayfs (a re-engineered version of haystack) and posixfs (a normal hierarchical filesystem).
The three filesystems all have slightly different interfaces reflecting their differing input parameters, so I have wrapped them by one common API which abstracts the differences:
struct refFS {
/** create a filesystem at the given location.
* @param path (in) the location of the filesystem
* @param size (in) the desired size of the volume (ignored)
* @return a handle to the file system
*/
void* (*create)(const char* const path, const off_t size);
/** opens the filesystem at the given location.
* @param path (in) the location of the file sysem
* @return a handle to the filesystem
*/
void* (*open)(const char* const path);
/** Closes the given filesystem.
* @param fs (in) the handle to the filesystem
*/
void (*close)(void* fs);
/** Stores a file into a file system.
* @param fs (in) handle to the filesystem
* @param dstPath (out) the path to the stored file
* @param src (in) the file to be stored
* @return negatife iff failure
*/
int (*put)(void* fs, char* dstPath, const extFile_t src);
/** Retrieves a file from the filesystem.
* @param fs (in) handle to the filesystem
* @param dst (out) handle to the retrieved file
* @param srcPath (in) the path to the stored file
*/
int (*get)(const void* const fs, extFile_t* dst, const char* const srcPath);
};
typedef struct refFS refFS_t;
struct extFile {
int fd;
off_t offset;
off_t length;
char name[MAX_FILENAME];
};
typedef struct extFile extFile_t;
I've constructed my own haystack system for comparison. I've changed some things from the original to make the comparison fairer. Duplicate, redundant, and unneede data has been eliminated. As has some data that would make haystack work harder than nib does (computing check-sums, etc). The format is as follows:
| uint64_t | next |
| uint64_t | num |
| uint64_t | size |
| uint64_t | reserved |
| (index entry)* | |
| uint64_t | key |
| uint64_t | offset |
| uint64_t | length |
| uint32_t | nonce |
| unsigned char | data* |
read(paths[x]) -> files[x]
paths[x] is a list of paths into nibFS. They contain the offset, length, filename, and MAC of teh file as returned when the file was originally written.
struct nibFile {
int fd; // stream to the desired file (the nib volume)
off_t offset; // offset of the file in nib volume
off_t length; // length of file data
char filename[]; // filename in nibFS
unsigned int macLen; // length (in bytes) of the MAC for this file path
unsigned char mac[]; // MAC for this file path
}
files[x] are file handles to files from the volume. On success (the input path was valid, as verified by the MAC), these are populated wit information to extract the file from the volume. On failure, the returned fd is -1.
struct extFile {
int fd; // stream to the file contents
off_t offset; // starting position in the stream
off_t length; // length of file data
char filename[]; // desired name of the file on nibfs volume
}
For committing a file to NIBFS, we want a function that takes a list of files and returns the list of paths indicating where they were stored.
write(files[x]) -> paths[x]
files[] is a list of files to be written. They contain the file data (or a handle to it), and a desired filename. An optional length field can be used for pre-allocating space on the volume, or when combined with an optional offset, specify that only a subsection of the file should be copied.
struct extFile {
int fd; // stream to the file contents
off_t offset; // starting position in the stream
off_t length; // length of file data
char filename[]; // desired name of the file on nibfs volume
}
paths[] is a list of references to the location of the written file in nbifs.
struct nibFile {
int fd; // stream to the desired file (the nib volume)
off_t offset; // offset of the file in nib volume
off_t length; // length of file data
char filename[]; // filename in nibFS
unsigned int macLen; // length (in bytes) of the MAC for this file path
unsigned char mac[]; // MAC for this file path
}
The MAC is the MAC as computed by the MAC algorithm specified in the NIBFS volume header:
mac[] = MAC(offset||length||filename)
Where:
MAC is the MAC algorithm specified by the NIBFS volume header
|| is the concatenation opperator
offset is the target offset in 64 bit binary big-endian
length is the target length in 64 bit binary big-endian
offset is the target name as an ASCII string (non-terminated)
On success, each file is committed to the volume and written to disk:
On failure, the returned path object has a fd of -1.
| byte | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 0 | "NIBFS\0" | ver | uint64_t serialNo | |||||||||||||
| 16 | char[32] label | |||||||||||||||
| 32 | ||||||||||||||||
| 48 | uint64_t opened | uint64_t closed | ||||||||||||||
| 64 | char[6] res | dl | kl | char[8] MAC family | ||||||||||||
| 80 | char[16] MAC algorithm | |||||||||||||||
| 96 | char[32] res | |||||||||||||||
| 112 | ||||||||||||||||
| 128 | uint64_t size | uint64_t next | ||||||||||||||
| 144 | uint64_t num | char[8] res. | ||||||||||||||
| 160 | char[16] res | |||||||||||||||
| 176 | char[64] MAC key | |||||||||||||||
| 192 | ||||||||||||||||
| 208 | ||||||||||||||||
| 224 | ||||||||||||||||
| 240 | char [272] res | |||||||||||||||
| ... | ||||||||||||||||
| 512 | ||||||||||||||||
The single byte values dl and kl are unsigned and represent "digest length" and "key length" respectively.
All multi-byte values are stored in network byte order (big endian).
Our URL was of the form:
volume=vvv,offset=oooooooo,length=llllllllll,mac=mmmmmmmmmmmmm
| field | bits | ||
| min | max | likely | |
| volume | 16 | 32 | 32 |
| offset | 32 | 64 | 64 |
| length | 32 | 64 | 32 |
| mac | 160 | 512 | 224 |
| bits | digits | |||
| decimal | hex | percent | base64 | |
| 32 | 10 | 8 | 12 | 5.3 |
| 64 | 20 | 16 | 24 | 10.6 |
| 160 | 49 | 40 | 60 | 26.6 |
| 224 | 68 | 56 | 84 | 37.3 |
| 512 | 155 | 128 | 192 | 85.3 |
For small numbers (up to 64 bits), it appears completely feasible to encode the value in hexadecimal. Encoding the MAC in hexadecimal would require 56 digits which may result in undesirably long URLs. Using encoding methods such as quoted-printable, uuencoding, yenc, ascii85 or standard base64 would all generate characters that are not URL safe (defined in RFC3986 - Uniform Resource Identifier (URI): Generic Syntax) and therefore not suitable for our use. An URL and filename safe variant of base64 (defined in RFC4648 - The Base16, Base32, and Base64 Data Encodings) could reduce the encoding length of the MAC to approximately 40 characters.
The analysis of requirements tells us that filenames should be user meaningful. We propose to include the filname in the URL
The analysis of requirements tells us that paths may be non-meaningful, so we have chosen to encode the volume ID, offset, length, and MAC into the path. Our encoded path is as follows:
/vVVVVVVVV/mMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM/oOOOOOOOOOOOOOOOO/lLLLLLLLL/filename.ext
Volume ID is placed first to support replication and load balancing.
MAC precedes offset, length and filename so that their concatenation used to build the URL can be passed directly into the MAC algorithm.
The MAC protects the filename (not just the offset and length) to prevent user embarrassment from attackers distributing URLs where only the filename was changed (since the filename is not required by the file system to read the file). Imagine:
.../o457/l215/meeting_of_flat_earth_society.jpg
as opposed to
.../o457/l215/meeting_of_math_society.jpg.
The MAC does not precede or protect the volume ID since a volume may not know its ID. Volumes should not know their IDs to encourage volume portability between systems. Each volume does know its MAC algorithm and the parameters to that algorithm, so MACs for the same offset, lenght, and filename can have different values. This should be encouraged to limit the impact of birthday attacks.
Values are separated by a path separator rather than passing them as query arguments to make the path cachable and usable through content distribution networks.
A Message Authentication Code (MAC) is a sort piece of information used to verify the integrity and authenticity of a message. A message is generated and the generated MAC is used to detect tampering (either deliberate or accidental) with the message. Any changes to the message would generate a different MAC. They differ from digital signatures in that they do not provide non-repudiation, which is not required by our system.
We have chosen to use an keyed-Hash MAC (see RFC2104 - HMAC: Keyed-Hashing for Message Authentication) to provide our URL authentication. An HMAC combines a public message with a fixed hash function, and a secret key to securely establish the integrity and authenticity of a message. An HMAC is a function of the form HMAC(h,k,m) where h is a fixed underlying hash function, k is a secret key, and m is a public message. Secure HMACs are resistant to existential forgery under chose-plaintext attacks, and the security of an HMAC lies in the security of the underlying hash function h.
HMACh,K(m) = h[ (K⊕opad) || h((K⊕ipad)||m) ]
HMAC was chosen due to its wide-spread use in other protocols, the existence of universal standards, extensive cross-platform library support, and extensive review in the cryptography field. Due to the MAC specification in the header of each volume, HMAC can be replaced with other MAC schemes (UMAC, CMAC or digital signatures) if desired or warranted.
For out initial version, we have chosen to use SHA-224, the smallest hash function in the SHA-2 hash family (see RFC4634 - US Secure Hash Algorithms (SHA and HMAC-SHA)). SHA-2 was chosen over SHA-1 and MD5 due to recent attacks against the latter algorithms. SHA-2 was chosen over RIPEMD due to SHA-2's wider use in government and industry, and more scrutiny in the field of cryptography. Extensive cross-platform libraries for SHA-224 are available. The hash function h is as changeable as the choice of HMAC over other MAC schemes. A new hash function simply has to be specified in the volume header, allowing for RIPEMD, MD5, SHA-1, or even SHA-512 to be used instead.
The original design goals combined with the analysis of requirements suggest that the best way to build our file system is to have a file-system with no meta-data. This is possible since we can encode the meta-data into the URLs and since our files are contiguous.
When files are guaranteed to be contiguous, all that is required to read a file is a device (or volume), an offset into that volume, and the length of what is to be read. In Haystack's case, this is accomplished with an OID that is a reference into an index which contains the offset and length of the file (indexes are matched to each volume, which is also specified in the URL). We propose to eliminate this index entirely, and encode the volume, offset, and length directly into the URL.
With Haystack, we have a mapping of the form:
volume=264,uid=122608936,pid=35954776,n=3971 -> volume=264,offset=oooooooo,length=llllllllll
In our design, we only have the URL:
volume=264,offset=oooooooo,length=llllllllll
With this design, we have lost the ability to detect invalid URLs (previously detected by comparing the nonce), and we have no ability to mark a file as deleted (previously noticed by removing the mapping from the index file). Additionally, we have allowed an adversary to read our entire volume by requesting a read from offset zero to the length of the volume.
See Threat Model.
We could solve these problems immediately by encoding a header at the front of each user file containing a bit pattern marking the start of the file, a nonce to prevent random guesses, and a length to prevent over-reading. An additional flag (or reserved values) could indicate if a file has been deleted. The problem with this approach is that an adversary can upload arbitrary data onto our volume, so they could fake the start of a file header. An attacker could craft a custom file containing a forged file header, then request a read starting at that forged header. They would then be free to read the rest of the volume based on their forged "length" field.
We cannot maintain a list of valid headers since our goal is to minimize reads and meta-data. One option is to attach a cryptographically secure Massage Authentication Code (MAC) to the file header, but this feels heavy-handed since it is adding more meta-data to the disk, and one of our design goals was to minimize meta-data.
Instead, we observe that we have already shifted the volume, offset, and length meta-data into the URL, so we propose to encode the MAC into the URL as well. We are left with an URL containing:
volume=264,offset=oooooooo,length=llllllllll,mac=mmmmmmmmmmmmmmmmmm
A cryptographically secure MAC will authenticate the message contained in the volume, offset, and length fields. Any changes to these fields will be detected by the system when it verifies the MAC, and the request can be rejected.
Deleted files are still indicated by a header for each file on the disk. This is necessary since the URLs now act as capabilities. The "deleted" flag in the header serves as a way to revoke a given capability.
We are not concerned about reclaiming the space of the deleted file since deletions are so rare in our operating environment / usage model. It would be possible to fill deleted file entries on the disk with smaller files as long as care was taken to leave the old file header in place to prevent the old URL (capability) from reading the new file.
To maintain extensibility of our file system, we also encode a small header onto the volume. This header contains details such as the file system version number, the location of the next byte of free space on the volume, the size of the volume, and the type of MAC used and its parameters (ie, the secret key).
NIBFS := volHead , file*
volHead := identifier, volumeDat, mac
identifier:= "NIBFS" , |version|
volumeDat := |next free| , |size|
mac := |mac family| , |mac algorithm| , |mac parameters|
file := fileHeader, |data|
fileHead := |deletedFlag|
We do not encode version numbers into file headers since it is assumed that all files on a volume will be written with the same encoding scheme.
(See RFC2119 - Key words for use in RFCs to Indicate Requirement Levels for definition of terms.)
For photos:
| /v264 | volume ID |
| /134/79 | hashing user ID (and volume?) |
| /122608936 | user ID |
| /s | size |
| 122608936 | user ID |
| _35954776 | photo ID |
| _3971 | nonce |
| .jpg | extension |
Note: Profile images are the same except they have no photo ID.
The nonce prevents users from guessing photo IDs to retrieve photos for which they do not have the URL.
| FB | Fkr | PB | Pcs | Blgr | ImSh | 4chn | GVd | UTb | |
|---|---|---|---|---|---|---|---|---|---|
| volume ID | y | y | y | ? | y | y | na | ? | ? |
| OID | y | y | ? | ? | y | y | y | ||
| hash | y | y | y | y | ? | ? | |||
| size/type | y | y | y | y | y | y | y | na | na |
| meaningful name | y | y | y | y | |||||
| meaningful path | ? | ? |
Nearly all of the URLs contain a volume ID, object ID, a hash, and a size indicator. Half of the files have user meaningful filenames, nearly none have user meaningful file paths [Note: Photobucket's path is almost user meaningful].
We can conclude that a user meaningful path is not important, but that a user meaningful name may be important.
The choice to encode a size into the URL is curious. The URLs have been obfuscated to make them meaningless to humans, so the convenience of having the size in the URL is suspect. Why isn't it just a new OID for a different size? Is it to save database space?
Profile main: /v227/1898/9/n122608936_4007.jpg Profile thumb: /v227/1898/9/q122608936_4007.jpg Photo preview: /v264/134/79/122608936/s122608936_35954776_3971.jpg Photo fullsize: /v264/134/79/122608936/n122608936_35954776_3971.jpg
Square: /3183/2741581551_d880652a94_s.jpg Thumbnail: /3183/2741581551_d880652a94_t.jpg Small: /3183/2741581551_d880652a94_m.jpg Medium: /3183/2741581551_d880652a94.jpg Large: /3183/2741581551_d880652a94_b.jpg Original: /3183/2741581551_635b7937dc_o.jpg
Thumbnail: /v489/btraffordphotos/th_courchette.jpg Regular: /v489/btraffordphotos/courchette.jpg
Thumbnail: /stefan.venken/RmMYbnPG8jI/AAAAAAAAAEk/67mIOiiqQQc/s144/IMG_0809.JPG Regular: /stefan.venken/RmMYbnPG8jI/AAAAAAAAAEk/67mIOiiqQQc/IMG_0809.JPG?imgmax=800 Full: /stefan.venken/RmMYbnPG8jI/AAAAAAAAAEk/67mIOiiqQQc/IMG_0809.JPG
Preview: /_LMD_FWTpU20/SJfIrMvYluI/AAAAAAAACdU/TIUy41cHDhQ/s400/babies.png Full: /_LMD_FWTpU20/SJfIrMvYluI/AAAAAAAACdU/TIUy41cHDhQ/s1600-h/babies.png
Thumb: /img218/4986/trekmap2kx6.th.jpg Orig: /img218/4986/trekmap2kx6.jpg
Thumb: /thumb/1218485801983s.jpg Orig: /src/1218485801983.jpg
Video: http://vp.video.google.com/videodownload?
version=0&
secureurl=QwAAAKc1kG4k3fDzX0HQCYLZKsLgZIMUkQtxSXAnVzYu4oqfKe6HX_gvRfkc6ZFOjMvzskDmZ2ASBD7l0ip63BP2cadn-ve91LnxjhRbDBdSoCYU&
sigh=d1vSouyOc5JUCth2U5WaBmwV9-4&
begin=0&
len=1164400&
docid=7881889424111915182
Thumbnail: http://2.gvt0.com/ThumbnailServer2?
app=vss&
contentid=fc27bfabd9ac3c46&
offsetms=205000&
itag=w160&
hl=en&
sigh=bqSOML5Isily84nptlPSC7Dtk8k
DocID: 7881889424111915182
q=TEDTalks: Barry Schwartz (2005)& vq=null& sourceid=ys& video_id=VO6XEQIsCoM& l=1222& sk=kNZ78tqnMiFDszzHbaZ5LQVdn6uywO5yC& fmt_map=& t=OEgsToPDskJ2kEBKln1r3P9LxFGzcxyJ& hl=en& plid=AART6iY_CTzc3kkSAAAAoAAoAAA& playnext=0& enablejsapi=1
The efficiency of Haystack hinges on index file being in memory. With the index in memory, files can be retrieved with 1 disk I/O. If the index is not in memory, at least 2 disk I/Os are required (one to read the index, one to read the file). Note: the keys into the index are not offsets into the index, so it would be best to re-load the entire index file.
Assuming the given index ratio of 1024:1, the system has the following memory requirements.
| scale | haystack size | index size |
| 540 TB | 540 GB | |
| Performance Server | 16 TB | 16 GB |
| Commodity Server | 4 TB | 4 GB |
| Haystack file | 10 GB | 10 MB |
The index file looks like a single layer of a B-Tree. It is an index to leaf nodes of data.
A haystack is a blob indexed by a separate index file.
The index (meta-data) to file data ratio is reported to be 1 : 1024.
haystack = |file|*
file = |header| data |footer|
header = version, magic number, length
footer = checksum
| version | |
|---|---|
| magic | nonce used to prevent reads without a valid url |
| length | length of file |
| data | the payload |
| checksum | checksum for the payload to check for corruption |
index = |entry|* entry = version, key, meta-size, start, length
| version | |
|---|---|
| key | UID for photo |
| meta-size | extension of key |
| start | offset into haystack |
| length | length of file |
The index file is mirrored in memory im a map that maps from the key (UID) to an array of offset and lenght (each element corresponding to a size).
haystack = |file|*
file = |header| data |footer|
header = version, magic number, length
footer = checksum
index = |entry|* entry = version, key, meta-size, start, length