3 Entities and Protocols - a Background
Distribution in Mozart is realized by sharing language entities. How this is done depends on if they are stateless or stateful. Stateless entities are replicated between sites whereas stateful entities create access structures. The local semantics of the stateful entities are maintained in a distributed setting by a number of consistency protocols.
Mozart entities may be in one of two states: plain or globalized. A plain entity is only referenced within its virtual machine. This virtual machine is called the entity's home site. A plain entity will become globalized at the instance when a reference to it is shared. A globalized entity is returned to being plain when no more remote references exist; this is called localization.
The Distribution Subsystem offers four kinds of distribution behavior and four kinds of replication patterns. Distribution behavior and replication patterns are paired together to create different distribution semantics. Each entity type in Mozart has been assigned a pair to define its distributed semantics and behavior.
3.1 Distribution of References
At globalization an entity is given a globally unique identity (GUId). This name is used to identify imported references, to see if a copy of the entity already exists at the importing site. The GUId consists of a reference to the home site and an identifier that is unique at the home site.
When entities are transferred from one site to another five kinds of replication patterns exist. The importing site is responsible for building a structure according to the replication pattern. The five patterns are described here:
Replicated
Replicated entities do not have a GUId. Instead enough information is transferred at distribution time to enable the importer to build a complete copy of the data structure. Without a GUId it is not possible to determine whether the entity already exists at the importing site or not.
Replicated Uniquely
An entity that is Replicated Uniquely transfers enough information to build a complete replica of it at the importing site. In contrast to Replicated entities, Replicated Uniquely entities have a GUId that enables the importer to make sure that there may exist one and only one instance of the entity at the importing site.
Access Structure
When a stateful entity is globalized, a Manager is constructed at its home site. References to the the entity imported at other sites result in the construction of proxies pointing to the manager (see Figure 3.1). This structure is called an access structure. The GUId of the entity is used to ensure that one and only one proxy is built at site that imports references to the entity.
Access structures are used to maintain reference consistency and as a base for the consistency protocols described below.
Lazy Replication
Lazy Replication is a special case of Replicated Uniquely. Instead of sending the whole value of the entity the possibility to build an access structure is transferred. If no instance of the entity exists at the importer, the access structure is built. When a Lazy Replicated entity is accessed for the first time the value of the entity is requested and the access structure is removed when the value arrives.
Resource Placeholder
Some data structures should not be available remotely. This is handled by replacing those entities with a placeholder on which no operations can be performed except equality. This placeholder is reflected to language level as a Resource.
3.2 Consistency Protocols
As stated earlier, the DS uses consistency protocols to maintain the semantics of a plain entity also when it has been globalized. Note that this is of course not necessary for replicated stateless entities.
Stateful entities can have a real state or be single assignment, where single assignment means transforming into another entity once. This is used to implement distributed logic variables. Single assignment entities can be dealt with efficiently by a proxy-manager structure where the manager knows and notifies its proxies. Other stateful entities may implement distribution by letting their state move around to active proxies or by letting a manager act as a server for read and write requests. This gives us with three different protocols for maintaining entity semantics:
Stationary State
The manager maintains the state of a stateful entity locally, and proxies send read and write requests asynchronously to access the state.
Mobile State
Any proxy can attract the state of a stateful entity and operate on it locally as on a plain entity while the state is present.
Single Assignment
The manager knows all of its proxies and can administer any request to transform the entity to a reference to another entity, and forward this to all proxies.
3.3 Distribution of Mozart Entities
Table 3.1 shows the class of reference distribution and the consistency protocol used for entities in Mozart.
Entity Type | Reference Distribution | Consistency Protocol |
|---|---|---|
Port | Access Structure | Stationary |
Variable | Access Structure | Single assignment |
Cell | Access Structure | Mobile state |
Lock | Access Structure | Mobile state |
Object | Lazy Replication | Mobile state |
Record | Replicated | none needed |
Atoms | Replicated | none needed |
List | Replicated | none needed |
Chunk | Replicated Unique | none needed |
Name | Replicated Unique | none needed |
Class | Replicated Unique | none needed |
Functor | Replicated Unique | none needed |
Procedure | Replicated Unique | none needed |
Code | Replicated Unique | none needed |
Dictionary | Resource Placeholder | none needed |
Array | Resource Placeholder | none needed |
Sited Entities | Resource Placeholder | none needed |
Builtin | Resource Placeholder | none needed |
Constraint Variable | Resource Placeholder | none needed |
Table 3.1.
3.4 Distributed Memory Management
Every Mozart site performs garbage collection locally. During this process all replicated entities and proxies are treated as plain Mozart data structures. Managers on the other hand act as roots for the local garbage collector.
To ensure that globalized entities are localized if and only if no more remote references exist, the DS has a distributed reference consistency algorithm. This is currently implemented by an extended version of Weighted Reference Counting1 called Secondary Weight. Weighted Reference Counting is an algorithm that assigns a total weight to an entity. When references are shared, a part of this weight is shared too. When all weight is present at the manager, the entity is local. The original algorithm has a problem in that weight is limited. Secondary Weight overcomes that problem, by allowing proxies to create a new range of weight that they manage.