So to start with what does “LurchTable” stand for?

Least
Used
Recently
Concurrent
Hash
Table

Of course I am dyslexic so I can get away with swapping U and R around. My dyslexia aside, It’s a fair representation of what the class does. It essentially is a ConcurrentDictionary that keeps and maintains a linked-list of nodes in specific way. It does differ significantly from ConcurrentDictionary in a few very important ways…

  1. The number of hash buckets available can not change after construction. This keeps the code simple and maintainable while providing all the tread-safety goodness. This is also going to be the biggest change from the ConcurrentDictionary. The LurchTable is typically used with a hard-limit on items. For example a cache might allow no more than 10k items. So we probably want at least 5k hash buckets, each ‘bucket’ is just an integer so this would pre-allocate 20kb of memory as an int[]. On the extreme end, if you were to supply int.Max as the hash size you would exceed .NET’s ability to allocate the memory required.
  2. Key/Value pairs (entries) are allocated and expanded dynamically as-needed. Unused entries are tracked in a separate linked-list. Unlike the .NET Framework’s Dictionary that will fail when adding the ‘nth’ entry due to an OutOfMemoryException being raise, the LurchTable does not allocate all entries as a single array. The allocation size is specified (or derived) at construction and the LurchTable will allocate a new array of this size and ‘append’ it to the existing allocated entries. This preserves time and memory as the contents of the dictionary fluctuate and prevent the LurchTable from attempting excessively large allocations.
  3. The linked lists, both used and unused entries, are maintained via lockless linked lists. The use of non-blocking linked lists allows for a high-degree of concurrent modifications to be made to the contents of the collection. This approach also greatly reduces the contention on the ‘free’ entries required to find an empty entry to use for a new item. In addition, the LurchTable maintains several ‘free’ lists to even further reduce contention.

Linking Entries

Entries can be either non-linked, linked by insertion, lined by insertion or modification, or linked by insertion, modification or access. The internal linking strategy is determined at construction by specifying one of the LurchTableOrder enumeration members (Access, Insertion, Modified, None). When ordering by anything other than None, a hard-limit on items can be specified at construction as well. When a hard-limit is set, the insertion of n+1 items will cause the ‘oldest’ item in the ordered list to be removed. Typically all this is specified at construction by using the more verbose ctor on the LurchTable:

    public LurchTable<TKey, TValue>(
        LurchTableOrder ordering,         // One of Access, Insertion, Modified, or None
        int limit,                        // Hard-limit number of items, or int.MaxValue for no limit
        int hashSize,                     // The number of hash buckets to allocate (adjusted up to a prime number)
        int allocSize,                    // The number of items to allocate at once (power of 2 that is < = allocSize)
        int lockSize,                     // The number of locks to allocate (adjusted up to a prime number)
        IEqualityComparer<TKTKey> comparer  // The comparer to use for the keys
    )

Other Deltas from the ConcurrentDictionary

New methods not typically found on a dictionary include the ability to Peek, Dequeue, or TryDequeue the oldest item in the collection. Peek will return the oldest entry based upon the link order. TryDequeue will attept to remove the oldest entry based upon the link order and can optionally take a predicate to control removal. Lastly, Dequeue is a tight-polling loop on TryDequeue and returns only after an item is successfully dequeued (Note: For obvious reasons Dequeue should be used cautiously).

All enumerations of the LurchTable are thread-safe and in Hash-order. Due to the lockless nature of the internal linking, it is not possible to enumerate the contents of the collection in the linked order. Enumeration of the links could easily be added; however, it would not be thread-safe and thus is not currently implemented.

All methods on the collection are thread-safe except the “Initialize” method. The Initialize() method recreates the internal ‘entries’ collection and essentially removes all items in O(1) whereas the Clear() method is now an O(n) time operation.

Events for ItemAdded, ItemUpdated, and ItemRemoved are exposed from the collection and are executed in-lock with the operation. While I don’t like events that execute from synchronized code, there really isn’t a better way to deal with this. Since I heavily rely on ItemRemoved events to flush data from a LurchTable cache to primary store, the event must act as an atomic operation to the consumer of the collection. All events are fire after internal structures have been modified and just prior to lock-release. Care should be taken not to raise exceptions from these events as these will propagate to the caller attempting to add/update/remove the item.

Uses for LurchTable

  • LRU Cache An LRU (Least Recently Used) cache is the most common of applications for this structure. Simply configure a hard-limit on the items and use LurchTableOrder.Access at construction. Then from the caller use the GetOrAdd call to either pull from cache or fetch from primary and add to cache in a single call.
  • Write-through Cache Another common usage might be a write-behind/delayed-write strategy for an external storage mechanism. Constructing with a hard-limit and using LurchTableOrder.Modified will give you a read-through/write-through cache. Use the GetOrAdd to fetch and any of the available set operations to write, then hook the ItemRemoved to flush to external storage.
  • Throttling Work Queue An interesting use (or abuse?) of the LurchTable is using it to distribute work across several threads. When a producer of work can outpace the ability of the consumers one needs to throttle the producer. One way is to simply sleep the producer until more work can be queued, another is to let the producer also consume work. Construct with LurchTableOrder.Insert and a hard-limit on the back-log to allow. Hook the ItemRemoved event to implement the work item processing. Start one or more threads producing work items by adding them to the dictionary. Finally start one or more threads consuming data by calling Dequeue/TryDequeue. This works well if the work to be performed is small (since the consumer can block the producer), mileage may vary for longer running tasks.

I’ve used this collection extensively for the past year and have been very pleased with the results and ease of use. It’s probably one of the more versatile and better pieces of code I’ve put together in a while. Give it a try by just including the source directly (/browse/src/Library/Collections/LurchTable.cs) or by using the NuGet package CSharpTest.Net.Library. You can also find the online help at http://help.csharptest.net.

 

Time has clearly come to accomplish two things…

  1. Move to GitHub.com instead of google code
  2. Split the library apart based on consumer feedback
Why move to GitHub?  While I still prefer mercurial there are a couple of things that motivate me to make the switch.  Firstly Google has utterly failed to get to a point where community contribution are easy and painless.  They also do not provide a whole-project download and with the removal of downloads I can no longer provide one easily.  Lastly I’m no longer receiving appropriate alerts about issues being entered, and thus much of your valuable feedback is being ignored.

As to breaking the library apart, I think it’s just well past due.  At the onset of this library the goal was not to really provide any one thing that was useful, but rather a collection of small things that support a larger project.  That just simply no longer holds true.  Many users have requested that the BPlusTree be split off as well as the SslTunnel and the RpcLibrary.  This makes a lot of sense as these components have matured to a state of being able to stand alone. So I am in the process of breaking out the following projects:

  • CSharpTest.Net.Collections (BPlusTree, LurchTable, OrdinalList, and others)
  • CSharpTest.Net.Commands (The CommandInterpreter and dependecies)
  • CSharpTest.Net.RpcLibrary
  • CSharpTest.Net.SslTunnel
  • CSharpTest.Net.Tools (CmdTool, ResX Exception Generators, StampVersion, StampCopyright)
I am leaning towards keeping the CSharpTest.Net.Library around but pruning out most of the functionality that is encompassed above as well as some more-or-less obsolete stuff.  The issue I struggle with is keeping it’s name or not…  TBD
 
Also, be aware that projects are being migrated to .NET 4 builds with Visual Studio 2012 projects.  They should still compile under 2.0/3.5 but after this past release they will no longer be included in nuget packages.
 
Please leave comments if you like to make any specific requests regarding the move/transition…
 

Additions in this release:

  1. Added CSharpTest.Net.Collections.LurchTable a thread-safe dictionary with the option of linking entries by insert, modify, or access. (LinkedHashMap for C#)
  2. Added CSharpTest.Net.Data.DbGuid to provide time based sequential GUID generation (COMB Guid).
  3. BPlusTree added INodeStoreWithCount and allowed injection of IObjectKeepAlive implementation.
  4. Added Crc64 for a quick 64-bit CRC using algorithm (CRC-64/XZ)
  5. Added a simple HttpServer class.
  6. Added Services/ServiceAccessRights and Services/SvcControlManager to provide more control over services.
  7. Added Http/MimeMessage to parse raw HTML form where ContentType = “multipart/form-data”, including one or more attachments.
  8. Extended the CommandInterpreter to allow exposing console commands over REST services via built-in service.
  9. Added a CallsPerSecondCounter to allow quick estimation of performance metrics in high-traffic code.
  10. Added an experimental TcpServer (currently under test)
  11. Extended the RpcError enumeration to encompass more errors and decorated descriptions.
  12. RpcLibrary now supports RpcServerRegisterIf2 allowing un-authenticated TCP access and control of max TCP request size.
  13. Added the IDL for the RpcLibrary for unmanaged interop

Fixes in this release:

  1. Converted BPlusTree’s Storage.Cache to use LurchTable to address memory issues in buggy LRU cache.
  2. Optimization of BPlusTree’s TransactedCompoundFile in location of free data blocks.
  3. Fixed the dreaded SEHException in the RpcLibrary, now expect acurate RpcException with correct RpcError details.
 

In my previous post “Why GUID primary keys are a database’s worst nightmare” I spoke about some of downsides to using GUID primary keys. In this post I’m going to focus more specifically on the .NET Framework’s implementation of System.Guid. I have a few complaints about this class, let’s cover them…

1. Guid.ToByteArray()

This, IMHO, is one of the worst possible things about a Guid. First this method returns a byte array in little-endian format. Not only is this directly opposite the stated standard GUID format, but it also means the bytes do not compare the same as the structured value. Thus when you combine System.Guid with a sequential guid generation you wind up with either a structure that doesn’t compare sequentially, or a byte array that doesn’t compare sequentially. Yes you can always swap bytes (1,4), (2,3), (5,6), and (7,8), but really? should I have to?

The second issue I have with this method is that it absolutely requires me to allocate the bytes on the heap. While this may not sound like such a big deal, if you are moving large volumes of data and serializing those Guids the only way you can (as byte[]) it will thrash the GC. I’m hopeful that in some future version of .NET we will find a Guid with a ToByteArray(GuidFormatType, byte[], offset) where GuidFormatType would allow little-endian or big-endian formats.

2. Guid.GetHashCode()

This one does puzzle me. They choose to completely ignore bytes 9, 10, 12, 13, 14, and 15 when computing a Guid’s hash code. Ok so maybe with random Guids this really doesn’t matter, but when you start trying to use Guid with sequential values this starts to impact hash performance. If, as in my example on the previous post, bytes 1-8 are date-time, then your entire hash value amounts to the entropy introduced in bytes 11 and 16. To be specific, byte 11 xors with the MSB and byte 16 xors with the LSB.

3. Guid.NewSequentialGuid()

Don’t you wish that .NET could just do this for us? We’ve know this to be a problem, and have know of a resolution to it, since 2002. They’ve even added “NEWSEQUENTIALGUID()” to Sql Server. Wouldn’t you think they could get this done for us? I guess until they fix the endianness of ToByteArray it’s really a moot point anyway.

Of course one option is to just PInvoke UuidCreateSequential.

static class Win32
{
    [DllImport("rpcrt4.dll", SetLastError=true)]
    public static extern int UuidCreateSequential(out Guid guid);
}

4. Guid.(Missing Properties)

Another annoyance is the lack of exposing the values of the Guid. Would it have really been that hard to expose the same integer, two shorts, and 8 bytes that we can pass to the constructor? One could then create an efficient binary serializer for the Guid type without a GC allocation and without worrying about byte-swapping little-endian values. In addition, the underlying randomization could then be reused without using the ToByteArray method. Maybe this isn’t a big deal for most people, but I’m still miffed that (AFAIK) there is not a single thread-safe means of creating a random value without allocating a byte[].

 

When you ask most people why using a GUID column for a primary key in a database might be slower than auto-incremented number the answer your likely to get is usually along these lines:

“Guids are 16 bytes, and integers are only 4 bytes.”

While this information is technically accurate, it is completely the wrong answer to the question. The performance delta from a 16 byte key to a 4 byte key is most likely negligible and almost certainly impossible to accurately measure. To understand what is wrong with a guid, you first need to know a little about how a database stores it’s data.

The most common storage used by databases (to the best of my knowledge) is a B+Tree. They offer great performance even for very large sets of data. They do however suffer from one problem, let’s call this ‘key density‘.

By key density I’m referring to the density, or close proximity, of the keys being accessed at any given moment as it compares the universe of all the keys in storage. For example let’s say I have 10 million records, each keyed by a unique integer numbered from 1 to 10,000,000. I can say that keys {44,46,52} have a high-density, whereas keys {100,10553,733555} have a very low-density.

Cache is everything. When a database needs to read or write a record, they traverse nodes in the tree and read them into memory from disk. Disk IO is the single biggest time expense a database has. So to reduce the number of reads, nodes visited while fetching or writing a record are usually cached. This allows more efficient retrieval of the record next time it is requested. As more low-density keys are accessed, more and more unique nodes are fetched from disk into memory and cache. Yet every cache has its limits, bound primarily by the hardware available and often by software configuration. Once the available cache space has been used, stale/old nodes are removed from cache to make room for newer ones.

So now let us imagine how this applies when using a auto-numbered field. To insert the next new row I’ll need to travel down the right-edge (highest key values) of the tree. Once at the leaf, insert and done (oversimplified). Since the next write uses the next possible key from the last one used, it is practically guaranteed to find the nodes it needs in cache. So a few quick memory look-ups later the record can be inserted without reading from disk. It should now be obvious why Guids will have problems…

Creating a new Guid is essentially done by taking a value ‘uniformly at random’ from the entire range of possible Guid values. That means that unlike our auto-number field with a high key-density, our Guid keys are designed to be sparse, or to have a low key-density. Because of this for two Guid values to be stored in the same tree node is likely going to be statistically more improbable than winning the lottery. Using a Guid as a primary key practically obliterates the ability for a database to reliably find nodes in the cache based upon previous queries. By the time the database has passed about 10 million rows your performance will fall drastically.

Want more proof? Read the Guid article on Wikipedia under the section “Sequential algorithms” it discusses this very topic. It also discusses solutions to this, as first introduced by Jimmy Nilsson in 2002, called a COMB Guid or Combined Guid for the combination of a timestamp.

So are Guid’s Evil in a Database? No. It’s the algorithm that generates the Guid that is the issue, not the Guid itself. As mentioned in the articles linked above, there are other algorithms. There are numerous possibilities documented online. I’ve implemented one of these that out-performs the native Guid.NewGuid() implementation that will be released in the next few weeks. Until then, this is fairly similar to the algorithm I’m using…


static class SequentialGuidGenerator
{
    static int _sequenced = (int)DateTime.UtcNow.Ticks;

    private static readonly System.Security.Cryptography.RNGCryptoServiceProvider _random =
        new System.Security.Cryptography.RNGCryptoServiceProvider();
    private static readonly byte[] _buffer = new byte[6];

    public static Guid NewGuid()
    {
        long ticks = DateTime.UtcNow.Ticks;
        int sequenceNum = System.Threading.Interlocked.Increment(ref _sequenced);
        lock (_buffer)
        {
            _random.GetBytes(_buffer);
            return new Guid(
                (int) (ticks >> 32), (short) (ticks >> 16), (short) ticks,
                (byte) (sequenceNum >> 8), (byte) sequenceNum,
                _buffer[0], _buffer[1], _buffer[2], _buffer[3], _buffer[4], _buffer[5]
                );
        }
    }
}

The problem with this code is that not all databases compare Guids the same way, or in the same format. So you should be cautious about using this approach until you understand your database and how it stores and compares a Guid type.

Lessons Learned and Applied Concept

The interesting and rather undocumented aspect about this issue is that it applies just as well across all types of composite keys. Let’s take an example, we have a simple logging structure we are writing to with NLog in a database. The rows are identified by a Guid, but we almost never query these records by Id. Most of the time when we query this data we are looking within a range of dates for a specific event. How would you model the primary key and indexes? Well most people want to use as small of a primary key as possible and so the natural assumption is to use the ID of the record. This, as we’ve already covered, is generally a bad idea just because we are using Guids, but even more because our queries will be time based. By promoting the timestamp into the primary key we not only gain better query performance, but we also remove the problem of the GUID identifier. Let’s see the example:

TABLE LogFile {
    Column DateTime timestamp,
    Column GUID id,
    Column int eventType,
    Column string message,
    Primary Key ( timestamp, id )
}

With the primary key using the timestamp as it’s first comparison we will always be writing to the same area within the table and will consistently hit the cache for writes. When seeking for data the timestamp will group all the records needed together so that the data we are after is stored as dense as is possible requiring the fewest possible reads.

Now let’s drift this example a little to a new scenario. Let’s say the log above is being written from an ASP.NET application in which all users are authenticated. We want to add this user identity to the LogFile data being written, and we want to constrain queries to be associated with a user. In the example above it may be safe to simply modify the Primary Key ( timestamp, id ), to include the user as first key. Thus the Primary Key ( userId, timestamp, id ) will now perform well for a single user right? Well the answer Yes and No. It really depends greatly on the application. Introducing userId as the primary key means that we could be writing to as many places in the file as we have users. If the application is a mobile app polling our web server every minute, then we’ve just scattered our writes across all N thousands of users in our system. Yet if our application requires a human being to use a web browser or mobile app, the number of active writing points in the file drops considerably… Well at least until your Facebook and at that point you cash out and go home :)

One last example. Given you are building SkyDrive, or GDrive, or whatever you want to store the following entities: Customer, Drive, Folder, File. Each entity is identified by a GUID. What does the File’s primary key look like? Well I’d probably key the File by (CustomerID, DriveID, FolderID, Timestamp, FileID). You would obviously need an ancillary index by FileID in order to access the file directly. Food for thought anyway…

The reason I bring all this up is that there is no rule of thumb for a good primary key. Each application will have different needs and different requirements. Want you should take away is that the density of keys being written to in that first field of your primary key will ultimately dictate your write throughput and likely your scalability. Be conscious of this, and choose keys wisely. The Guid ID of a record is not always the best answer for a primary key.

As a side-note, using Guid’s as a primary key in the B+Tree will work but much more slowly at large volumes (2+ million). Using a sequential guid generator like the one above, or using an ordered natural key (like a qualified file name) will serve you much better. Ordered (or near-ordered) keys will provide linear scalability whereas unique random GUIDs will start to suffer once you’ve exceeded the cache space.

 
 

Release Notes: NOTES: Major version increment primarily due to extensive changes in BPlusTree’s capabilities and storage format. The next release will flag the v1 Options class as Obsolete to ensure people are using the latest version. All new code should be using ‘OptionsV2′ when constructing a BPlusTree. Additions in this release: Added BPlusTree.OptionsV2 to provide [...]

 

Continued from: BPlusTree 2.0 Changes Part 4 – Rewriting the Storage Format Getting Started To utilize the new file format in the BPlusTree you will need to use OptionsV2 class. The previous Options class is still there and continues to use the same file format. // Create the OptionsV2 class to specify construction arguments: var [...]

 

Continued from: BPlusTree 2.0 Changes Part 3 – AddRange and BulkInsert So all the previous updates took place back in April of this year. As I started to prepare to release a new drop of the BPlusTree I started having thoughts about an alternative storage format. So the update got shelved and I started working [...]

 
WCF replacement for cross process/machine communication

I ran across another post of someone looking to get rid of WCF on StackOverflow today. The post titled “WCF replacement for cross process/machine communication” goes into the typical complaints about configuration of WCF. I actually think this is the least of the issues I’ve had with WCF. Whatever your reason for looking to abandon [...]