5

I have about 1 billion datasets that have a DatasetKey and each has between 1 and 50 000 000 child entries (some objects), average is about 100, but there are many fat tails.

Once the data is written, there is no update to the data, only reads.

I need to read the data by DatasetKey and one of the following:
Get number of child entries
Get first 1000 child entries (max if less than 1000)
Get first 5000 child entries (max if less than 5000)
Get first 100000 child entries (max if less than 100000)
Get all child entries

Each child entry has a size of about 20 bytes to 2KB (450 bytes averaged).

My layout I want to use would be the following:

I create a file of a size of at least 5MB.
Each file contains at least one DatasetKey, but if the file is still less than 5MB I add new DatasetKeys (with child entries) till I exceed the 5 MB.
First I store a header that says at which file-offsets I will find what kind of data.
Further I plan to store serialized packages using protocol-buffers.
One package for the first 1000 entries,
one for the next 4000 entries,
one for the next 95000 entries,
one for the next remaining entries.

I store the file sizes in RAM (storing all the headers would be to much RAM needed on the machine I use). When I need to access a specific DatasetKey I look in the RAM which file I need. Then I get the file size from the RAM. When the file-size is about 5MB or less I will read the whole file to memory and process it. If it is more than 5MB I will read only the first xKB to get the header. Then I load the position I need from disk.

How does this sound? Is this totaly nonsense? Or a good way to go?

Using this design I had the following in mind:

I want to store my data in an own binary file instead a database to have it easier to backup and process the files in future.
I would have used postgresql but I figured out storing binary data would make postgresqls-toast to do more than one seek to access the data.
Storing one file for each DatasetKey needs too much time for writing all the values to disk.
The data is calculated in the RAM (as not the whole data is fitting simultaniously in the RAM, it is calculated block wise).
The Filesize of 5MB is only a rough estimation.

What do you say? Thank you for your help in advance!

edit

Some more background information:

DatasetKey is of type ulong.

A child entry (there are different types) is most of the time like the following:

public struct ChildDataSet
{
    public string Val1;
    public string Val2;
    public byte Val3;
    public long Val4;
}

I cannot tell what data exactly is accessed. Planned is that the users get access to first 1000, 5000, 100000 or all data of particular DatasetKeys. Based on their settings.

I want to keep the response time as low as possible and use as less as possible disk space.

@Regarding random access (Marc Gravells question):

I do not need access to element no. 123456 for a specific DatasetKey.

When storing more than one DatasetKey (with the child entries) in one file (the way I designed it to have not to create to much files), I need random access to to first 1000 entries of a specific DatasetKey in that file, or the first 5000 (so I would read the 1000 and the 4000 package).

I only need access to the following regarding one specific DatasetKey (uint):
1000 child entries (or all child entries if less than 1000)
5000 child entries (or all child entries if less than 5000)
100000 child entries (or all child entries if less than 100000)
all child entries

All other things I mentioned where just a design try from me :-)

EDIT, streaming for one List in a class?

public class ChildDataSet
{
    [ProtoMember(1)]
    public List<Class1> Val1;
    [ProtoMember(2)]
    public List<Class2> Val2;
    [ProtoMember(3)]
    public List<Class3> Val3;
}

Could I stream for Val1, for example get the first 5000 entries of Val1

4
  • I would save the Count WITH the Key. Using Tries, would you be able to save all the DatasetKeys in memory?
    – xanatos
    Mar 23, 2011 at 21:00
  • My DatasetKeys are from type uint (sorry, I forgott to add this information). Using Tries is not possible as I understand the theorie about Tries. Getting the number of child entries is not the most frequent read type. It is "Get first 1000 child entries". I would need about 4-6 additional GB to store the counts. I thought about using the mem to store frequent accessed DatasetKey headers of large files.
    – Chris
    Mar 23, 2011 at 21:14
  • When you say random access - do you need to pick, say, item 123124 at random? Mar 24, 2011 at 8:40
  • @Marc Gravell: I have added the answer to your question in my edit above. I don't need to pick item 123124 at random. Just some specific packages (1000 and 4000) of DatasetKey 123 if I would use my design try and store more than one DatasetKey child values in one file. I have chosen that design to get more throughput when creating the files.
    – Chris
    Mar 24, 2011 at 9:26

4 Answers 4

1

Go with a single file. At the front of the file, store the ID-to-offset mapping. Assuming your ID space is sparse, store an array of ID+offset pairs, sorted by ID. Use binary search to find the right entry. Roughly log(n/K) seeks, where "K" is the number of ID+offset pairs you can store on a single disk block (though the OS might need an additional additional seek or two to find each block).

If you want spend some memory to reduce disk seeks, store an in-memory sorted array of every 10,000th ID. When looking up an ID, find the closest ID without going over. This will give you a 10,000-ID range in the header that you can binary search over. You can very precisely scale up/down your memory usage by increasing/decreasing the number of keys in the in-memory table.

Dense ID space: But all of this is completely unnecessary if your ID space is relatively dense, which it seems it might be since you have 1 billion IDs out of a total possible ~4 billion (assuming uint is 32-bits).

The sorted array technique described above requires storing ID+offset for 1 billion IDs. Assuming offsets are 8 bytes, this requires 12 GB in the file header. If you went with a straight array of offsets it would require 32 GB in the file header, but now only a single disk seek (plus the OS's seeks) and no in-memory lookup table.

If 32 GB is too much, you can use a hybrid scheme where you use an array on the first 16 or 24 bits and use a sorted array for the last 16 or 8. If you have multiple levels of arrays, then you basically have a trie (as someone else suggested).

Note on multiple files: With multiple files you're basically trying to use the operating system's name lookup mechanism to handle one level of your ID-to-offset lookup. This is not as efficient as handling the entire lookup yourself.

There may be other reasons to store things as multiple files, though. With a single file, you need to rewrite your entire dataset if anything changes. With multiple files you only have to rewrite a single file. This is where the operating system's name lookup mechanism comes in handy.

But if you do end up using multiple files, it's probably more efficient for ID lookup to make sure they have roughly the same number of keys rather than the same file size.

2
  • Thank you for your answer. It is very helpful. Regarding multiple files: Do you know how the systems (windows) keyspace is organized and how fast it is and how much RAM it needs to store? The reason is that I only write once, so I only need the system's name lookup to get the files. But now it depends on how fast it is (when using NTFS for example).
    – Chris
    Apr 5, 2011 at 22:35
  • I don't know NTFS specifics, but each directory has some kind of name-to-disk-block mapping (possibly some kind of hash table or tree). There'll also be some kind of in-memory cache of names so that you don't have to go to disk every time. But my point is that with multiple files you're doing lookup(ID) -> filename+offset then os-lookup(filename) -> handle then read(handle,offset) -> data. If you have a single file, the handle part never changes, so you can skip the os-lookup phase every time. Apr 5, 2011 at 22:54
1

The focus seems to be on the first n items; in which case, protobuf-net is ideal. Allow me to demonstrate:

using System;
using System.IO;
using System.Linq;
using ProtoBuf;


class Program
{
    static void Main()
    {
        // invent some data
        using (var file = File.Create("data.bin"))
        {
            var rand = new Random(12346);
            for (int i = 0; i < 100000; i++)
            {
                // nothing special about these numbers other than convenience
                var next = new MyData { Foo = i, Bar = rand.NextDouble() };

                Serializer.SerializeWithLengthPrefix(file, next, PrefixStyle.Base128, Serializer.ListItemTag);
            }
        }
        // read it back
        using (var file = File.OpenRead("data.bin"))
        {
            MyData last = null;
            double sum = 0;
            foreach (var item in Serializer.DeserializeItems<MyData>(file, PrefixStyle.Base128, Serializer.ListItemTag)
                .Take(4000))
            {
                last = item;
                sum += item.Foo; // why not?
            }
            Console.WriteLine(last.Foo);
            Console.WriteLine(sum);
        }
    }
}
 [ProtoContract]
class MyData
{
     [ProtoMember(1)]
     public int Foo { get; set; }
     [ProtoMember(2)]
     public double Bar { get; set; }
}

In particular, because DeserializeItems<T> is a streaming API, it is easy to pull a capped quantity of data by using LINQ's Take (or just foreach with break).

Note, though, that the existing public dll won't love you for using struct; v2 does better there, but personally I would make that a class.

23
  • Do you know if using the foreach loop while reading lead to the situation that the hard disk head will go more than one time to the positition of this file to read the data? I tried to come over this fact by just read at least 5MB to memory and then serialize it from memory. So the hard disk head would be free to go to other positions in mean time. Or will the .net framework manage that there is only one access to that file?
    – Chris
    Mar 24, 2011 at 9:56
  • @Chris I don't understand the question; but the code as shown is a forwards-only, one pass only stream through the file. It doesn't assume the stream is seekable, as it is common to use network streams. Mar 24, 2011 at 9:58
  • @Chris if you mean re concurrent disk access, that is pretty low-level, and depends on a lot of factors Mar 24, 2011 at 10:05
  • @Marc My questions points to what will the hard disk do while we access a file with a "foreach" instead of reading the file at once. Will the hard disk in your example go to position 0 of the data.bin, then read everything till child entry position 4000 or will it read just one entry, then access the next entry on hard disk and again the next entry and so on. So when during this read some other software uses the hard disk as well, the hard disk head will be on an other position and needs to be positioned again to get the next entry?
    – Chris
    Mar 24, 2011 at 10:13
  • 1
    @Marc Yes :( A few SSDs is what would help very much. But it is not yet in out budget. I think I can manage to get one 128GB SSD. So I will put all the headers on that disk and the raw data on the slow big disks. So I exactly know where to fetch the data. We are talking of tens of terabytes of data here putting and in raid on SSD is too much for us.
    – Chris
    Mar 24, 2011 at 12:55
1

Create a solution with as much settings as possible. Then create a few test script and see which settings works best.

Create some settings for:

  • Original file size
  • Seperate file headers
  • Caching strategy (how much and what in mem)
0

Why not try Memory-mapped files or SQL with FileStream?

4
  • FileStream is not possible for me, as we have no Microsoft SQL Licence and I don't want to store the data in database. Regarding Memory-mapped-files: The data is written once and after that only read. What would the advantage by using memory mapped files instead of my solution?
    – Chris
    Mar 23, 2011 at 20:57
  • FileStream works on SQL Express and doesn't count towards the size limit. Mar 23, 2011 at 21:04
  • As for memory-mapped I'm just tossing ideas out. I don't know enough about your domain to provide anything more detailed. Something along the lines of the type of data you are storing and how it will be used would be more helpful then a description of your custom indexing. Mar 23, 2011 at 21:07
  • I have added some additional information. I hope that helps. As I understood using SQL Express and FileStream, I would need the primary Key stored in the database. I think this would exceed the 4GB limit. I am open to hear any idea from you. I will check every idea in relation to out project and give you feedback.
    – Chris
    Mar 23, 2011 at 21:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.