Ayende @ Rahien

Refunds available at head office

Voron & the FreeDB dataset

I got tired of doing arbitrary performance testing, so I decided to take the FreeDB dataset and start working with that. FreeDB is a data set used to look up CD information based on the a nearly unique disk id. This is a good dataset, because it contains a lot of data (over three million albums, and over 40 million songs), and it is production data. That means that it is dirty. This makes it perfect to run all sort of interesting scenarios.

The purpose of this post (and maybe the new few) is to show off a few things. First, we want to see how Voron behaves with realistic data set. Second, we want to show off the way Voron works, its API, etc.

To start with, I run my FreeDB parser, pointing it at /dev/null. The idea is to measure what is the cost of just going through the data is. We are using freedb-complete-20130901.tar.bz2 from Sep 2013.

After 1 minute, we went through 342,224 albums, and after 6 minutes we were at 2,066,871 albums. Reading the whole 3,328,488 albums took about a bit over ten minutes. So just the cost of parsing and reading the FreeDB dataset  is pretty expensive.

The end result is a list of objects that looks like this:

image

Now, let us see how we want to actually use this. We want to be able to:

  • Lookup an album by the disk ids
  • Lookup all the albums by an artist*.
  • Lookup albums by album title*.

This gets interesting, because we need to deal with questions such as: “Given Pearl Jam, if I search for Pearl, do I get them? Do I get it for jam?” For now, we are going to go with case insensitive, but we won’t be doing full text search, we will allow, however, prefix searches.

We are using the following abstraction for the destination:

   1: public abstract class Destination
   2: {
   3:     public abstract void Accept(Disk d);
   4:     public abstract void Done();
   5: }

Basically, we read data as fast as we can, and we shove it to the destination, until we are done. Here is the Voron implementation:

   1: public class VoronDestination : Destination
   2: {
   3:     private readonly StorageEnvironment _storageEnvironment;
   4:     private WriteBatch _currentBatch;
   5:     private readonly JsonSerializer _serializer = new JsonSerializer();
   6:     private int counter = 1;
   7:  
   8:     public VoronDestination()
   9:     {
  10:         _storageEnvironment = new StorageEnvironment(StorageEnvironmentOptions.ForPath("FreeDB"));
  11:         using (var tx = _storageEnvironment.NewTransaction(TransactionFlags.ReadWrite))
  12:         {
  13:             _storageEnvironment.CreateTree(tx, "albums");
  14:             _storageEnvironment.CreateTree(tx, "ix_artists");
  15:             _storageEnvironment.CreateTree(tx, "ix_titles");
  16:             tx.Commit();
  17:         }
  18:         _currentBatch = new WriteBatch();
  19:     }
  20:  
  21:     public override void Accept(Disk d)
  22:     {
  23:         var ms = new MemoryStream();
  24:         _serializer.Serialize(new JsonTextWriter(new StreamWriter(ms)), d);
  25:         ms.Position = 0;
  26:         var key = new Slice(EndianBitConverter.Big.GetBytes(counter++));
  27:         _currentBatch.Add(key, ms, "albums");
  28:  
  29:         if(d.Artist != null)
  30:             _currentBatch.MultiAdd(d.Artist.ToLower(), key, "ix_artists");
  31:         if (d.Title != null)
  32:             _currentBatch.MultiAdd(d.Title.ToLower(), key, "ix_titles");
  33:  
  34:         if (counter%1000 == 0)
  35:         {
  36:             _storageEnvironment.Writer.Write(_currentBatch);
  37:             _currentBatch = new WriteBatch();
  38:         }
  39:  
  40:     }
  41:  
  42:     public override void Done()
  43:     {
  44:         _storageEnvironment.Writer.Write(_currentBatch);
  45:     }
  46: }

Let us go over this in detail, shall we?

In line 10 we create a new storage environment. In this case, we want to just import the data, so we can create the storage inline. On lines 13 – 15, we create the relevant trees.

You can think about Voron trees in a very similar manner to the way you think about tables. They are a way to separate data into different parts of the storage. Note that this still all reside in a single file, so there isn’t a physical separation.

Note that we created an albums tree, which will contain the actual data. And ix_artists, ix_titles trees. Those are indexes into the albums tree. You can see them being used just a little lower.

In the Accept method, you can see that we use a WriteBatch, a native Voron notion that allows us to batch multiple operations into a single transaction. In this case, for every album, we are making 3 writes.

First, we write all of the data, as a JSON string, into a stream and put it in the albums tree. Then we create a simple incrementing integer to be the actual album key. Finally, we add the artist and title entries (lower case, so we don’t have to worry about case sensitivity in searches) into the relevant indexes.

At 60 seconds, we written 267,998 values to Voron. In fact, I explicitly designed it so we can see the relevant metrics. At 495 seconds we have reads 1,995,385 entries from the FreeDB file, we parsed  1,995,346 of them and written to Voron  1,610,998. As you can imagined, each step is running in a dedicated thread, so we can see how they behave on an individual basis. The good thing about this is that I can physically see the various costs, it is actually pretty cool

Here is the Voron directory at 60 seconds:

image

You can see that we have two journal files active (haven’t been applied to the data file yet) and the db.voron file is at 512 MB. The compression buffer is at 32 MB (this is usually twice as big as the biggest transaction, uncompressed).

The scratch buffer is used to hold in flight transaction information (until we send it to the data file), and you can see it is sitting on 256MB in size.

At 15 minutes, we have the following numbers: 3,035,452 entries read from the file,  3,035,426 parsed and 2,331,998 written to Voron. Note that we are reading the file & writing to Voron on the same disk, so that might impact the read performance.

At that time, we can see the following on the disk:

image

Note that we increase the size of most of our files by factor of 2, so some of the space in the db.voron file is probably not used. Note that we needed more scratch space to handle the in flight information.

The entire process took 22 minutes, start to finish. Although I have to note that this hasn’t been optimized at all, and I know we are doing a lot of stupid stuff through it.

You might have noticed something else, we actually “crashed” closed the Voron db, this was done to see what would happen when we open a relatively large db after an unordered shutdown.

We’ll actually get to play with the data in my next post. So far this has been pretty much just to see how things are behaving. And… I just realized something, I forgot to actually add an index on disk id Sad smile.

Which means that I have to import the data again. But before that, I also wrote the following:

   1: public class JsonFileDestination : Destination
   2: {
   3:     private readonly GZipStream _stream;
   4:     private readonly StreamWriter _writer;
   5:     private readonly JsonSerializer _serializer = new JsonSerializer();
   6:  
   7:     public JsonFileDestination()
   8:     {
   9:         _stream = new GZipStream(new FileStream("freedb.json.gzip", FileMode.CreateNew, FileAccess.ReadWrite), CompressionLevel.Optimal);
  10:         _writer = new StreamWriter(_stream);
  11:     }
  12:  
  13:     public override void Accept(Disk d)
  14:     {
  15:         _serializer.Serialize(new JsonTextWriter(_writer), d);
  16:         _writer.WriteLine();
  17:     }
  18:  
  19:     public override void Done()
  20:     {
  21:         _writer.Flush();
  22:         _stream.Dispose();
  23:     }
  24: }

This completed in ten minutes, for 3,328,488 entries. Or a rate of about 5,538 per / second. The result is a 845MB gzip file.

I had twofold reasons to want to do this. First, this gave me something to compare ourselves to, and more to the point, I can re-use this gzip file for my next tests, without having to go through the expensive parsing of the freedb file.

I did just that and ended up with the following:

   1: public class VoronEntriesDestination : EntryDestination
   2: {
   3:     private readonly StorageEnvironment _storageEnvironment;
   4:     private WriteBatch _currentBatch;
   5:     private int counter = 1;
   6:  
   7:     public VoronEntriesDestination()
   8:     {
   9:         _storageEnvironment = new StorageEnvironment(StorageEnvironmentOptions.ForPath("FreeDB"));
  10:         using (var tx = _storageEnvironment.NewTransaction(TransactionFlags.ReadWrite))
  11:         {
  12:             _storageEnvironment.CreateTree(tx, "albums");
  13:             _storageEnvironment.CreateTree(tx, "ix_diskids");
  14:             _storageEnvironment.CreateTree(tx, "ix_artists");
  15:             _storageEnvironment.CreateTree(tx, "ix_titles");
  16:             tx.Commit();
  17:         }
  18:         _currentBatch = new WriteBatch();
  19:     }
  20:  
  21:     public override int Accept(string d)
  22:     {
  23:         var disk = JObject.Parse(d);
  24:  
  25:         var ms = new MemoryStream();
  26:         var writer = new StreamWriter(ms);
  27:         writer.Write(d); writer.Flush();
  28:         ms.Position = 0;
  29:         var key = new Slice(EndianBitConverter.Big.GetBytes(counter++));
  30:         _currentBatch.Add(key, ms, "albums");
  31:         int count = 1;
  32:  
  33:         foreach (var diskId in disk.Value<JArray>("DiskIds"))
  34:         {
  35:             count++;
  36:             _currentBatch.MultiAdd(diskId.Value<string>(), key, "ix_diskids");
  37:         }
  38:  
  39:         var artist = disk.Value<string>("Artist");
  40:         if (artist != null)
  41:         {
  42:             count++; 
  43:             _currentBatch.MultiAdd(artist.ToLower(), key, "ix_artists");
  44:         }
  45:         var title = disk.Value<string>("Title");
  46:         if (title != null)
  47:         {
  48:             count++; 
  49:             _currentBatch.MultiAdd(title.ToLower(), key, "ix_titles");
  50:         }
  51:  
  52:         if (counter % 100 == 0)
  53:         {
  54:             _storageEnvironment.Writer.Write(_currentBatch);
  55:             _currentBatch = new WriteBatch();
  56:         }
  57:         return count;
  58:     }
  59:  
  60:     public override void Done()
  61:     {
  62:         _storageEnvironment.Writer.Write(_currentBatch);
  63:         _storageEnvironment.Dispose();
  64:     }
  65: }

Now we are actually properly disposing of things, and I also decreased the size of the batch, to see how it would respond. Note that it is now being fed directly from the gzip file, at a greatly reduced cost.

I also added tracking note only for how many albums we write, but also how many entries. By entries I mean, how many Voron entries (which include the values we add to the index).

I did find a bug where we would just double the file size without due consideration to its size, so now we are doing smaller file size increases.

Word of warning: I didn’t realized until after I was done with all the benchmarks, but I actually run all of those in DEBUG configuration, which basically means that it is utterly useless as a performance metric. That is especially true because we have a lot of verifier code that runs in DEBUG mode. So please don’t take those numbers as actual performance metrics, they aren’t valid.

Time # of albums # of entries
4 minutes 773,398 3,091,146
6 minutes 1,126,998 4,504,550
8 minutes 1,532,858 6,126,413
18 minutes 2,781,698 11,122,799
24 minutes 3,328,488 13,301,496

The status of the file system midway during the run. You can see that now we increase the file is smaller increments. And that we are using more scratch space, probably because we are under very heavy write load.

image

After the run:

image

Scratch & compression are only used when the database is running, and deleted on close. The database is 7GB in side, which is quite respectable. Now, to working with it, but I’ll save that for my next post, this one is long enough already.

Comments

peter
01/07/2014 03:25 PM by
peter

why would the .journal file remain after completion?

Ayende Rahien
01/07/2014 03:34 PM by
Ayende Rahien

Peter, For the next write transaction to come along

Comments have been closed on this topic.