Ayende @ Rahien

Hi!
My name is Oren Eini
Founder of Hibernating Rhinos LTD and RavenDB.
You can reach me by phone or email:

ayende@ayende.com

+972 52-548-6969

, @ Q c

Posts: 18 | Comments: 65

filter by tags archive

Voron’s implementation: Managed memory mapped database–getting to C memory model

time to read 11 min | 2160 words

In my previous post I started to talk about the architecture of Naver. But this is actually still too early to tell, since before anything else, I want to create the low level interface for working with pages. And even before that, I had to decide how to actually represent a page in C#. In LMDB, this is easy because you can just access the memory using a pointer, and work with memory in this fashion is really natural in C. But in C#, that is much harder. It took me some trial and error, but I realize that I was trying to write C code in C#, and that isn’t going to work. Instead, I have to write native C#, which is similar, but different. In C, I can just pass around a pointer, and start doing evil things to it at will. In C#, there are a lot of road blocks along the way that prevent you from doing that.

So I ended up with this:

   1: [StructLayout(LayoutKind.Explicit, Pack = 1)]
   2: public struct PageHeader
   3: {
   4:     [FieldOffset(0)]
   5:     public int PageNumber;
   6:     [FieldOffset(4)]
   7:     public PageFlags Flags;
   8:  
   9:     [FieldOffset(5)]
  10:     public ushort Lower;
  11:     [FieldOffset(7)]
  12:     public ushort Upper;
  13:  
  14:     [FieldOffset(5)]
  15:     public int NumberOfPages;
  16: }

This is the memory layout that I want. But, there is not way in C# to say, allocate this struct at this location. Luckily, I found a workaround.

   1: public unsafe class Page
   2: {
   3:     private readonly byte* _base;
   4:     private readonly PageHeader* _header;
   5:  
   6:     public Page(byte* b)
   7:     {
   8:         _base = b;
   9:         _header = (PageHeader*)b;
  10:     }
  11:  
  12:     public int PageNumber { get { return _header->PageNumber; } set { _header->PageNumber = value; } }

What I can do, I can have a Page class that manage this for me. This means that I just give the class a pointer, and it can treat this either as a PageHeader* or as a byte array. This means that I also get to do cool tricks like having an array backed by memory directly in the code:

   1: public ushort* KeysOffsets
   2: {
   3:     get { return (ushort*)(_base + Constants.PageHeaderSize); }
   4: }

The Page class have a lot of methods relating to managing the page itself, and it should abstract away all the pesky details of actually working with memory directly.

So, this isn’t a really informative post, I fear. But it did take me a few hours to come up with the approach that I wanted. I kept trying to find ways to embed addresses inside the PageHeader, until I realized that I can just hold that externally. Note that all the important state about the Page is actually stored in memory outside the Page class, so that is shared globally, but you can have two Page instances that point to the same place. And that is where I decided to put local state. Things like where we are currently positioned in the page, for example.


Comments

tobi

"ushort Lower" at offset 5 will cause unaligned access. Not sure if that is a performance problem. At least the CLR and C compilers never do this on their own.

Jon
Jon

Guess I better start reading up on unsafe contexts and pointers to keep up with this blog post series! I'm looking forward to more post like this!

tobi

Doing more research on this (http://lemire.me/blog/archives/2012/05/31/data-alignment-for-speed-myth-or-reality/) it seems there is no performance difference at all. Why are compilers avoiding this like the plague then?

Ayende Rahien

Tobi, Look at the comments, this is fairly recent development.

Drew Noakes

Depending upon how you use the Page class, you can avoid the overhead of having a reference type altogether by just casting the byte* to a PageHeader* and then moving your methods/properties from the class to your struct directly. In that way, they will be manipulating the underlying byte[] directly, and there's nothing for the GC to clean up at the end of it.

For example:

var page = (PageHeader*)bytePointer; page->PageNumber = 2;

No copying of memory. No GC.

Drew Noakes

BTW thanks for the great talk in London last night. I really enjoyed your review of the different databases you researched, and the detail on the improvements you've made with Voron.

Ayende Rahien

Drew, There is a non persistent state that I need to keep. For example, the last search pos in the page. I keep that in the Page class for that purpose.

Comment preview

Comments have been closed on this topic.

FUTURE POSTS

  1. RavenDB 3.0 New Stable Release - 11 hours from now
  2. Production postmortem: The case of the lying configuration file - about one day from now
  3. Production postmortem: The industry at large - 2 days from now
  4. The insidious cost of allocations - 3 days from now
  5. Buffer allocation strategies: A possible solution - 6 days from now

And 4 more posts are pending...

There are posts all the way to Sep 11, 2015

RECENT SERIES

  1. Find the bug (5):
    20 Apr 2011 - Why do I get a Null Reference Exception?
  2. Production postmortem (10):
    31 Aug 2015 - The case of the memory eater and high load
  3. What is new in RavenDB 3.5 (7):
    12 Aug 2015 - Monitoring support
  4. Career planning (6):
    24 Jul 2015 - The immortal choices aren't
View all series

Syndication

Main feed Feed Stats
Comments feed   Comments Feed Stats