Problems with a chunk-based file

[Brainer]

Hello everyone. :)

After a long time, I decided to finally start coding again. I'm planning to start working on my VFS again; to all who were waiting - the project is not dead!

Anyway, I wanted to work a little on a side project directly linked with my VFS, and I encountered a problem. Take a look at the following structure:
http://i43.tinypic.com/2ahyx3k.png

For offsets, I reserved some space just after the header. It's not really an offsets array, it'll consists of fixed-size records:

type
{ .: TEntryRecord :. }
TEntryRecord = packed record
EntryHash: Cardinal;
OffsetInFile: Int64;
end;

But as you can see, the reserved space is limited. What if the array grows larger? If I assume correctly, the array will override all data kept after it.

How to avoid that? ???

[Andreaz]

Just put the header and offset array in the end of the file instead. Then you just have to rewrite the header when adding data to the file.

This is how the package structure looks like in Phoenix:



[File data #1]
..
[File data #n]
..
[Package header]
Ident
Version
Name
Description
File count
[File header #1]
Name
Size
Resource
Modified
Checksum
Offset
[File header #n]
Name
Size
Resource
Modified
Checksum
Offset
[Package footer]
Ident
HeaderPosition

[chronozphere]

Hey Patrick. Haven't seen you for a while. ;) When will you be back on MSN?

I had to solve similair problems with my VFS. I use the following structure:

VFS-HeaderData-Blocks + Block-HeadersFile-Headers

When the ammount of data-blocks grows to large, it will override the file-Headers. To prevent this, i've written a routine to Allocate "n" blocks for a file.

> It checks all the blocks to see if any blocks allready belong to the file (this information is stored in the FileID of the blockheader). If more blocks are needed, it'll proceed with the next step.
> It check whether there are any "free" blocks that we could use (Blocks who's blockheaders where FileID = 0). If still more blocks are needed, it'll proceed.
> It reads all fileheader-data to a backup buffer (TMemoryStream). Then it starts adding blocks by overwriting the previous fileheader-data (which is backupped). When enough blocks are added, the fileheader-data will be rewritten after the last block.

It's just a matter of making a backup, overwrite and replacing the backup. It's important that you update your whole system, so it knows about the added blocks and can still find the File-headers allthough they moved.

So in your case... when the offsets array grows too large, you have to backup and replace ALL the block data to be able to allocate some new data. In most cases, i think the RAW-data part of your file will be MUCH bigger than the offsets array. My advice to you is, to swap these two, so the RAW data will go first. This is better (performance-wise), because reading and writing a small peice of block of data (Offsets array) is allways better than having to read/write RAW data which can be just a couple of MB's or even more.

I have one question though. What exactly does "OffsetInFile" contain?

1. The absolute offset from the beginning?
2. Is it relative to the end of the header?
3. Is it relative the end of the offsets array?

This choice is quite important. If the first case is true, you need to update ALL Offsets in each TEntryRecord, because your Offsets array grew bigger. The last choice would be better, because the offsets would still be correct. In that case you have to store the "OffsetsSize" in your Header. To find a piece of data you'd use:

VFSHeader.OffsetSize + EntryRecord.OffsetInFile = location of chunk

Hope this helps. If you would like to discuss any of this. please get on MSN :) (in the evening, i'll not be online during the day)

[Brainer]

Hmm, I don't really get it. See, even if I store raw data before the offsets, there's still a chance of offsets data to be overwritten by raw data. The only way of reproducing it I can think of is to keep it in memory, but I want to avoid that.

Am I wrong?

[chronozphere]

The actual sollution is to make a backup of the part of the file that is to be overwritten when some other part of the file grows bigger. After that, you just write the backup back to the file but to a new location (just after the newly allocated space). Example:

HH-BBBBBB-GGG

If we want more B, we make a backup of all the G data. Now we overwrite some of the G-data with B-data.

HH-BBBBBBBB-G

Now we write our backupped G data after the new B data.

HH-BBBBBBBB-GGG

My advice is to make sure that the G-part of you file is generally smaller than the B part. Every time you need more B-data you have to make a backup of G and restore it later on. If G is very large, it takes more time to read/write.

Hope this makes sense. ;)

[Brainer]

Yep, it does now. :) But I wonder if it's the same solution used in SQLite. Rewriting the part you want to overwrite is time-consuming. And what if you have 10000 blocks to backup? It'll surely take some time.

I'm thinking of some way to ensure that there's always enough space to add new chunks without worrying that something will be overwritten. Take a look at that:
http://i41.tinypic.com/29mr3vk.png

Maybe something like that could work? But how to prepare such a "divider"? Maybe every time you add new chunks, as raw data will grow "downwards". ???

[chronozphere]

You are probably talking about a system with free-space in the middle and two parts of the file growing towards eachother when they get bigger. I don't think it solves the problem. It only makes things more complex. In the end, the offsetarray will clash with the Raw data and you'd have the same problem. :)

What you could do is:
> Use my trick to make a backup of the part that is to be overwritten and put it back afterwards (see previous post).
> You can make two seperate files, which would be more easy. One storing the VFS-header and the file information, offsets etc... and the other storing raw data. This allows both parts to grow without interfering.

[Brainer]

Yep, I've been considering using two files instead of one, just as it's done in MySQL (i.e. using MyISAM tables -> http://en.wikipedia.org/wiki/MyISAM). I could use SQLite for a quick entry management, but it simplifies things too much and I want to have some challenge. :D

The idea of making backups sounds quite good. I could cache entries to memory and rewrite them back. But I made tests and it takes some time. Just like I mentioned in our MSN talk, I made a test that reads/writes a 1 million of entries.


type
{ .: TRec :. }
TRec = packed record
NameHash: Cardinal;
OffsetInFile: Int64; // an absolute offset from the beginning of file
end;

OperationReadingWritingTime4.02 seconds4.92 seconds

So if you had a lot of entries, you'd have to wait 5 seconds before you can add anything again...

[noeska]

Could you not store the record structure inside a stream/file that is also stored in the blocks. E.g. the record structure is just another file inside the archive. No interference that way.

[Brainer]

Hmm, that's a good idea. :)

I wonder, actually how do databases work? You can freely modify records (i.e. change their sizes), add new and remove existing ones and it's all done very fast... I'd like to know how to make such a system. Are B+trees the way to go? How to use them? It'd be easy if the records were fixed-size. But they just can't - I cannot limit anyone only to 255 characters long strings...

Or maybe I'm complicating things while the answer is really nearby? What do you think?

[ize]

Just a theory but how about this?

In your Header, put a variable to contain the file offset of the "index". As the header is a fixed size, you can update this for every addition/deletion. For each chunk, also store the the size of that chunk, then at the end of the file after the raw data you store the index which contains the number of chunks, the file offset for each chunk and maybe also a flag to show if it's active or not.
Your file structure would look like:
[Header] [Chunk0] .. [Chunkn] [Index]

For adding:

Go to the index file offset.
Store chunk size and file offset in index
Overwrite index with new data.
Store file offset in Header.
Write index to disk.
Go to the beginning of the file and re-write the Header.


For deleting:

Change the active "flag" in index.
Go to index file offset
Re-write the index


I know this would be a lot of wasted space, but you could write a procedure to delete all "inactive" chunks from the file (kinda like compacting) which only has to be done every so often. It also gives you the option of restoring deleted data just by changing the flag.

I don't know if this is how databases work, but if you're looking for speed, then this is how i'd do it.

edit:
Just re-read post (properly :-[) The above should still work if the data shrinks, but not if it grows. How often will the data get larger? I thought databases were fast because they used fixed-size records.

[noeska]

PS my virtual file system already has the file index as 'just another' file inside the archive. Also it is groweable. Shrinking is a bit harder when it involves an chunk in the mids of an archive, i just mark these chunks as deleted and offer them for reuse asap. E.g. for al of this i use a TVirtualFileStream construct that calls the needed TVirtualFileSystem functions. E.g. for the programmer does not need to know any about the TVirtualFileSystem (in a future release not even about opening and closing it.)

http://www.noeska.net/projects/nvfs/

[Brainer]

I haven't really read it all properly, ize, but thanks for your ideas and I'll analyze them for sure. ;)

I don't think databases use fixed-sized records, because how would you store strings in such records? Of course, if you want to use short strings, it's not a problem at all. But I don't think any user would be satisfied with a database that allows only 255-chars long strings. :(

Thanks noeska for the link, I'll take a look at the project of yours.

Another thing I was thinking of is to use the following structure:
http://i39.tinypic.com/ji12k3.png
Any ideas how to implement something like that? I can't really understand how it's possible to maintain such a structure - and I DO know it's possible as it's what SQLite uses and it does its job really fast...

[noeska]

are you user sqlite uses that structure? An sqlite file seems to grow as more data is put inside. This method can only be used if you fix the total archive file size to a specific size.

On the variable record size.

- one record per chunk
A chunk can contain (for example) 600 bytes. When you write a record in a chunk and that records totalsize is 400 bytes you have 200 bytes left that you could waste. E.g. the next record will be put in a new chunk. If you have a 800 bytes record that would not fit in a 600 byte stucture so that would be split over 2 chunks wasting 400 bytes in de second chunk.

| c1    | c2    | c3
| r1 | ws| r2    | r2 | ws
 
- multiple records per chunk
A chunk can contain (for example) 600 bytes. When you write a 400 byte record in a chunck you need to specify its lengt infront of it. Now the next record can be written in the first chunk after the first 400 bytes + size (e.g. 2 bytes). and continues in subsequent chunks

| c1      | c2    |c3
| r1  | r2| r2    | r2 | fs

Also a list of records e.g. a table can be considere one filestream with
(size)(record)(size)(record)
When a record is added a new chunk is added when needed. When deleting a record an investigation should be made what chunks are involved.

[Brainer]

Yep, as you can read in the source:


** |----------------|
** | file header | 100 bytes. Page 1 only.
** |----------------|
** | page header | 8 bytes for leaves. 12 bytes for interior nodes
** |----------------|
** | cell pointer | | 2 bytes per cell. Sorted order.
** | array | | Grows downward
** | | v
** |----------------|
** | unallocated |
** | space |
** |----------------| ^ Grows upwards
** | cell content | | Arbitrary order interspersed with freeblocks.
** | area | | and free space fragments.
** |----------------|


Anyway, why do you think it's only possible when the file is fixed-size? How would that make any difference?

[noeska]

in my opinion free space in the middle can only exist in a fixed filesize. otherwise it would not be free space?

btw i extended my previous post with info on variable record sizes...

[Brainer]

Yep, probably the thing about having free space in the middle isn't right, but there's still a problem. How to prevent two different kinds of data from overwritting each other as they grow? :o

Yep, the idea you proposed is good. AFAIK it's not what they used in hard disks, as one sector = one file.

[noeska]

Have a read on my second example:



- multiple records per chunk
A chunk can contain (for example) 600 bytes. When you write a 400 byte record in a chunck you need to specify its lengt infront of it. Now the next record can be written in the first chunk after the first 400 bytes + size (e.g. 2 bytes). and continues in subsequent chunks

| c1 | c2 |c3
| r1 | r2| r2 | r2 | fs

Also a list of records e.g. a table can be considere one filestream with
(size)(record)(size)(record)
When a record is added a new chunk is added when needed. When deleting a record an investigation should be made what chunks are involved.


This has multiple records per chunk.

[chronozphere]

Could you not store the record structure inside a stream/file that is also stored in the blocks. E.g. the record structure is just another file inside the archive. No interference that way.

That is an interesting idea, but i would implement it in a slightly other way. If you use the existing file-system to store filesystem-data you will not be able to retrieve this data because it's stored in the system itsself, and you need this meta-data to tell in which file the meta-data is stored.. It's an endless circle isn't it. :D

I think it's better to think of another approach. Think of it as some kind of encapsulation. The topmost layer of the system describes a file that contains a header and a certain ammount of data-blocks. The header tells us how many blocks are out there, what kind of blocks they are and which block-type has which size.
You could introduce block-types like: "FileData" or "FileHeader".

Each block looks like this:

[BlockIdentifier - 4 bytes]
[BlockType - 4 bytes]
[BlockData - Size depends on BlockType]

Now, the next layer contains the actual filesystem (The file-data and fileheaders). This data is stored inside blocks as described above. So for example you could have these two blocks:




//A block containing a fileheader

BlockIdentifier = 2356
BlockType = btFileHeader
BlockData: [
FileID = 12
FileName = 'MyFile'
FileSize = 1254
.. The rest of your fileheader ... ]

//A block containing file-data

BlockIdentifier = 2357
BlockType = btFileData
BlockData: [
//DataBlock Header
FileBlockID = 43
BelongsToFile = 12
UsedSize = 1254
//Data here
//....
//.... ]


You are simply encapsulating your filesystem into another blocksystem. Doing it this way allows you to keep adding data to the end of your file without having to move data around to allow parts of the file to grow. This system allows for fragmentation and asks for a defragmentation-method(). You also need to scan all blocks at startup to be able to enumerate all files that exist inside the VFS.
If the added complexity and work is no problem for, you could try this method. :)

And if you are concerned with speed that much, i would suggest to stick with fixed size records. That comes with a price as your system will consume more HDD space, but that's life. You can't have it all, and you just have to walk the right road instead of trying to walk all of them. ;)

[ize]

I don't think databases use fixed-sized records, because how would you store strings in such records? Of course, if you want to use short strings, it's not a problem at all. But I don't think any user would be satisfied with a database that allows only 255-chars long strings. :(


I know Microsoft Access database records are fixed-size. When designing a table, you define the sizes of the fields. For strings you can have a Text field which is up to 255 chars, or a Memo which is up to 65,535 chars. although i'm not sure how it stores the data ;)

[noeska]

Could you not store the record structure inside a stream/file that is also stored in the blocks. E.g. the record structure is just another file inside the archive. No interference that way.

That is an interesting idea, but i would implement it in a slightly other way. If you use the existing file-system to store filesystem-data you will not be able to retrieve this data because it's stored in the system itsself, and you need this meta-data to tell in which file the meta-data is stored.. It's an endless circle isn't it.  :D

....

You are simply encapsulating your filesystem into another blocksystem. Doing it this way allows you to keep adding data to the end of your file without having to move data around to allow parts of the file to grow. This system allows for fragmentation and asks for a defragmentation-method(). You also need to scan all blocks at startup to be able to enumerate all files that exist inside the VFS.
If the added complexity and work is no problem for, you could try this method. :)


The circle got a a starting point on by having the 'file' index always start in block 2. Leaving block 1 for the header. Now the 'file' index can be used to retrieve meta data and data tables and data indexes also stored as other files inside the chunked file. The 'file' index can be considered an data table also.

Have a look at my vfs: http://www.noeska.net/projects/nvfs/
and look at
procedure TVirtualFileSystem.GetFileList(aname: string; List: TStrings);
that uses FDir: TVirtualFileStream;
what is a filestream inside the chunked file that starts in block2.
it can be loaded in a stream by name '/' because
function TVirtualFileSystem.FindFile(aname: string; var afilerecord: TFileInfo): int64;
returns the first record in block 1:
self.ReadBlock(1,FileRecordEntry,0,SizeOf(TFileInf o));
and yes this record is fixed size :-) variable sized records are somewhere low on my todo list.
as filename: string[255];
and yes nvfs potentialy needs to be defragmented after deleting files and making files larger/smaller.
But i have no need to enumerate al files at startup. Al i need to do when reading a file is look up its name in '/' that way i retrieve the starting chunk and each chunk knows the follow up chunk for a file.

[Brainer]

Thanks for all your ideas. :) But they don't seem to resolve my problem.

The block structure I wanna use is:

type
{ .: TBlock :. }
TBlock = packed record
Flag: Byte;
NextBlock: Cardinal; // used when reading files contents
end;


The problem is not how the structure would look like, but how to implement the file format. What I mean is that I've not a slightest clue how to manage a file structure and file data inside one file. Also, as I want my format to support directory trees (what's important - a directory can contain files and subdirectories).

That's what the problem really is, nevertheless the idea of blocks proposed by chronozphere suits me. :)

And yes, sorry for me being not clear from the very beginning.

[noeska]

It is not easy. ;) Dont try to do all at once. But try to make chunks/blocks work with a directory first. Then consider your directory to be a file that starts in block 1. And your header to be block 0. Then think on subdirectories. Oh and try to avoid loading to much in memory the vfs is leading not internal memory.

Also did not you have something working before? Try to adapt that? You said it had problems when lots of files were added?

Also i should make i better example for nvfs to show it of better. But that wont be until next week.

[ize]

noeska's right. Get your header/chunk code sorted and after that directories and sub-directories are easy. Just specify the virtual path and filename when adding the file.

Eg: File c:\example.txt can be stored as df0:\dir1\subdir1\example.txt in the file system(with df0: being the virtual root drive)

All you need to do is store that filename and the directories can be worked out from that, not affecting how you save the chunk data. Of course, this doesn't take into account empty directories because i can't see the point of storing them :)

Here's some code. It's from a file packer i started to write a little while back but didn't finish(the packing worked, i couldn't get my head round compressing the data).

edit: found this Compression Library (http://www.yunqa.de/delphi/doku.php/products/ucl/index) which was exactly what i was looking for. I'm sure you guys know all about it :) I think i'll have another go at finishing my project now.

const
rootdir = 'df0:';

{add a trailing character C to a string S}
function TrailC(S: string;C: Char): string;
begin
if (Length(s)>0) and (s[Length(s)]<>c) then S:=S+C;
Result:=S;
end;

{split a filename into separate parts. Return the path or the file depending on dir(true for directory). default returns path}
function split(f0: string; dir: boolean): string;
var
k: integer;
begin
// no path specified
if (pos('\', f0)=0) then begin
if dir then begin
result:=trailc(rootdir, '\');
end
else if not dir then result:=f0;
exit;
end;

// find last path separator
k:=length(f0);
while (f0[k]<>'\') and (k>0) do dec(k);
if dir then begin
result:=copy(f0, 1, k);
if length(result)=1 then result:=trailc(rootdir, '\'); // convert '\' to 'df0:\'
if (result[1]='\') then insert(rootdir, result, 1) // convert '\directory1' to 'df0:\directory1'
else if (pos(rootdir,result)=0) then insert(trailc(rootdir, '\'), result, 1); // force rootdir into filename
end
else result:=copy(f0, k+1, length(f0));
end;

{string satisfy function. allows widcard matches of a string S using Mask like *.txt or file??.txt. Returns True on success}
function StrSatisfy(S,Mask: PChar) : Boolean;
label
next_char;
begin
next_char:
Result:=True;
if (S^=#0) and (Mask^=#0) then exit;
if (Mask^='*') and (Mask[1]=#0) then exit;
if S^=#0 then begin
while Mask^ = '*' do Inc(Mask);
Result:=Mask^=#0;
exit;
end;

Result:=False;
if Mask^=#0 then exit;
if Mask^='?' then begin
Inc(S);Inc(Mask);goto next_char;
end;
if Mask^='*' then begin
Inc( Mask );
while S^<>#0 do begin
Result:=StrSatisfy(S,Mask);
if Result then exit;
Inc(S);
end;
exit; // (Result = False)
end;
Result:=S^=Mask^;
Inc(S);Inc(Mask);
if Result then goto next_char;
end;

{enumerate all files using mask. findexes was the array for my file index}
function enumfiles(mask: string): tstrings;
var
f, p: string;
i: tindex;
begin
result:=nil;
if (trim(mask)='') or (length(findexes)=0) then exit;
result:=tstringlist.create;
p:=split(mask);
f:=split(mask, false);
for i in findexes do
if (split(i.filename)=p) and (strsatisfy(pchar(split(i.filename,false)),pchar(f ))) then result.add(i.filename);
end;

{enumerate all folders using Mask}
function enumfolders(mask: string): tstrings;
var
k: integer;
p: string;
i: tindex;
begin
result:=nil;
if (trim(mask)='') or (length(findexes)=0) then exit;
result:=tstringlist.create;
for i in findexes do begin
p:=split(i.filename, true);
p:=copy(p,1,length(p)-1); // remove the last '\' from filepath
k:=result.indexof(p); // only add new directories
if (strsatisfy(pchar(p), pchar(mask))) and (k=-1) then result.add(p);
end;
end;


So given 5 files(with df0:\ being the root directory):
df0:\a.txt
df0:\directory1\b.txt
df0:\directory1\c.txt
df0:\directory1\directory1\d.txt <- same named sub-dirs are allowed
df0:\directory2\e.txt

enumfiles('*') = df0:\a.txt (if you wanted all files, just read the index - it would be easier and quicker)
enumfiles('\directory1\*') = df0:\directory1\b.txt & df0:\directory1\c.txt
enumfolders('directory1\*') = directory1

[Brainer]

Ok guys, thanks for your replies. I'll read it all once again and try to make something out of your ideas. :)