posts - 19 , comments - 8 , trackbacks - 0

Persistent Dictionary

This blog describes the implementation of a persistent dictionary. There are a number of excellent solutions to this online, but most were highly complex. This is a simple implementation which was sufficient for my purpose. It uses the classes described in theĀ Heap blog.

The Cache

First we defined the interface for the persistent cache. This follows the traditional CRUD pattern.

using System;
using JetBlack.Patterns.Heaps;

namespace JetBlack.Patterns.Caching
{
    public interface ICache<T> : IDisposable
    {
        Handle Create(T value);
        T Read(Handle handle);
        Handle Update(Handle handle, T value);
        void Delete(Handle handle);
    }
}

A Cache Implementation

Now we can implement a fairly straightforward cache, without making too many decisions about how it will be used. All we need to provide is a heap, a serializer, and a deserializer.

The Update method has some complexity. If the size of the object has changed it will need to deallocate the old block and allocate a new one.

using System;
using JetBlack.Patterns.Heaps;

namespace JetBlack.Patterns.Caching
{
    public class SerializingCache<TItem, TRaw> : ICache<TItem>
    {
        private readonly IHeap<TRaw> _heap;
        private readonly Func<TItem, TRaw[]> _serialize;
        private readonly Func<TRaw[], TItem> _deserialize;

        public SerializingCache(IHeap<TRaw> heap, Func<TItem, TRaw[]> serialize, Func<TRaw[],TItem> deserialize)
        {
            _heap = heap;
            _serialize = serialize;
            _deserialize = deserialize;
        }

        public Handle Create(TItem value)
        {
            var raw = _serialize(value);
            var handle = _heap.Allocate(raw.Length);
            _heap.Write(handle, raw);
            return handle;
        }

        public TItem Read(Handle handle)
        {
            var raw = _heap.Read(handle);
            return _deserialize(raw);
        }

        public Handle Update(Handle handle, TItem value)
        {
            var raw = _serialize(value);
            var block = _heap.GetAllocatedBlock(handle);

            if (block.Length != raw.Length)
            {
                _heap.Free(handle);
                handle = _heap.Allocate(raw.Length);
            }

            _heap.Write(handle, raw);

            return handle;
        }

        public void Delete(Handle handle)
        {
            _heap.Free(handle);
        }

        public void Dispose()
        {
            _heap.Dispose();
        }
    }
}

An Example String Cache

A trivial implementation of the serializers could be the following.

using System.Text;
using JetBlack.Patterns.Heaps;

namespace JetBlack.Patterns.Caching
{
    public class StringCache : SerializingCache<string,byte>
    {
        public StringCache(IHeap<byte> heap, Encoding encoding)
            : base(heap, encoding.GetBytes, encoding.GetString)
        {
        }

        public StringCache(IHeap<byte> heap)
            : this(heap, Encoding.Default)
        {           
        }
    }
}

A Persistant Dictionary

All we need to do to create a persistent dictionary is to wrap a cache with a dictionary implementation. We keep and index of keys to handles to map to the persistent cache.

The factory class at the top generates the dictionary with binary serializers so we can support a large population of possible objects.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using JetBlack.Core.Collections.Generic;
using JetBlack.Patterns.Heaps;
using System.IO;
using System.Runtime.Serialization.Formatters.Binary;

namespace JetBlack.Patterns.Caching
{
    public static class PersistentDictionary
    {
        public static readonly BinaryFormatter BinaryFormatter = new BinaryFormatter();

        public static PersistantDictionary<TKey, TValue> Create<TKey,TValue>()
        {
            return Create<TKey,TValue>(new FileStreamHeap(() => new FileStream(Path.GetTempFileName(), FileMode.Open), new LightweightHeapManager()));
        }

        public static PersistantDictionary<TKey,TValue> Create<TKey,TValue>(IHeap<byte> heap)
        {
            return new PersistantDictionary<TKey,TValue>(new SerializingCache<TValue,byte>(heap, Serialize, Deserialize<TValue>));
        }

        public static byte[] Serialize<TValue>(TValue value)
        {
            using (var stream = new MemoryStream())
            {
                BinaryFormatter.Serialize(stream, value);
                stream.Flush();
                return stream.GetBuffer();
            }
        }

        public static TValue Deserialize<TValue>(byte[] bytes)
        {
            using (var stream = new MemoryStream())
            {
                return (TValue)BinaryFormatter.Deserialize(stream);
            }
        }

    }

    public class PersistantDictionary<TKey, TValue> : IDictionary<TKey, TValue>, IDisposable
    {
        private readonly ICache<TValue> _cache;
        private readonly IDictionary<TKey, Handle> _index = new Dictionary<TKey, Handle>();

        public PersistantDictionary(ICache<TValue> cache)
        {
            _cache = cache;
        }

        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            using (var indexEnumerator = _index.GetEnumerator())
            {
                while (indexEnumerator.MoveNext())
                    yield return KeyValuePair.Create(indexEnumerator.Current.Key, _cache.Read(indexEnumerator.Current.Value));
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        public void Add(KeyValuePair<TKey,TValue> item)
        {
            Add(item.Key, item.Value);
        }

        public void Clear()
        {
            foreach (var handle in _index.Values)
                _cache.Delete(handle);
            _index.Clear();
        }

        public bool Contains(KeyValuePair<TKey, TValue> item)
        {
            return ContainsKey(item.Key);
        }

        public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
        {
            foreach (var item in _index)
                array[arrayIndex++] = KeyValuePair.Create(item.Key, _cache.Read(item.Value));
        }

        public bool Remove(KeyValuePair<TKey, TValue> item)
        {
            return Remove(item.Key);
        }

        public int Count
        {
            get { return _index.Count; }
        }

        public bool IsReadOnly
        {
            get { return false; }
        }

        public bool ContainsKey(TKey key)
        {
            return _index.ContainsKey(key);
        }

        public void Add(TKey key, TValue value)
        {
            var handle = _cache.Create(value);
            _index.Add(key, handle);
        }

        public bool Remove(TKey key)
        {
            Handle handle;
            if (!_index.TryGetValue(key, out handle))
                return false;
            _cache.Delete(handle);
            _index.Remove(key);
            return true;
        }

        public bool TryGetValue(TKey key, out TValue value)
        {
            Handle handle;
            if (!_index.TryGetValue(key, out handle))
            {
                value = default(TValue);
                return false;
            }
            value = _cache.Read(handle);
            return true;
        }

        public TValue this[TKey key]
        {
            get { return _cache.Read(_index[key]); }
            set
            {
                Handle handle;
                _index[key] = _index.TryGetValue(key, out handle) ? _cache.Update(handle, value) : _cache.Create(value);
            }
        }

        public ICollection<TKey> Keys
        {
            get { return _index.Keys; }
        }

        public ICollection<TValue> Values
        {
            get { return _index.Values.Select(handle => _cache.Read(handle)).ToList(); }
        }

        public void Dispose()
        {
            _cache.Dispose();
        }
    }
}

Print | posted on Monday, September 1, 2014 11:13 AM | Filed Under [ C# persistent dictionary PersistentDictionary ]

Feedback

No comments posted yet.
Post A Comment
Title:
Name:
Email:
Comment:
Verification:
 

Powered by: