Mike Boyles Thoughts On New Shared Dictionary Features

Shared Dictionary Features

This document describes features that I would like to see in the next generation of GroupLab.Networking Shared Dictionary library.

UDP and HTTP transport protocols'''

The entire architecture should be based on the assumption that an unreliable connectionless transport protocol is used. Optional reliability will be implemented atop the transport protocol with acknowledgements. Because a connectionless transport protocol is assumed – even though HTTP uses TCP which is connection-oriented – the messaging layer must indicate session start/end while timeouts during which no messages are received are used to indicate a session is lost. With HTTP, outgoing packets need to be queued between periodic connections. Fixed-length packets (e.g., 512+1 bytes) will be assumed and a fixed upper bound packet rate (e.g., 60 packets/second) will be used. When using HTTP as the transport protocol, a single HTTP POST can transmit multiple packets at once. A packet can hold all or part of multiple messages.

Abandon current implementation of vectors, maps, and metadata

Use a two-tier Dictionary – DictionaryElement object model. Metadata should be implemented as properties on DictionaryElement. DictionaryElements should support being 'unnamed' and allow numeric indexing to implement vectors. They should also support linking entire DictionaryElements into the tree to implement maps.

 Dictionary d = new Dictionary();
 d.Open("udp://localhost:test?uid=user@host&pwd=xxx");
 // Map-like interface
 DictionaryElement ui = new DictionaryElement();
 ui["name"].Value = "Michael Boyle";
 ui["email"].Value = "boylem@cpsc.ucalgary.ca";
 ui["id"].Value = id;
 // Metadata as properties
 ui.PersistencePolicy = PersistencePolicy.RemoveWhenUserDisconnects;
 ui.PersistencePolicyData = d.UserId;
 // Link entire tree in at once
 d["/users/" + id.ToString()].Value = ui; // equivalent to d["/users"][id.ToString()].Value
 // Vector-like access
 for(int i = 0; i < d["/users"].Children.Count; i++)
 {
    Console.WriteLine(d["/users"][i]["name"].Value + " is online");
 }

Metadata corresponding to transport layer behaviours as well as dictionary layer behaviours

At the transport layer, a single shared dictionary connection consists of one or more streams. An ordered sequence of messages are sent along each stream. One stream corresponds to one key or group of keys in which updates must be strictly ordered. By default, all keys are in the same stream, but the end programmer can configure messaging properties on the keys to pull them out into their own streams.

Each stream has a few configurable properties:

  • acknowledgement – recipient sends back a message confirming acknowledgement of a packet : this is used to implement guaranteed reliability : default should be acknowledgement is required
  • economisation – if a message is queued to be sent while another message in the same stream is still waiting to be sent, the waiting message is discarded : reduces bandwidth consumption when lots of changes are being sent : default should be economisation is off
  • priority – three priority class : normal, time-sensitive, and bulk file transfer : optionally, a fine-grained priority levels within each class; default should be the 'normal' class.

At the dictionary layer, the economisation and acknowledgement properties could be combined into an 'update' policy: every-update-guaranteed -or- most-recent-update-guaranteed: the most-recent-update-required policy only occasionally retries when no acknowledgement received.

Three more policies exist at the dictionary layer:

  • caching – cache-in-RAM, cache-to-disk, no-cache : control how values are stored : default is cache-in-RAM; no-cache useful for audio streams, implementing RPCs; cache-to-disk useful for bulk file transfer scenarios
  • persistence – keep-indefinitely, remove-after-timeout, remove-when-session-disconnects, remove-when-user-disconnects, reference-counted : default is keep-indefinitely
  • encryption – true or false : default false

As an example, imagine a shared voice, video, and telepointer system. Audio is uncompressed. Video uses iframe/pframe compression. (What's that? Well, in video compression strategies, iframes (keyframes) store a representation of an entire video frame while pframes store only the delta between the current frame and the previous iframe.)

 Dictionary d = new Dictionary();
 d.Open("udp://localhost:test?uid=user@host&pwd=xxx");
 DictionaryEntry mystreams = new DictionaryEntry();
 mystreams.PersistencePolicy = PersistencePolicy.RemoveWhenSessionEnds;
 mystreams.PersistencePolicyData = d.SessionId;
 mystreams["audio"].UpdatePolicy = UpdatePolicy.MostRecentUpdateGuaranteed;
 mystreams["audio"].PriorityPolicy = PriorityPolicy.TimeSensitive;
 mystreams["audio"].CachePolicy = CachePolicy.NoCache;
 mystreams["video/iframe"].UpdatePolicy = UpdatePolicy.EveryUpdateGuaranteed;
 mystreams["video/iframe"].PriorityPolicy = PriorityPolicy.Normal;
 mystreams["video/iframe"].CachePolicy = CachePolicy.MemoryCache;
 mystreams["video/pframe"].UpdatePolicy = UpdatePolicy.MostRecentUpdateGuaranteed;
 mystreams["video/pframe"].PriorityPolicy = PriorityPolicy.TimeSensitive;
 mystreams["video/pframe"].CachePolicy = CachePolicy.NoCache;
 mystreams["telepointer"].UpdatePolicy = UpdatePolicy.MostRecentUpdateGuaranteed;
 mystreams["telepointer"].PriorityPolicy = PriorityPolicy.TimeSensitive;
 mystreams["telepointer"].CachePolicy = CachePolicy.MemoryCache;
 d["/streams"][d.SessionId] = mystreams;

Cross-platform implementation should be possible

Custom marshaller The current GroupLab.Networking implementation uses the .NET binary serializer for all objects, making cross-platform implementation impossible. I would like to see a custom marshaller be implemented for common types: null, byte, bool, char, short, int, long, float, double, DateTime, Point/F, Size/F, RectangleF, string (utf8), Guid, ArrayList/List<T>, Hashtable, plus one-dimensional arrays of these types. All other types should use a platform specific marshaller: standard .NET marshaller for CLR objects, standard Java marshaller for Java objects, and IPersistStream for COM objects. All classes used to transmit messages should consist of marshallable types.

AES encryption at the messaging layer Dictionaries may be password protected and the password can be used to generate an AES encryption key to be used at the packet layer. A packet is encrypted only if any message contained in it requires encryption. AES is to be used to ease implementation in other languages, platforms.

Users and sessions as first-rate concepts Connections are associated with a user identity as well as a session identity, with multiple sessions per user. User and session metadata is stored directly in the dictionary, e.g.,

 /users/boylem@cpsc.ucalgary.ca
 /users/boylem@cpsc.ucalgary.ca/sessions/0 := <<guid1>>
 /users/boylem@cpsc.ucalgary.ca/sessions/1 := <<guid2>>
 /users/saul@cpsc.ucalgary.ca
 /users/saul@cpsc.ucalgary.ca/sessions/0 := <<guid3>>
 /sessions/guid1 := boylem@cpsc.ucalgary.ca
 /sessions/guid2 := boylem@cpsc.ucalgary.ca
 /sessions/guid3 := saul@cpsc.ucalgary.ca

Mutual exclusion, test-and-set, retain/release, synchronisation A number of critical features are needed to arbitrate concurrent access to the dictionary. These can be implemented on the DictionaryElement class itself:

 class DictionaryElement
 {
  public DictionaryElement this[string key] {get;set;}
  public DictionaryElement this[int index] {get;set;}
  public DictionaryElement();
  public Dictionary {get;}
  public string Name {get;set;}
  public object Value {get;set;}
  public int Index {get;}
  public DictionaryElement Parent;
  public DictionaryElement FirstChild;
  public DictionaryElement LastChild;
  public DictionaryElement NextSibling;
  public DictionaryElement PrevSibling;
  public DictionaryElementCollection Children;
  public DictionaryElementCollection Siblings;
  public DictionaryElementCollection Ancestors;
  public PriorityPolicy PriorityPolicy {get;set;}
  public PersistencyPolicy PersistencePolicy {get;set;}
  public object PersistencePolicyData {get;set;}
  public CachePolicy CachePolicy {get;set;}
  public UpdatePolicy UpdatePolicy {get;set;}
  public bool Subscribed {get;}

  public bool Lock(double timeout, double duration);
  public IAsyncResult BeginLock(double timeout, double duration, AsyncCallback callback, object state);
  public bool EndLock(IAsyncResult result);
  public void Unlock();
  public void TestSet(string name, object compareTo, bool setIfEqual, object setTo);
  public void TestSet(DictionaryEntry child, object compareTo, bool setIfEqual);
  public void Retain();
  public void Release();
  public void Touch();
  public void Sync();
 }

 class Dictionary
 {
  public Dictionary();
  public bool Open(string url);
  public IAsyncResult BeginOpen(string url, AsyncCallback callback, object state);
  public bool EndOpen(IAsyncResult result);
  public void Close();
  public DictionaryElement this[string key] {get;set;}
  public DictionaryElement RootElement {get;}
  public string SessionId {get;}
  public string UserId {get;}
 }