Overview

Many standard collections such as HashSet<Key>, Dictionary<Key, Value> use HashCode to organize the underlying data structures. This leads into results of HashCode determining the internal element placement, and ultimately the iteration order of the container. Within a single process where HashCodes remain stable, this rarely causes issues. But in distributed computing this behavior can cause subtle bugs.

For example, imagine an algorithm that iterates through a set of players and selects the first that fulfills a certain condition. If multiple players fulfill the condition then, due to different container ordering, different clients and server nodes might select different players. Depending on further logic, this will easily lead into an out-of-sync situation.

To fix a collection's iteration order, the iteration order must be defined either explicitly or implicitly. For explicit order, one may use SortedSet<Key> or SortedDictionary<Key, Value> which always iterate in the sorted key order. This however requires the Keys to be IComparable which can be tedious and error-prone to implement for types that are not naturally comparable.

For implicit ordering, Metaplay SDK ships with OrderedSet<Key> and OrderedDictionary<Key, Value> which work as drop-in-replacements for HashSet<Key> and Dictionary<Key, Value>. These collections iterate in the same order as the items were inserted into the collection. For example inserting elements A, B and C in order will result in the iteration order of A, B, C.

Collection Behaviors

Type	Deterministic order	Notes
HashSet<K>	No
Dictionary<K, V>	No
SortedSet<K>	Yes, ordered by key	Slow and allocates a lot, use OrderedSet<> instead if possible
SortedDictionary<K, V>	Yes, ordered by key	Slow and allocates a lot, use OrderedDictionary<> instead if possible
OrderedSet<K>	Yes, insert order
OrderedDictionary<K, V>	Yes, insert order
List<K>	Yes, insert order	Use only for small collections