Storing, Loading, and Updating a Trie in ASP.NET MVC 3

I have a trie-based word detection algorithm for a custom dictionary. Note that regular expressions are too brittle with this dictionary as entries may contain spaces, periods, etc.

I've implemented the algorithm in a local C# app that reads in the dictionary from file and stores the trie in memory (it's compact, so no RAM size issues at all). Now I would like to use this algorithm in an MVC 3 app on a cloud host like AppHarbor, with the added twist that I want a web interface to enable adding/editing words.

It's fast enough that loading the dictionary from file and building the trie every time a user uploads their text would not be an issue (< 1s on my laptop). However, if I want to enable a开发者_高级运维dmins to edit the dictionary via the web interface, that would seem tricky since the dictionary would potentially be getting updated while a user is trying to upload text for analysis.

What is the best strategy for storing, loading, and updating the trie in an MVC 3 app?

---

I'm not sure if you are looking for specific implementation details, or more conceptual ideas about how to handle but I'll throw some ideas out there for now.

Actual Trie Classes - Here is a good C# example of classes for setting up a Trie. It sounds like you already have this part figured out.

Storing: I would persist the trie data to XML unless you are already using a database and have some need to have it in a dbms. The XML will be simple to work with in the MVC application and you don't need to worry about database connectivity issues, or the added cost of a database. I would also have two versions of the trie data on the server, a production copy and a production support copy, the second for which your admin can perform transactions against.

Loading In your admin module of the application, you may implement a feature for loading the trie data into memory, the frequency of data loading depends on your application needs. It could be scheduled or available as a manual function. Like in wordpress sites, if a user should access it while updating they would receive a message that the site is undergoing maintenance. You may choose to load into memory on demand only, and keep the trie loaded at all times except for if problems occurred.

Updating - I'd have a second database (or XML file) that is used for applying updates. The method of applying updates to production would depend partially on the frequency, quantity, and time of updates. One safe method might be to store transactions entered by the admin. For example:

• trie.put("John", 112);
• trie.put("Doe", 222);
• trie.Remove("John");

Then apply these transactions to your production data as needed via an admin function. If needed put your site into "maint" mode. If the updates are few and fast you may be able to code the site so that it will hold all work until transactions are processed, a user might have to wait a few milliseconds longer for a result but you wouldn't have to worry about mutating data issues.

This is pretty vague but just throwing some ideas out there... if you provide comments I'll try to give more.

---

1 Store trie in cache: It is not dynamic data, and caching helps us in other tasks (like concurrency access to trie by admin and user)

2 Make access to cache clear:

:

public class TrieHelper
{
public Trie MyTrie
{
    get
    {
        if (HttpContext.Current.Cache["myTrieKey"] == null)
            HttpContext.Current.Cache["myTrieKey"] = LoadTrieFromFile(); //Returns Trie object
        return (Trie)HttpContext.Current.Cache["myTrieKey"];
    }
}

3 Lock trie object while adding operation in progress

public void AddWordToTrie(string word)
{
    var trie = MyTrie;
    lock (HttpContext.Current.Cache["myTrieKey"])
    {
    trie.AddWord(word);
    } // notify that trie object locking when write data to file is not reuired
    WriteNewWordToTrieFile(word); // should lock FileWriter object
    }
}

4 If editing is performs by 1 admin at a time - store trie in xml file - it will be easy to implement logic of search element, after what word your word should be added (you can create function, that will use MyTrie object in memory), and add it, using linq to xml.

---

I've got a kind'a the same but 10 times bigger :)

The client design it's own calendar with questions ans possible answer in the meanwhile some is online and being used by the normal user.

What I come up was something as test and deploy. The Admin enters the calendar values and set it up correctly and after he can use a Preview button to see if it's like he needs/wants, then, to make the changes valid to all end users, he need to push Deploy.

He, as an ADMIN, will know that, until he pushes the DEPLOY button, all users accessing the Calendar will have the old values. Soon he hits deploy all is set in the Database, and pushed the files he uploaded into Amazon S3 (for faster access).

I update the Cache with the new calendar and the new Calendar object is cached until the App pool says otherwise or he hit the Deploy button again.

You could do something like this.

---

As you are going to perform your application in the cloud environment, I'd suggest you to take a look at CQRS and durable messaging and provide some concurrency model (possibly, optimistic concurrency and intelligent conflict detection http://skillsmatter.com/podcast/design-architecture/cqrs-not-just-for-server-systems 5:00)

Also, obviously, you need to analyze your business requirements more precisely because, as Udi Dahan mentioned, race conditions are result of the lack of business analysis.