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: 6,128 | Comments: 45,551

filter by tags archive

The low level interview question

time to read 2 min | 234 words

The following is likely to end up in the list of questions we’ll ask candidates to answer when they apply to Hibernating Rhinos.

We need to store information about keys and their location on disk. We need to implement a trie. We want the trie to store int64 size values and unbounded UTF8 string keys.

Given that, we have the following interface:

We need to implement that with the following properties:

  • The trie will be represented by single 32 kilobytes byte array.
    • You cannot store any additional information about the trie outside of the array.
  • The costs of searching in the trie in proportional to the size of the key.
  • There are no duplicates.
  • This is a single thread implementation.
  • If the array is full, it is fine to return false from the TryWrite()
  • Unsafe code is fine (but not required).
  • You cannot use any in memory structure other than the byte array. But it is fine to allocate memory during the processing of the operations (for example, to turn the string key into a byte array).

We will be looking at the following aspect in the implementation:

  • Correctness
  • Performance
  • Space used

The idea is that we can pack as much as possible into as small a space as possible, but at the same time, we can get great performance.

Dependencies management in a crisis

time to read 3 min | 480 words

Typically when people talk about dependencies they talk about how easy it is to version them, deploy them, change & replace them, etc. There seems to be a very deep focus on the costs of dependencies during development.

Today I want to talk about another aspect of that. The cost of dependencies when you have a crisis. In particular, consider the case of having a 2 AM support call that is rooted to one of your dependencies. What do you do then?

The customer see a problem in your software, so they call you, and you are asked to resolve it. After you narrowed the problem down to a particular dependency, you now need to check whatever this is your usage of the dependency that is broken, or whatever there is a genuine issue with the dependency.

Let us take a case in point with a recent support call we had. When running RavenDB on a Windows Cluster with both nodes sharing the same virtual IP, authentication doesn’t work. It took us a while to narrow it down to Windows authentication doesn’t work, and that is where we got stuck. Windows authentication is a wonderfully convenient  tool, but if there is an error, just finding out about it require specialized knowledge and skills. After verifying that our usage of the code looked correct, we ended up writing a minimal reproduction with about 20 lines of code, which also reproduced the issue.

At that point, we were able to escalate to Microsoft with the help of the customer. Apparently this is a Kerberos issue and you need to use NTLM and there was a workaround with some network configuration (check our docs if you really care about the details). But the key point here is that we would really have absolutely no way to figure it out on our own. Our usage of Windows authentication was according to the published best practices, but in this scenario you had to do something different to get it to work.

The point here is that if we weren’t able to escalate that to Microsoft, we would be in a pretty serious issue with the customer “we can’t fix this issue” is something that no one wants to hear.

As much as possible, we try to make sure that any dependencies that we take are either:

  • Stuff that we wrote and understand.
  • Open source* components that are well understood.
  • Have a support contract that we can fall back on, with the SLA we require.
  • Non essential / able to be disabled without major loss of functionality.

* Just taking OSS component from some GitHub repo is a bad idea. You need to be able to trust them, which means that you need to be sure that you can go into the code and either fix things or understand why they are broken.

Code review challengeThe concurrent dictionary refactoring–answer

time to read 4 min | 612 words

Here is the full method that we refactored:

 public void ReturnMemory(byte* pointer)
 {
     var memoryDataForPointer = GetMemoryDataForPointer(pointer);

     _freeSegments.AddOrUpdate(memoryDataForPointer.SizeInBytes, x =>
     {
         var newQueue = new ConcurrentStack<AllocatedMemoryData>();
         newQueue.Push(memoryDataForPointer);
         return newQueue;
     }, (x, queue) =>
     {
         queue.Push(memoryDataForPointer);
         return queue;
     });
 }

And here is the allocation map for this method:

public unsafe void ReturnMemory(byte* pointer)
{
    <>c__DisplayClass9_0 CS$<>8__locals0 = new <>c__DisplayClass9_0();
    CS$<>8__locals0.memoryDataForPointer = this.GetMemoryDataForPointer(pointer);
    this._freeSegments.AddOrUpdate(CS$<>8__locals0.memoryDataForPointer.SizeInBytes, 
new Func<int, ConcurrentStack<AllocatedMemoryData>>(CS$<>8__locals0.<ReturnMemory>b__0),
new Func<int, ConcurrentStack<AllocatedMemoryData>, ConcurrentStack<AllocatedMemoryData>>(CS$<>8__locals0.<ReturnMemory>b__1)); }

As you can see, we are actually allocating three objects here. One is the captured variables class generated by the compiler (<>c__DisplayClass9_0) and two delegate instances. We do this regardless of if we need to add or update.

The refactored code looks like this:

 public void ReturnMemory(byte* pointer)
 {
     var memoryDataForPointer = GetMemoryDataForPointer(pointer);

     var q = _freeSegments.GetOrAdd(memoryDataForPointer.SizeInBytes, size => new ConcurrentStack<AllocatedMemoryData>());
     q.Push(memoryDataForPointer);

 }

And what actually gets called is:

public unsafe void ReturnMemory(byte* pointer)
{
    Interlocked.Increment(ref this._returnMemoryCalls);
    AllocatedMemoryData memoryDataForPointer = this.GetMemoryDataForPointer(pointer);
    if(<>c.<>9__9_0 == null)
    {
        <>c.<>9__9_0 = new Func<int, ConcurrentStack<AllocatedMemoryData>>(this.<ReturnMemory>b__9_0);
    }
    this._freeSegments.GetOrAdd(memoryDataForPointer.SizeInBytes, <>c.<>9__9_0).Push(memoryDataForPointer);
}

The field (<>c.<>9__9_0) is actually a static field, so it is only allocated once. Now we have a zero allocation method.

Code review challengeThe concurrent dictionary refactoring

time to read 2 min | 216 words

In a recent code review, I had modified the following code:

_freeSegments.AddOrUpdate(memoryDataForPointer.SizeInBytes, x =>
{
   var newQueue = new ConcurrentQueue<AllocatedMemoryData>();
   newQueue.Enqueue(memoryDataForPointer);
   return newQueue;
}, (x, queue) =>
{
   queue.Enqueue(memoryDataForPointer);
   return queue;
});

Into this code:

var q = _freeSegments.GetOrAdd(memoryDataForPointer.SizeInBytes, 
                         size => new ConcurrentQueue<AllocatedMemoryData>());
q.Enqueue(memoryDataForPointer);

Can you tell me why?

Project Tamar

time to read 1 min | 127 words

I’m happy to announce that despite the extreme inefficiencies involved in the process, the performance issues and what are sure to be multiple stop ship bugs in the way the release process is handled. We have successfully completed Project Tamar.

The result showed up as 2.852 Kg bundle, and is currently sleeping peacefully. I understand that this is a temporary condition, and lack of sleep shall enthuse shortly. I’ll probably regret saying that, but I can’t wait.

 

This little girl is named Tamar and to celebrate, I’m offering a 28.52% discount for all our products. This include:

Just use coupon code: Tamar

This will be valid for the next few days.

Fixing the index, solutions

time to read 4 min | 650 words

In my previous post, I showed a pretty trivial index and asked how to efficiently update it. Efficient being time & memory wise.

The easiest approach to do that is by using a reverse lookup option. Of course, that means that we actually need to store about twice as much data as before.

Given the following documents:

  • users/21 – Oren Eini
  • users/42 – Hibernating Rhinos
  • users/13 – Arava Eini

Previously, we had:

Term Documents
Oren users/21,
Eini users/21, users/13
Hibernating users/42,
Rhinos users/42,
Arava users/13

And with the reverse lookup, we have:

Term Documents Document Terms
Oren users/21,   users/21 Oren, Eini
Eini users/21, users/13   users/42 Hibernating, Rhinos
Hibernating users/42   users/13 Arava, Eini
Rhinos users/42      
Arava users/13      

And each update to the index would first do a lookup for the document id, then remove the document id from all the matching terms.

The downside of that is that we take about twice as much room. The upside is that all the work is done during indexing time, and space is pretty cheap.

It isn’t that cheap, though. So we want to try something better.

Another alternative is to introduce a level of indirection, like so:

Term Documents   Num Id
Oren 1,   1 users/21
Eini 1,3   2 users/42
Hibernating 2   3 users/13
Rhinos 2      
Arava 3      

Now, let us say that we want to update users/13 to be Phoebe Eini, we will end up with:

Term Documents   Num Id
Oren 1,   1 users/21
Eini 1,3,4   2 users/42
Hibernating 2   4 users/13
Rhinos 2      
Arava 3      
Phoebe 4      

We removed the 3rd document, and didn’t touch the terms except to add to them.

That gives us a very fast way to add to the system, and if someone will search for Arava, we will see that  the number no longer exists, so we’ll return no results for the query.

Of course, this means that we have to deal with garbage in the index, and have some way to clean it up periodically. It also means that we don’t have a way to really support Update, instead we have just Add and Delete operations.

Interview questionfix the index

time to read 4 min | 630 words

This is something that goes into the “what to ask a candidate”.

Given the following class:

public class Indexer
{
    private Dictionary<string, List<string>> terms = 
        new Dictionary<string, List<string>>(StringComparer.OrdinalIgnoreCase);

    public void Index(string docId, string text)
    {
        var words = text.Split();
        foreach (var term in words)
        {
            List<string> val;
            if (terms.TryGetValue(term, out val) == false)
            {
                val = new List<string>();
                terms[term] = val;
            }
            val.Add(docId);
        }
    }

    public List<string> Query(string term)
    {
        List<string> val;
        terms.TryGetValue(term, out val);
        return val ?? new List<string>();
    }
}

This class have the following tests:

public class IndexTests
{
    [Fact]
    public void CanIndexAndQuery()
    {
        var index = new Indexer();
        index.Index("users/1", "Oren Eini");
        index.Index("users/2", "Hibernating Rhinos");

        Assert.Contains("users/1", index.Query("eini"));
        Assert.Contains("users/2", index.Query("rhinos"));
    }

    [Fact]
    public void CanUpdate()
    {
        var index = new Indexer();
        index.Index("users/1", "Oren Eini");
        //updating
        index.Index("users/1", "Ayende Rahien");

        Assert.Contains("users/1", index.Query("Rahien"));
        Assert.Empty(index.Query("eini"));
    }
}

The first test passes, but the second fails.

The task is to get the CanUpdate test to pass, while keeping memory utilization and CPU costs as small as possible. You can change the internal implementation of the Indexer as you see fit.

After CanUpdate is passing, implement a Delete(string docId) method.

Figure this code?

time to read 3 min | 547 words

I have just finished writing this code, and it occurred to me that on its own, it makes very little sense.

private static int RedactedFunctionName(List<int> a, List<int> b)
{
    List<int> n,m;
    if (a.Count > b.Count)
    {
        n = a;
        m = b;
    }
    else
    {
        n = b;
        m = a;
    }

    int nSize = n.Count;
    int mSize = m.Count;

    double o1 = nSize + mSize;
    double o2 = nSize * Math.Log(mSize, 2);

    int result = 0;
    if (o1 < o2)
    {
        int mi = 0, ni = 0;
        while (mi < mSize && ni < nSize)
        {
            if (n[ni] > m[mi])
            {
                mi++;
            }
            else if (n[ni] < m[mi])
            {
                ni++;
            }
            else
            {
                ni++;
                mi++;
                result++;
            }
        }
    }
    else
    {
        for (int i = 0; i < mSize; i++)
        {
            if (n.BinarySearch(m[i]) >= 0)
                result++;
        }
    }
    return result;
}

Can you figure out what this function does, why is it behaving in this manner, and what preconditions it expects?

FUTURE POSTS

  1. The worker pattern - 10 hours from now

There are posts all the way to May 30, 2016

RECENT SERIES

  1. The design of RavenDB 4.0 (14):
    26 May 2016 - The client side
  2. RavenDB 3.5 whirl wind tour (14):
    25 May 2016 - Got anything to declare, ya smuggler?
  3. Tasks for the new comer (2):
    15 Apr 2016 - Quartz.NET with RavenDB
  4. Code through the looking glass (5):
    18 Mar 2016 - And a linear search to rule them
  5. Find the bug (8):
    29 Feb 2016 - When you can't rely on your own identity
View all series

Syndication

Main feed Feed Stats
Comments feed   Comments Feed Stats