Frequently Asked Questions
A recurring theme in distributed computing is how to deal with resources that a server allocates on behalf of a client. A typical example is a shopping cart that is implemented in the server: the server creates the shopping cart for the client, and the client gradually fills the cart with items. Eventually, the client is expected to either purchase the items in the shopping cart or to cancel the entire process; either action allows the server to destroy the shopping cart again, thereby reclaiming its associated resources.
Of course, the problem with this design is what to do if the client neither completes the purchase nor cancels it. Unless the server takes explicit action to deal with this scenario, it will hang onto the shopping cart forever and, once enough clients have failed to complete their purchasing process, will eventually run out of memory or other resources.
This particular problem is well known in distributed computing and has a well-known solution: use a session concept and a reaper to get rid of objects that have been abandoned by clients. (See "The Grim Reaper: Making Objects Meet Their Maker" in Issue 3 of Connections for a detailed discussion of this technique.)
However, not all distributed systems work this way. An alternative approach is to say "when the client no longer wants the object, the server should automatically reclaim it". This is exactly what Microsoft's DCOM (now a relic of the past) used to do. To understand why, we need to look a little bit at the history of DCOM.
DCOM was based on COM. In other words, Microsoft already had a non-distributed version of a component model and wanted to extend it to distributed applications: where, with COM, both client and the target object were in a single address space, with DCOM, they could be in different address spaces. In effect, DCOM was meant to be COM "with a longer wire". This meant that the existing COM APIs had to work without change in the distributed case, and that is where DCOM hit a snag.
COM used reference counting for its objects, much like Ice does for Slice classes and a number of other C++ data types. (See "Who's Counting" in Issue 25 of Connections for a detailed explanation of this mechanism.) When a client dropped the last reference to a COM object, the object's reference count dropped to zero, which caused the object to be reclaimed. This works very well as long as the client and the objects are in a single address space because it is fairly easy to ensure that the reference counts are maintained accurately. However, for COM APIs to work for the distributed case without a change in semantics, DCOM had to use the same reference counting. In other words, the actions of a client in one address space had to change the reference count of an object in a different address space.
The problem is how to ensure that the server maintains an accurate view of a reference count whose value depends on the actions of remote clients that can fail. Note that it is imperative for the reference count to be accurate: if the server's notion of the count is too low for any reason, it will reclaim an object while it is still in use and cause errors for those clients who think that the object still exists; if the server's notion of the count is too high, it will fail to reclaim resources when it should.
Maintaining accurate distributed reference counts turns out to be a surprisingly hard problem. The biggest issue is that clients can fail in unpredictable and random ways. For example, a client's machine can suffer a power failure or a client can get disconnected by a network failure. In either case, the network may not deliver timely notification of the problem to the server. Partial failure scenarios further complicate the picture. For example, if a client encounters an error when sending a message to a server, it cannot always be sure that the message was not received and acted upon by the server. This means that any distributed reference counting must be implemented with stateless and idempotent messages, otherwise such partial failures can permanently corrupt a reference count.
DCOM's solution for distributed reference counting was to define a ping protocol. Briefly, this protocol required clients (or rather, the client-side run time) to send ping messages to the server once every two minutes. The server-side run time monitored these ping messages and, if three consecutive messages were missed, the server assumed that the corresponding client was dead and adjusted the reference count of its objects accordingly.
There are numerous problems with this mechanism, both in concept and in implementation:
• A one-size-fits-all timeout of six minutes is wrong for almost everyone: some applications will need much shorter timeouts in order to avoid running out of resources while others need a much longer timeout to avoid objects being reclaimed prematurely.
• The mechanism reference counts all objects in the system. However, distributed applications usually contain many objects that do not need any reference counting. In fact, some distributed applications contain millions of objects, none of which require reference counting. Maintaining these unwanted reference counts causes needless overhead.
• Applications typically do not use objects as independent entities. Instead, several objects form a logical group and, when it comes to time to reclaim resources, all objects in the group must be reclaimed. (An example is our shopping cart object, which might reference a number of order item objects that represent the contents of the cart.) DCOM maintains a separate count for each object in the group even though, conceptually, a single count would be sufficient; however, there is no way for applications to indicate that such groups exist, so they could be counted as a whole.
• The ping protocol cannot run in the client's thread of execution because that thread may be busy with other, CPU-bound tasks, so it must run either asynchronously or use preemptive task switching. Depending on the client platform, implementing the protocol can be difficult. (For example, many embedded environments simply do not offer the necessary functionality, such as environments without support for threads or environments that support only a single foreground task.) In other words, the heavy demands of the DCOM run time limit the platforms on which it can be implemented.
• Because different clients may share the same objects, and because ping messages must identify which objects are in use, all objects must have a unique identity that clients and servers agree on. The run time can enforce that object identities are unique; however, unique identities are quite large and, therefore, expensive to hold in memory and to send over the network.
• The amount of information that must be carried by the network to maintain reference counts does not rise linearly with the number of objects. This is because ping messages must be sent for every object used by every client. In other words, the amount of traffic rises as O(n·m), where n is the number of clients, and m is the number of objects. For an application with two million clients, each using thirty objects (which is not unusual these days), that is sixty million ping messages every two minutes (or 500,000 per second).
• The server-side run time is responsible for destroying objects once three consecutive ping messages are missed. This means that the server-side run time must track which objects are used by every client for up to six minutes. For applications with many clients and objects, that is a considerable amount of state.
DCOM's ping protocol addresses some of these concerns, for example, by grouping ping messages into sets to reduce network traffic, by sending messages only when the client-side reference count of an object drops to zero (rather than sending a separate message for every call to DCOM's AddRef and Release), and by allowing ping sets to be piggy-backed onto ordinary messages.
However, despite these optimizations, the idea does not fly. For one, the protocol allows an unused object to hang around for up to six minutes, which is unacceptable for many applications. But, more seriously, the protocol incurs an intolerable amount of network traffic for applications with many objects. (Contrary to popular opinion, bandwidth is not cheap. Just ask anyone who pays for the bandwidth required by a popular web server or someone who communicates with cellular phones via GPRS or—heaven forbid—satellite links.)
The upshot is that DCOM's distributed reference counting did not scale well enough for a significant number of applications and, for those applications where it did scale, it often was unsuitable due to its fixed timeout. Microsoft eventually abandoned DCOM and distributed reference counting and, for .NET Remoting (which itself was superseded by WCF), introduced a leasing scheme that is very similar to the reaping technique we describe in Issue 3 of Connections.
Apart from reference counting, there are other forms of garbage collection (such as mark-and-sweep) that could be considered candidates for distributed systems. But they all suffer from the same underlying problem: to collect garbage, it is necessary to have an accurate system-wide view of every use of every object in existence. While this works very well in a single address space, for distributed systems, this is a fundamentally non-scalable requirement. So, in summary, Ice does not use distributed garbage collection because doing so would be a truly bad idea.