BDB storage engine

[Michael Weber]

Ok, I have all of the storage actions done for the BDB storage engine, and I think they are functional.  I am going through all of the tests in the test bed to try to make sure everything is working and I'm running into a problem.  Take a very simple index test like BoostingDuringIndexing.CanGetBoostedValues.  It inserts two documents and makes sure we can query the boost order correctly.  With the new storage engine, both documents insert correctly, then when the the system goes to index them versus the builtin index Raven/DocumentsByEntityName and the test bed index, we get a deadlock in the IIndexingStorageActions.UpdateIndexingStats (almost every time).

The problem seems to be that both index threads try to update their stats count at the same time, and since the documents for the indexing stats are small, they both hit the same page of the db.  And since BDB locks based on pages, we get a deadlock.  Now, when we get a deadlock, we are supposed to abort the transaction and retry.  I'm not sure exactly how to do that, and it sort of seems like IsWriteConflict is supposed to handle that.

If I handle IsWriteConflict and check to see if we had a deadlock and abort the transaction then we do move forward, but of course the indexing stats are not updated.  And when the test goes to run the query, we get zero results, even though in the database it says that the index has been indexed up to the correct etag.  And checking the lucene index with Luke shows that all documents are present.

I'm not exactly sure how to get past this problem.  Attached is the log file for the unit test run.

BTW, I did at least do some bulk insert testing from the freedb database loader (5 minute run), this is with no performance work at all

ESENT

folk/f00d1312 142,561  00:04:59.9769034

total inputs: 142584

Done in 00:05:00.0250306

BDB

folk/af0ae30e 109,753  00:04:59.9160742

total inputs: 109776

Done in 00:05:00.0048137

[Michael Weber]

Actually, now that I think about it in order to retry after a deadlock, we would just do the retries in TransactionalStorage.ExecuteBatch.  That is assuming all actions queued by that batch message are idempotent.  And that may work for future deadlocks we encounter, but it doesn't work for this scenario (without changes) since the DeadlockException will never reach ExecuteBatch since it's caught to produce "Failed to index documents for index......".

And in general for the deadlock retry to work from ExecuteBatch we need to make sure that no batched action ever catches our exception.

[Oren Eini (Ayende Rahien)]

Michael

You cannot re-execute the action, those are NOT guaranteed to be idempotent.

[Oren Eini (Ayende Rahien)]

Nice numbers for the perf, let us start with that.

We rely quite heavily on the fact that we can update separate rows on the indexing stats.

This is the key for being able to parellelize indexing.

Can you change the page size for that data?

Can you maybe force it to be on another page?

[Michael Weber]

Well I'm not sure how to fix the deadlock problem in general then... These are the most common deadlocks bu of course deadlocks are always possible anywhere and our only recourse is to abort the transaction and retry.

[Michael Weber]

I've tried that on the data leaf page but it still tries to hit the same page. Maybe because of a higher btree node. I can try inserting additional records to force the keys on different pages and see if that works.

[Oren Eini (Ayende Rahien)]

What about not updating the record?

But create a new one?

So you always look at the latest record, and you clean them out every once in a while?

[Michael Weber]

Yeah, that could work also, but are there ever two threads updating the same index?  If that's true then any of these could be a problem.

I am going to look into using a BDB queue for the index table:

"Queue if your application requires high degrees of concurrency. Queue provides record-level locking (as opposed to the page-level locking that the other access methods use), and this can result in significantly faster throughput for highly concurrent applications."

[Louis Haußknecht]

Great to see this moving forward! However what about licensing?

http://en.wikipedia.org/wiki/Berkeley_DB states BDB needs to be licensed by oracle if used in non open-source products. 

If one is developing a closed-source product with RavenDB and using BDB as storage engine, would you need to license both?

[clayton collie]

Would that not be an issue for HR, not individual developers ?

[Michael Weber]

I don't know much about the licenseing, but I found this from an oracle licenseing faq:

Berkeley DB is available under dual license:

*  Public license that requires that software that uses the Berkeley DB code be free/open source software; and

*  Closed source license for non-open source software.

If your code is not redistributed, no license is required (free for in-house use).

On Wednesday, August 22, 2012 9:24:42 AM UTC-4, Louis Haußknecht wrote:

[Oren Eini (Ayende Rahien)]

The same index, no.

But different indexes, all the time.

[Oren Eini (Ayende Rahien)]

Which pretty much solves the problem for us, yes.

[Michael Weber]

Ok -- that actually makes it easier, then what about having a separate file for each index?  That would prevent deadlocks versus writes.

[Oren Eini (Ayende Rahien)]

Sure, that can work, but would it still be consistent across all files?

[Michael Weber]

Will what be consistent?

[Oren Eini (Ayende Rahien)]

Transactionally consistent between the different files?

[Michael Weber]

Ah, yes BDB is consistent across files.  When you get a lock its for a file + page.

And I'm not actually talking about a physical file.  It will be the virtual databases in the physical file.  Like in  http://mikecodespot.blogspot.com/2012/08/how-to-create-index.html

[Oren Eini (Ayende Rahien)]

Oh, okay

[Michael Weber]

Ok -- I've done that and they each index's stats are certainly on a different page now, and I don't seem to get a lock between different indexes now.

Now I'm getting another write/ write deadlock between what my guess is updating the stats and updating the etag/last time.  Do this happen on different threads?

[Oren Eini (Ayende Rahien)]

You also need to make sure that reduce updates and map updates happens on different places.

[Oren Eini (Ayende Rahien)]

We do update the stats for the same index in parallel for map & reduce stats.

[Michael Weber]

Ok that combined with the fact you cannot delete sections of a database file means we will need one physical file per index and 3 sections in each file: the map stats, the reduce stats and the touch counts.

Then I can just delete the physical file when we delete an index. And it should keep everything separate.

Do the new mapped results, scheduled reduction and reduction results work similarly with respect to threading versus index name? Because I'm already starting to see problems from those tests as well.

[Michael Weber]

I've made some progress with this and am starting to like the way it's turning out, but I'm still getting two writes (one to stats, one to etag/timestamp) on separate thread.  From my logging (5,0,6 is the internal record IDs for the map, reduce and touch tables)

2012-08-22 15:44:50.7529 11 Update(pagesByTitle2:5,0,6)

2012-08-22 15:44:50.7529 8 UpdateStats(pagesByTitle2:5,0,6)

Thread 11 tries to update the etag/timestamp while thread 8 is updating the stats (both for map index), thus, we are getting a deadlock on record #5

[Michael Weber]

Oh -- I think it's the MaxNumberOfParallelIndexTasks.  I guess there can be more than one thread updating the stats.  I'm not sure how to fix the deadlocks assuming that there is more than one thread updating the stats at the same time.

[Oren Eini (Ayende Rahien)]

For maps and reduces at the same level for the index, you don't have concurrency.

But scheduled reduction can have concurrent writes. Note the way that we do this in Esent, we always write, then we do a cleanup.

[Oren Eini (Ayende Rahien)]

What is the TransactionStorage method that get called here?

[Michael Weber]

Thread #1

2012-08-22 16:21:22.4747 19 Update(pagesByTitle2:5,0,6) 

2012-08-22 16:21:22.4747 19    at System.Environment.GetStackTrace(Exception e, Boolean needFileInfo)

   at System.Environment.get_StackTrace()

   at Raven.Storage.Bdb.Tables.IndexingStatsTable.Update(Txn txn, String name, Guid etag, DateTime timestamp) in c:\dev\ravendb\Raven.Database\Storage\Bdb\Tables\IndexingStatsTable.cs:line 101

   at Raven.Storage.Bdb.StorageActions.DocumentStorageActions.UpdateLastIndexed(String index, Guid etag, DateTime timestamp) in c:\dev\ravendb\Raven.Database\Storage\Bdb\StorageActions\Indexing.cs:line 43

   at Raven.Database.Indexing.IndexingExecuter.<>c__DisplayClass19.<ExecuteIndexingWork>b__a(IStorageActionsAccessor actions) in c:\dev\ravendb\Raven.Database\Indexing\IndexingExecuter.cs:line 139

   at Raven.Storage.Bdb.TransactionalStorage.ExecuteBatch(Action`1 action) in c:\dev\ravendb\Raven.Database\Storage\Bdb\TransactionalStorage.cs:line 129

   at Raven.Storage.Bdb.TransactionalStorage.Batch(Action`1 action) in c:\dev\ravendb\Raven.Database\Storage\Bdb\TransactionalStorage.cs:line 100

   at Raven.Database.Indexing.IndexingExecuter.ExecuteIndexingWork(IList`1 indexesToWorkOn) in c:\dev\ravendb\Raven.Database\Indexing\IndexingExecuter.cs:line 135

   at Raven.Database.Indexing.AbstractIndexingExecuter.ExecuteIndexing() in c:\dev\ravendb\Raven.Database\Indexing\AbstractIndexingExecuter.cs:line 174

   at Raven.Database.Indexing.AbstractIndexingExecuter.Execute() in c:\dev\ravendb\Raven.Database\Indexing\AbstractIndexingExecuter.cs:line 42

   at System.Threading.Tasks.Task.InnerInvoke()

   at System.Threading.Tasks.Task.Execute()

   at System.Threading.Tasks.Task.ExecutionContextCallback(Object obj)

   at System.Threading.ExecutionContext.RunInternal(ExecutionContext executionContext, ContextCallback callback, Object state, Boolean preserveSyncCtx)

   at System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state, Boolean preserveSyncCtx)

   at System.Threading.Tasks.Task.ExecuteWithThreadLocal(Task& currentTaskSlot)

   at System.Threading.Tasks.Task.ExecuteEntry(Boolean bPreventDoubleExecution)

   at System.Threading.Tasks.ThreadPoolTaskScheduler.LongRunningThreadWork(Object obj)

   at System.Threading.ThreadHelper.ThreadStart_Context(Object state)

   at System.Threading.ExecutionContext.RunInternal(ExecutionContext executionContext, ContextCallback callback, Object state, Boolean preserveSyncCtx)

   at System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state, Boolean preserveSyncCtx)

   at System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state)

   at System.Threading.ThreadHelper.ThreadStart(Object obj) 

Thread #2

2012-08-22 16:21:22.4747 8 Update(pagesByTitle2:5,0,6) 

2012-08-22 16:21:22.4877 8    at System.Environment.GetStackTrace(Exception e, Boolean needFileInfo)

   at System.Environment.get_StackTrace()

   at Raven.Storage.Bdb.Tables.IndexingStatsTable.Update(Txn txn, String name, Guid etag, DateTime timestamp) in c:\dev\ravendb\Raven.Database\Storage\Bdb\Tables\IndexingStatsTable.cs:line 101

   at Raven.Storage.Bdb.StorageActions.DocumentStorageActions.UpdateLastIndexed(String index, Guid etag, DateTime timestamp) in c:\dev\ravendb\Raven.Database\Storage\Bdb\StorageActions\Indexing.cs:line 43

   at Raven.Database.Indexing.IndexingExecuter.<>c__DisplayClass19.<ExecuteIndexingWork>b__a(IStorageActionsAccessor actions) in c:\dev\ravendb\Raven.Database\Indexing\IndexingExecuter.cs:line 139

   at Raven.Storage.Bdb.TransactionalStorage.ExecuteBatch(Action`1 action) in c:\dev\ravendb\Raven.Database\Storage\Bdb\TransactionalStorage.cs:line 129

   at Raven.Storage.Bdb.TransactionalStorage.Batch(Action`1 action) in c:\dev\ravendb\Raven.Database\Storage\Bdb\TransactionalStorage.cs:line 100

   at Raven.Database.Indexing.IndexingExecuter.ExecuteIndexingWork(IList`1 indexesToWorkOn) in c:\dev\ravendb\Raven.Database\Indexing\IndexingExecuter.cs:line 135

   at Raven.Database.Indexing.AbstractIndexingExecuter.ExecuteIndexing() in c:\dev\ravendb\Raven.Database\Indexing\AbstractIndexingExecuter.cs:line 174

   at Raven.Database.Indexing.AbstractIndexingExecuter.Execute() in c:\dev\ravendb\Raven.Database\Indexing\AbstractIndexingExecuter.cs:line 42

   at System.Threading.Tasks.Task.InnerInvoke()

   at System.Threading.Tasks.Task.Execute()

   at System.Threading.Tasks.Task.ExecutionContextCallback(Object obj)

   at System.Threading.ExecutionContext.RunInternal(ExecutionContext executionContext, ContextCallback callback, Object state, Boolean preserveSyncCtx)

   at System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state, Boolean preserveSyncCtx)

   at System.Threading.Tasks.Task.ExecuteWithThreadLocal(Task& currentTaskSlot)

   at System.Threading.Tasks.Task.ExecuteEntry(Boolean bPreventDoubleExecution)

   at System.Threading.Tasks.ThreadPoolTaskScheduler.LongRunningThreadWork(Object obj)

   at System.Threading.ThreadHelper.ThreadStart_Context(Object state)

   at System.Threading.ExecutionContext.RunInternal(ExecutionContext executionContext, ContextCallback callback, Object state, Boolean preserveSyncCtx)

   at System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state, Boolean preserveSyncCtx)

   at System.Threading.ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, Object state)

   at System.Threading.ThreadHelper.ThreadStart(Object obj) 

[Michael Weber]

I may have you chasing ghosts here.... I finally sat down and said let me find out the exact database PUT/GET that's causing the deadlock when lo and behold I saw that the deadlock was not coming from the database, but coming from the c#/BDB interface.  They have a global lock(obj) { } around every put/get which was causing the seen deadlock and hiding any database deadlocks.  Unfortunately now that I have freed up the database to produce the real deadlocks, I can see them coming through for a slightly different reason:

Now they seem to mostly occur with a write from the UpdateIndexingStats from the index thread and the IsIndexStale read from the front-end query.  Extending the deadlock timeout range helps solve those (of course), but eventually we may want to look at other options.

[Michael Weber]

Turning on snapshot isolation has helped with the deadlocks between the  IsIndexStale and UpdateIndexingStats.  From a deadlock point of view, things seem to be looking up.

[Oren Eini (Ayende Rahien)]

IsIndexStale() is an operation that happens a LOT and should use snapshot isolation

[Jesús López]

I wonder why you are using this .NET wrapper http://sourceforge.net/projects/libdb-dotnet/ instead of the official one provided by Oracle.

 

On Wednesday, August 22, 2012 5:37:22 AM UTC+2, Michael Weber wrote:

Ok, I have all of the storage actions done for the BDB storage engine, and I think they are functional.  I am going through all of the tests in the test bed to try to make sure everything is working and I'm running into a problem.  Take a very simple index test like BoostingDuringIndexing.CanGetBoostedValues.  It inserts two documents and makes sure we can query the boost order correctly.  With the new storage engine, both documents insert correctly, then when the the system goes to index them versus the builtin index Raven/DocumentsByEntityName and the test bed index, we get a deadlock in the IIndexingStorageActions.UpdateIndexingStats (almost every time).

The problem seems to be that both index threads try to update their stats count at the same time, and since the documents for the indexing stats are small, they both hit the same page of the db.  And since BDB locks based on pages, we get a deadlock.  Now, when we get a deadlock, we are supposed to abort the transaction and retry.  I'm not sure exactly how to do that, and it sort of seems like IsWriteConflict is supposed to handle that.

If I handle IsWriteConflict and check to see if we had a deadlock and abort the transaction then we do move forward, but of course the indexing stats are not updated.  And when the test goes to run the query, we get zero results, even though in the database it says that the index has been indexed up to the correct etag.  And checking the lucene index with Luke shows that all documents are present.

I'm not exactly sure how to get past this problem.  Attached is the log file for the unit test run.

BTW, I did at least do some bulk insert testing from the freedb database loader (5 minute run), this is with no performance work at all

ESENT

folk/f00d1312 142,561  00:04:59.9769034

total inputs: 142584

Done in 00:05:00.0250306

BDB

folk/af0ae30e 109,753  00:04:59.9160742

total inputs: 109776

Done in 00:05:00.0048137

[Michael Weber]

At the time I wasn't aware there was a interface from oracle.  I will look into it.

[Chris Marisic]

If Oracle's C# code for this is anything like ODP.NET

FUCKING RUN FOR THE HILLS AND SET OFF NUCLEAR DEVICES

[Michael Weber]

After looking at this, I don't think it will work for what we need.  For instance the c# wrapper doesn't support partial reads or writes which we use extensively.

On Thursday, August 23, 2012 5:57:18 AM UTC-4, Jesús López wrote:

[Jesús López]

I think It does support it. Take a look at DatabaseEntry class, it has some properties related to partial reads and writes like Partial, PartialLen, and PartialOffset.

[Michael Weber]

You may be right...  In the end, with BDB it all comes down to what version you want to support.  I was looking a 4.8 (which is the first version that supported c# from oracle).  The wrapper I'm using right now supports 4.5 and 4.3.  I was staying in the 4.x region since that is typically what is released with linux distributions (but even then the chances of matching 4.5 or 4.3 exactly is slim).

So we need to figure out what version we want to support.  A list of current versions per incompatible release is here

http://www.oracle.com/technetwork/products/berkeleydb/downloads/index-082944.html 

[Oren Eini (Ayende Rahien)]

Is there a reason to no go with the latest?

[Michael Weber]

I wouldn't think so.  It doesn't seem like you can get a compatible version with yum or apt-get from any distrubution I've used recently (4.7.25 on centos, 5.1.25 on some fedora version, 4.2/4.5/4.6 on debian).  So we are going to have to provide binaries or you are going to have to compile it yourself.  So if that's the case then going with the latest seems to be ok.

I should probably do some actual tests with the oracle c# interface on linux to make sure it works...

I also have to figure out the 32/64 bit problem with DllImport.

[Oren Eini (Ayende Rahien)]

I am fine with having to deploy the binaries, we would probably need to do that anyway, to make it an xdeploy

[Michael Weber]

How do you want to handle the source, do we put the BDB tree in the packages directory?

[Oren Eini (Ayende Rahien)]

Don't know.

Would rather avoid blow our repo size.

And it isn't like we are going to do a custom build of that.

Maybe just a reference to the version we use?

[Michael Weber]

Yeah -- i would think we would just compile the binaries, include them in the packages directory like the other libraries and include the version we got binaries from

[Michael Weber]

Ok -- i got the latest version to compile binaries, with the oracle c# interface.  And the test program that came with it worked fine on windows.  Trying to get the c# interface to work on linux was another story.  Oracle seems to be doing something with pinvoke that is not really supposed to be allowed (and I don't know that it will work, if the GC moves the objects it's taking pointers to, can write up a blog post on if anyone want to know).  But regardless mono refuses to run it.  So I had to make some changes to the interface library to get around that issue.  But banging my head for a few hours on that I got the same test program to run on linux/mono also.

So now it's time to port the raven storage engine over to the oracle interface, hopefully it won't be too bad.

[Oren Eini (Ayende Rahien)]

Can you explain the thing it is doing? Maybe is isn't pinning things?

[Chris Marisic]

Make sure to do extensive testing for memory leaks when you work with oracle C# code.

[Michael Weber]

There are three cases where they are storing a wrapper object in an unmanaged structure (for returning later to a c# callback).  But they are just passing the object itself to the dllimport function.

[DllImport(libname, EntryPoint="CSharp_DB_ENV_api2_internal_set")]

  public static extern void DB_ENV_api2_internal_set(HandleRef jarg1,  DatabaseEnvironment  jarg2);

  [DllImport(libname, EntryPoint="CSharp_DB_ENV_api2_internal_get")]

  public static extern  DatabaseEnvironment  DB_ENV_api2_internal_get(HandleRef jarg1);

  internal DatabaseEnvironment api2_internal {  set {

      libdb_csharpPINVOKE.DB_ENV_api2_internal_set(swigCPtr, value);

    }  get { return libdb_csharpPINVOKE.DB_ENV_api2_internal_get(swigCPtr); } }

On windows, this seems to work (at least in the short term, as I haven't tested more than that).  The DatabaseEnvionment variable isn't pinned anywhere, so unless the marshaling handles it with a reference to a pointer being stored, then I don't think this will hold up.  On mono, you cannot have the argument DatabaseEnvironment since it doesn't have a [StructLayout].  And we aren't trying to store a structure anyway, so this wouldn't be what we want.

I solved it by replacing the DatabaseEnvironment parameter with a delegate argument (that is marshaled and pinned properly).  Then when I get back the delegate (which I don't really care about), I can pull out the Target property which is the c# object that we wanted to hold a reference to anyway.

[Oren Eini (Ayende Rahien)]

Yes, much better.

[Oren Eini (Ayende Rahien)]

For what it worth, when I started to use Esent, they had much the same issues, it got fixed since them, with our help

[Michael Weber]

I believe it, the unmanaged stuff is a pain.

And I do think that we should do extensive testing to make sure we aren't leaking any memory, but I think we would need to do that with any unmanaged wrapper, oracle or not.  And this wrapper has a much cleaner code base than the one I was using before, so if we do need to keep making changes it should be easier to do (for example I already see some potential performance problems with this wrapper, that we will need to analyze eventually)

[Michael Weber]

Chris may be right... I've converted the BDB over to the latest version of BDB and the oracle provider and I've had nothing but problems...  Strange unhandled exceptions and corrupted memory on unmanaged calls.  There are a couple other things I don't like:

It copies buffers from unmanaged to managed on every read and write

It throws exceptions on record not found instead of just returning an error code

It relies on finalizers to clean up disposable database buffers

I am thinking of going back to the one I had working and was happy with, but it only supports bdb 4.5, but as we don't use any of the features from the newer versions, I don't see why that would be a problem.  The only think I have to do is verify that the c# interface I have for 4.5 is compatible with linux.

[Oren Eini (Ayende Rahien)]

Okay, we need to make sure if there aren't any critical bugs since 4.5 

[Michael Weber]

Well they have minor releases within each major version.  The real version is 4.5.20.

[Oren Eini (Ayende Rahien)]

Okay

[Michael Weber]

OK -- after reverting to the 4.5 version of what I had, and building a linux version of BDB 4.5.20 (and adjusting some of of the DllImports), I can build Raven.Database, etc. on windows, then run it with mono:

using(var tx = NewTransactionalStorage())

{

tx.Batch(mutator => mutator.Documents.AddDocument("Ayende", null, RavenJObject.FromObject(new { Name = "Rahien" }), new RavenJObject()));

tx.Batch(mutator => mutator.Documents.AddDocument("Ayende", null, RavenJObject.FromObject(new { Name = "Oren" }), new RavenJObject()));

tx.Batch(x => Console.WriteLine(x.Documents.GetDocumentsCount()));

RavenJObject document = null;

tx.Batch(viewer => { document = viewer.Documents.DocumentByKey("Ayende", null).DataAsJson; });

Console.WriteLine(document.Value<string>("Name"));

}

The previous test is successful, and dumping the database you can see the data in the file.

[clayton collie]

Fantastic news. This was the final piece of my stack without a Linux story.

BTW - also enjoyed the blog posts..

[Oren Eini (Ayende Rahien)]

Awesome, in so many ways.

[Chris Marisic]

Oracle is just epic fail when it comes to .NET. At my first software development job the company used oracle 10g, it was IMPOSSIBLE to write to a Large object (LOB), Char large object (CLOB) or Binary large object (BLOB) column in oracle without massive memory leaks from the client. It was horrendous, there was no solution except to set app recycle to like every hour for us.

[Ryan Heath]

Unfortunately I have had the same experience with their .net api <sigh>

// Ryan