The Multiton Design Pattern

Introduction

Many people have independely discovered a new design pattern, the “Multiton”, which, like the “Singleton” is an initialization pattern in the style of the Design Patterns book. Like the Singleton, the Multiton provides a method that controls the construction of a class: instead of maintaining a single copy of an object in an address space, the Multiton maintains a Dictionary that maps keys to unique objects.

The Multiton pattern can be used in systems that store persistent data in a back-end store, such as a relational databases. The Multiton pattern can be used to maintain a set of objects are mapped to objects (rows) in a persistent store: it applies obviously to object-relational mapping systems, and is also useful in asynchronous RIA’s, which need to keep track of user interface elements that are interested in information from the server.

An alternate use case of Mulitons, seen in the “Multicore” version of the PureMVC framework, is the extension of the Singleton pattern to support multiple instances of a system in a single address space.

As useful as the Multiton pattern is, this article explains how Multitons use references in a way that doesn’t work well with conventional garbage collection. Multitons are a great choice when the number of Multitons is small, but they may leak memory unacceptablely when more than a few thousand are created. Future posts will describe patterns, such as the Captive Multiton, that provide the same capabilities with more scalable memory management — subscribe to our RSS feed to keep informed.

Use of a Multiton in An Asynchronous Application

In our last article on Model-View Separation in Asynchronous RIA’s, we used a Singleton object that represented an entire table in a relational database. This object maintained a list of listerners that were interested in the contents of a table. In this case, the amount of information in the table was small, and often used in the aggregate, so retreiving a complete copy of the table was a reasonable level of granularity. We could imagine a situation, however, where the number of records and size of the records is enough that we need to transfer records individually. (This specific case is an outline of an implementation for Silverlight: a GWT implementation would be similar — details specific to GWT are talked about in a previous post.)

Imagine, for instance, a BlogPosting object, which represents a post in a blog, which in turn has an integer primary key. The BlogPosting object is a multiton, so you’d write

[01] var posting=BlogPosting.GetInstance(postId);

to get the instance of BlogPosting that corresponds to postId. Client objects can’t really write something like

[02] TitleField.Text=posting.Title

because the operation of retrieving text from an the server is asynchronous, and won’t return in time to return a value, either on line [01] or [02]. More reasonably, a BlogPostingViewer can register itself against a BlogPosting instance so it will be notified when information is available about the blog posting.

[03] public class BlogPostingViewer: UserControl,IBlogPostingListener {
[04]     protected int PostId;
[05]
[06]     public BlogPostViewer(int postId) {
[07]        PostId=postId;
[08]        BlogPosting.GetInstance(postId).AddListener(this);
[09]     }
[10]
[11]     public void Dispose() {
[12]        BlogPosting.GetInstance(postId).RemoveListener(this);
[13]        super.Dispose();
[14]     }

This example shows a pattern usable in a Silverlight applicaton, unlike the GWT style in the model-view article. The Dispose() method will need to be called manually when the BlogPostingViewer is no longer needed, since it will never be garbage collected so long as a reference to it inside the BlogPosting exists. (This points to a general risk of memory leaks with Multitons that we’ll talk about later.) This problem can be addre

The BlogPostingViewer goes on to implement the IBlogPostingListener interface, updating the visual appearance of the user interface to reflect information from the UI:

[15]     public void UpdatePosting(BlogPostingData d) {
[16]         if (d==null) {
[17]            ClearUserInterface();   // user-defined method blanks out UI
[18]            return
[19]         }
[20]         TitleField.Text=d.Title;
[21]         ...
[22]     }
}

We assume that BlogPostingData represents the state of the BlogPosting at a moment in time, distinct from the BlogPosting, which represents the BlogPosting as a persistent object. BlogPostingData might (roughly) correspond to the the columns of a relational table and look something like:

[23] public class BlogPostingData {
[24]    public string Title { get; set;}
[25]    public Contributor Author { get; set; }
[26]    public string Body { get; set;}
[27]    public Category[] AssociatedCategories { get; set;}
[28]    ...
[29] }

We could then add a BlogPostingViewer to the user interface and schedule it’s initialization by writing

[30] var viewer=new BlogPostingViewer(PostId);
[31] OuterControl.Children.Add(viewer);
[32] BlogPosting.GetInstance(PostId).Fetch();

Note that line [32] tells the BlogPosting instance to retreive a copy of the posting from the server (an instance of BlogPostingData) and call UpdatePosting() on all of the listeners. Therefore, there will be a time between line [30] and the time when the async call started on line [32] gets back when the BlogPostingViewer is empty (not initialized with BlogPostingData.) Therfore, the BlogPostingViewer must be designed so that nothing bad happens when it’s in that state: it has to show something reasonable to user and not crash the app if the user clicks a button that isn’t ready yet.

(In a more developed application, the BlogPosting could keep a cache of the latest BlogPostingData: this could improve responsiveness by updating the BlogPostingViewer at the moment it registers, or by doing a timestamp or checksum stamp against the server to reduce the bandwidth requirements of a Fetch(), just watch out for the unintended consequences of multiple code paths.)

Implementing a Muliton

Here’s an implementation of a Multiton in C# that’s not too different from the Java implementation from Wikipedia.

class BlogPosting {
    #region Initialization
    private static readonly Dictionary<int,BlogPosting> _Instances =
       new Dictionary<int,BlogPosting>();

    private BlogPosting(int key) {
        ... construct the object ...
    }

    public static BlogPosting GetInstance(int key) {
        lock(_Instances) {
            BlogPosting instance;
            if (_Instances.TryGetValue(key,out instance)) {
                return instance;
            }

            instance = new BlogPosting(key);
            _Instances.Add(key, instance);
            return instance;
        }
    }
    #endregion

    ... the rest of the class ...

}

I’m pretty sure that a version of this could be created in C# with slightly sweeter syntax that would look like

BlogPosting.Instance[postId]

but this doesn’t address the weak implementation of static inheritence in many popular languages that requires us to cut-and-paste roughly 20 lines of code for each Multiton class, rather than being able to reuse inheritence logic. The Ruby Applications Library, on the other hand, contains a Multiton class that can be used to bolt Multiton behavior onto a class. It would be interesting to see what could be accomplished with PHP 5.3′s late static binding.

Multitons And Memory Leaks

Multitons, unfortunately, don’t interact well with garbage collectors. Once a Multiton is created, the static _Instances array will maintain a reference to every Multiton in the system, so that Multitons won’t be collected, even if no active references exist.

You might think you could manually remove Multitons from the _Instances list, but this won’t be entirely reliable. In the case above, each BlogPosting maintains a list of IBlogPostingListeners. You could, in principle, scavenge BlogPostings with an empty set of listerners, but that doesn’t stop a class from squirreling away a copy of a BlogPosting that will later conflict with a new BlogPosting that somebody creates by using BlogPosting.GetInstance().

WeakReferences, as available in dot-Net and the full Java platform (as opposed to GWT), are not an answer to this problem, because references work backwards in this case: a BlogPosting is collectable if (i) no references to the BlogPosting exist outside the _Instances array, and (ii) a BlogPosting doesn’t hold references to other objects that may need to be updated in the future.

The severity of this issue depends on the number of Multitons created and the size of the Mulitons. If the granularity of Multitons is coarse, and you’ll only create five of them, there’s no problem. 1000 Multitons that each consume 1 kilobyte will consume about a megabyte of RAM, which is inconsequential for most applications these days. However, this amounts to a scaling issue: an application that works fine when it creates 50 Mulitons could break down when it creates 50,000.

One answer to this problem is to restrict access to Muliton so that: (i) references to Multitons can’t be saved by arbitrary objects and (ii) manages Multitons with a kind of reversed reference count, so that Multitons are discared when they no longer hold useful informaton. I call this a Captive Multiton, and this will be the subject of our next exciting episode: subscribe to our RSS feed so you won’t miss it.

More Information About Multitons

So far as I can tell, Multitons have been independently discovered by many developers in recent years. I used Multitons (I called them “Parameterized Singleons”) in the manner above in a GWT application that I developed in summer 2007. The PureMVC Framework uses Multitons to allow multiple instances of the framework to exist in an address space. A reusable Multiton implementation exists in Ruby.

Conclusion

The Muliton Pattern is an initialization pattern in the sense defined in the notorious “Design Patterns” Book. Mulitons are like Singletons in that they use static methods to control access to a private constructor, but instead of maintaining a single copy of an object in an address space, a Multiton maintains a mapping from key values to objects. A number of uses are emerging for mulitons: (i) Multitons are useful when we want to use something like the Singleton pattern, but support multiple named instances of a system in an an address space and (ii) Multitons can be a useful representation of an object in a persistent store, such as a relational database. Multitons, however, are not collected properly by conventional garbage collectors: this is harmless for applications that create a small number of mulitons, but poses a scaling problem when Multitons are used to represent a large number of objects of fine granularity — a future posting will introduce a Captive Multiton that solves this problem: subscribe to our RSS feed to follow this developing story.