Looking for a simple standalone persistent dictionary implementation in C#

Question

For an open source project I am looking for a good, simple implementation of a Dictionary that is backed by a file. Meaning, if an application crashes or restarts the dictionary will keep its state. I would like it to update the underlying file every time the dictionary is touched. (Add a value or remove a value). A FileWatcher is not required but it could be useful.

class PersistentDictionary<T,V> : IDictionary<T,V>
{
    public PersistentDictionary(string filename)
    {

    } 
}

Requirements:

• Open Source, with no dependency on native code (no sqlite)
• Ideally a very short and simple implementation
• When setting or clearing a value it should not re-write the entire underlying file, instead it should seek to the position in the file and update the value.

Similar Questions

• Persistent Binary Tree / Hash table in .Net
• Disk backed dictionary/cache for c#

Answer 1

Sounds cool, but how will you get around changes to the stored value (if it was a reference type) itself? If its immutable then all is well but if not you're kinda stuffed :-)

If you're not dealing with immutable values, I would suspect a better approach would be to handle persistence at the value level and to just rebuild the dictionary as necessary.

(edited to add a clarification)

Answer 2

Just use serialization. Look at the BinaryFormatter class.

Answer 3

I don't know of anything to solve your problem. It will need to be a fixed size structure, so that you can meet the requirements of being able to rewrite records without rewriting the entire file.

This means normal strings are out.

Answer 4

Like Douglas said, you need to know the fixed size of your types (both T and V). Also, variable-length instances in the object grid referenced by any of those instances are out.

Still, implementing a dictionary backed by a file is quite simple and you can use the BinaryWriter class to write the types to disk, after inheriting or encapsulating the Dictionary<TKey, TValue> class.

Answer 5

• The C5 Generic Collection Library

  C5 provides functionality and data structures not provided by the standard .Net System.Collections.Generic namespace, such as persistent tree data structures, heap based priority queues, hash indexed array lists and linked lists, and events on collection changes.

• bplustreedotnet

  The bplusdotnet package is a library of cross compatible data structure implementations in C#, java, and Python which are useful for applications which need to store and retrieve persistent information. The bplusdotnet data structures make it easy to store string keys associated with values permanently.

• ESENT Managed Interface

  Not 100% managed code but it's worth mentioning it as unmanaged library itself is already part of every windows XP/2003/Vista/7 box

  ESENT is an embeddable database storage engine (ISAM) which is part of Windows. It provides reliable, transacted, concurrent, high-performance data storage with row-level locking, write-ahead logging and snapshot isolation. This is a managed wrapper for the ESENT Win32 API.

Answer 6

one way is to use the Extensible Storage Engine built into windoows to store your stuff. It's a native win database that supports indexing, transactions etc...

Answer 7

Consider a memory mapped file. I'm not sure if there is direct support in .NET, but you could pinvoke the Win32 calls.

Answer 8

I haven't actually used it, but this project apparently provides an mmap()-like implementation in C#

Mmap

Answer 9

I am not much of a programmer, but wouldn't creating a really simple XML format to store your data do the trick?

<dico> 
   <dicEntry index="x">
     <key>MyKey</key>
     <val type="string">My val</val>
   </dicEntry>
   ...
</dico>

From there, you load the XML file DOM and fill up your dictionary as you like,

XmlDocument xdocDico = new XmlDocument();
string sXMLfile;
public loadDico(string sXMLfile, [other args...])
{
   xdocDico.load(sXMLfile);
   // Gather whatever you need and load it into your dico
}
public flushDicInXML(string sXMLfile, dictionary dicWhatever)
{
   // Dump the dic in the XML doc & save
}
public updateXMLDOM(index, key, value)
{
   // Update a specific value of the XML DOM based on index or key
}

Then whenever you want, you can update the DOM and save it on disk.

xdocDico.save(sXMLfile);

If you can afford to keep the DOM in memory performance-wise, it's pretty easy to deal with. Depending on your requirements, you may not even need the dictionary at all.

Answer 10

Let me analyze this:

1. Retrieve information by key
2. Persistant storage
3. Do not want to write back the whole file when 1 value changes
4. Should survive crashes

I think you want a database.

Edit: I think you are searching for the wrong thing. Search for a database that fits your requirements. And change some of your requirements, because I think it will be difficult to meet them all.

Answer 11

I found this link and sound like what you are looking for. It is programmed in Java but it shouldn't be that hard to port it to C#:

http://www.javaworld.com/javaworld/jw-01-1999/jw-01-step.html

Answer 12

I think your issue is likely to be that last point:

When setting or clearing a value it should not re-write the entire underlying file, instead it should seek to the position in the file and update the value.

This is exactly what a DB does - you're basically describing a simple file based table structure.

We can illustrate the problem by looking at strings.

Strings in memory are flexible things - you don't need to know the length of a string in C# when you declare its type.

In data storage strings and everything else are fixed sizes. Your saved dictionary on disk is just a collection of bytes, in order.

If you replace a value in the middle it either has to be exactly the same size or you will have to rewrite every byte that comes after it.

This is why most databases restrict text and blob fields to fixed sizes. New features like varchar(max)/varbinary(max) in Sql 2005+ are actually clever simplifications to the row only actually storing a pointer to the real data.

You can't use the fixed sizes with your example because it's generic - you don't know what type you're going to be storing so you can't pad the values out to a maximum size.

You could do:

class PersistantDictionary<T,V> : Dictionary<T,V>
    where V:struct

...as value types don't vary in storage size, although you would have to be careful with your implementation to save the right amount of storage for each type.

However your model wouldn't be very performant - if you look at how SQL server and Oracle deal with table changes they don't change the values like this. Instead they flag the old record as a ghost, and add a new record with the new value. Old ghosted records are cleaned up later when the DB is less busy.

I think you're trying to reinvent the wheel:

• If you're dealing with large amounts of data then you really need to check out using a full-blown DB. MySql or SqlLite are both good, but you're not going to find a good, simple, open-source and lite implementation.

• If you aren't dealing with loads of data then I'd go for whole file serialisation, and there are already plenty of good suggestions here on how to do that.

Answer 13

I'd recommend SQL Server Express or other database.

• It's free.
• It integrates very well with C#, including LINQ.
• It's faster than a homemade solution.
• It's more reliable than a homemade solution.
• It's way more powerful than a simple disk-based data structure, so it'll be easy to do more in the future.
• SQL is an industry standard, so other developers will understand your program more easily, and you'll have a skill that is useful in the future.

Answer 14

I wrote up an implementation myself based on a very similar (I think identical) requirement I had on another project a while ago. When I did it, one thing I realised was that most of the time you'll be doing writes, you only do a read rarely when the program crashes or when it's closed. So the idea is to make the writes as fast as possible. What I did was make a very simple class which would just write a log of all the operations (additions and deletions) to the dictionary as things occurred. So after a while you get a lot of repeating between keys. Because of that, once the object detects a certain amount of repetition, it'll clear the log and rewrite it so each key and its value only appears once.

Unfortunately, you can't subclass Dictionary because you can't override anything in it. This is my simple implementation, I haven't tested it though I'm sorry, I thought you might want the idea though. Feel free to use it and change it as much as you like.

class PersistentDictManager {
    const int SaveAllThreshold = 1000;

    PersistentDictManager(string logpath) {
        this.LogPath = logpath;
        this.mydictionary = new Dictionary<string, string>();
        this.LoadData();
    }

    public string LogPath { get; private set; }

    public string this[string key] {
        get{ return this.mydictionary[key]; }
        set{
            string existingvalue;
            if(!this.mydictionary.TryGetValue(key, out existingvalue)) { existingvalue = null; }
            if(string.Equals(value, existingvalue)) { return; }
            this[key] = value;

            // store in log
            if(existingvalue != null) { // was an update (not a create)
                if(this.IncrementSaveAll()) { return; } // because we're going to repeat a key the log
            }
            this.LogStore(key, value);
        }
    }

    public void Remove(string key) {
        if(!this.mydictionary.Remove(key)) { return; }
        if(this.IncrementSaveAll()) { return; } // because we're going to repeat a key in the log
        this.LogDelete(key);
    }

    private void CreateWriter() {
        if(this.writer == null) {
            this.writer = new BinaryWriter(File.Open(this.LogPath, FileMode.Open)); 
        }
    }

    private bool IncrementSaveAll() {
        ++this.saveallcount;
        if(this.saveallcount >= PersistentDictManager.SaveAllThreshold) {
            this.SaveAllData();
            return true;
        }
        else { return false; }
    }

    private void LoadData() {
        try{
            using(BinaryReader reader = new BinaryReader(File.Open(LogPath, FileMode.Open))) {
                while(reader.PeekChar() != -1) {
                    string key = reader.ReadString();
                    bool isdeleted = reader.ReadBoolean();
                    if(isdeleted) { this.mydictionary.Remove(key); }
                    else {
                        string value = reader.ReadString();
                        this.mydictionary[key] = value;
                    }
                }
            }
        }
        catch(FileNotFoundException) { }
    }

    private void LogDelete(string key) {
        this.CreateWriter();
        this.writer.Write(key);
        this.writer.Write(true); // yes, key was deleted
    }

    private void LogStore(string key, string value) {
        this.CreateWriter();
        this.writer.Write(key);
        this.writer.Write(false); // no, key was not deleted
        this.writer.Write(value);
    }

    private void SaveAllData() {
        if(this.writer != null) {
            this.writer.Close();
            this.writer = null;
        }
        using(BinaryWriter writer = new BinaryWriter(File.Open(this.LogPath, FileMode.Create))) {
            foreach(KeyValuePair<string, string> kv in this.mydictionary) {
                writer.Write(kv.Key);
                writer.Write(false); // is not deleted flag
                writer.Write(kv.Value);
            }
        }
    }

    private readonly Dictionary<string, string> mydictionary;
    private int saveallcount = 0;
    private BinaryWriter writer = null;
}

Answer 15

I was working on porting EHCache to .NET. Take a look at the project

http://sourceforge.net/projects/thecache/

Persistent caching is core functionality that is already implemented. All main Unit Tests are passing. I got a bit stuck on distributed caching, but you do not need that part.

Answer 16

check this blog out: http://ayende.com/Blog/archive/2009/01/17/rhino.dht-ndash-persistent-amp-distributed-storage.aspx

looks to be exactly you are looking for.

Answer 17

http://csharp.illusionalworld.com/2009/02/persistent-dictionary.html

It does all you want.

Answer 18

http://www.codeproject.com/KB/cs/MultiMap_P_2.aspx

Answer 19

I've implemented the kind of PersistedDictionary you are looking for. The underlying storage is the ESENT database engine which is built into windows. The code is available here:

http://managedesent.codeplex.com/