[E-Lang] Migration and Una (was: E FAQ)
Mark S Miller
Sun, 30 Sep 2001 10:33:40 -0700
>> >4.8. Is there a reason that object mobility isn't supported?
>> [...] it would seem that secure mobile objects are impossible.
At 11:10 AM Friday 9/28/01, Ken Kahn wrote:
>I'll agree about the general case, but aren't there many cases where one
>would want object mobility to trusted hosts? [...]
Sure. And it would be perfectly sensible for such a thing to be provided.
Btw, in light of previous discussions on e-lang, we may want to rephrase
this as "mutually reliant UTCBs".
>The broader question is what should a language support. I would argue it
>should support those things that a large enough fraction of the users need,
>when providing such support provides greater benefits than if the
>functionality were provided by user code. Unless adding such functionality
>costs too much in terms of complexity or implementation costs.
I'd say that's exactly the right question. Since mobility among mutually
reliant UTCBs can't provide a security benefit (mutually reliant UTCBs
jointly form a single UTCB anyway), I assume the only benefits we're seeking
are performance and management of our vulnerabilities to partition. I
believe user code can obtain these benefits by using the planned support for
PassByContruction (for replication and smart references), delegation (to
switch which replica is taken to be authoritative) and GC (to get rid of old
replicas when it's safe to do so).
Let's say A1 is designed to be a pseudo-migratable object. If A1 is
immutable, then everything's easy: It should be PassByContruction (pbc), and
it should just make a replica of itself in every vat that references it.
/*Note: Selfless pcbs are Immutable, Transparent, and PassByCopy. See
http://www.erights.org/elib/equality/same-object.html */. All resolved
references to a pbc object are near references, so there would be no
resolved remote references to any replica for a partition to break.
(Unresolved remote promises that designate a pbc object should promptly
resolve, but until then are breakable. This corresponds to an unavoidable
issue under any scheme.) When there are no longer any references to a local
replica, then it gets GC'ed, and "migration" has been accomplished.
If A1 is mutable, then we can first arrange for eventually consistent
(Lamport-style) replication using Chip Morningstar's Unum pattern. This
doesn't yet give us "migration", but please bear with me. Each replica of
an Unum is a "presence" of the Unum, and all the presences jointly are taken
to form the Unum. One of the presences is the "authoritative presence" --
its state is considered to be the "true" state of the Unum. A1, being the
initial presence, therefore starts out as the authoritative presence.
The other presences are effectively smart remote references to the
authoritative presence. These "shadow presences" maintain a somewhat stale
cache of a copy of some state from the authoritative presence -- but only
state that can be useful even when it's stale. These shadow presences do
support immediate calls for those operations that can be sensible performed
using this stale data -- giving us another huge victory over network
latency. But operations needing accurate state must still be eventual, and
must be delegated to the authoritative presence.
The shadow presences also register themselves as observers (in E,
"reactors") on the authoritative presence. Every time the authoritative
presence changes replicated state, it notifies all its reactors, so that
they may update their cached copies. In the absence of partition, we can
say that these caches are always "eventually consistent" -- they are always
consistent with some past state, they only move forward in time, and under
quiescence they will always eventually become accurate. (Does this capture
Lamport-like eventual consistency?)
During a partition, the presence can still give correct, even if
increasingly stale, service for the staleness tolerant operations. Of
course, it must refuse the accurate operations. Should the authoritative
presence again become reachable, the shadow should "heal". (Note: at EC we
didn't do this. Instead, we always invalidated shadow presences on
partition. So although both choices seem valuable, we don't yet have any
experience with shadows that survive partition.)
What happens when a shadow presence A2 is passed? Two simple possibilities are
1) a new shadow presence A3 is created that takes the authoritative presence
A1 as authoritative. A2 and A3 would both be registered as reactors on A1.
2) a new shadow presence A3 is created that takes shadow presence A2 as
authoritative. A2 is a reactor on A1, and A3 is a reactor on A2.
#1 is Granovetter introduction, and supports grant matching. #2 is
proxying, and does not.
Answer #1 gives us a flat multicast fanout for state updates. Answer #2
turns the presences into a spontaneously malformed multicast tree. (I say
"malformed" because the topology of the tree is based only on acts of
introduction, and not on any sensible performance issues.) NetNews, DNS,
and Notes are all massively scalable systems that use Lamport-like eventual
consistency to distribute state updates.
"When someone says they want to buy a shovel, remember that they probably
really want a hole in the ground."
Even though we have not yet addresses "migration", since the authoritative
presence hasn't moved, I speculate that this kind of massive state
replication, and the ability of local replicas to service local requests
synchronously, in fact provides most of the benefits that were actually
being sought by those who thought they wanted replication. And so far, we
haven't had to compromise capability security in the slightest -- given that
the state being replicated include only state available via A1'a normal
client interface. (In MarcS' terminology (need link) this is "front-end
state" rather than "encapsulated state".)
Besides non-migration, we've made one other sacrifice above in order to in a
simple security model: sticking to topology choices #1 and #2. I don't know
how to reconcile adaptive multicast topologies with capability security,
except by resorting to another layer of crypto (treating messages as
off-line certs), which would take us well beyond the security implicitly
provided by E itself.
Starting from the Unum pattern, migration is conceptually simple. (For this
discussion, let's assume the flat multicast fanout topology #1.) Let's say
the current authoritative presence A1 decides that A2 should become the
authoritative presence. It informs all its reactors (A2 and A3) of its
decision. A3 reacts to the decision by taking A2 to be authoritative,
unregistering on A1, and registering on A2. A2 also unregisters on A1, but
doesn't bother to register on itself. A2 now considers itself
authoritative. A1 then changes itself to consider A2 authoritative, and
registers on A2.
(Important: This points out another sense in which shadow presences are
smart references: they can engage in behavior to determine who/what they
take as authoritative. As another example, the shadow presences of a
Quorum-Unum would only take as authoritative answers that n out of m
authoritative presences agreed on. All such things should be programmable
in regular unprivileged E code.)
Any messages A1 receives that require accurate answers (which could have
been in transit from, eg, A3) it now forwards to A2. Any notification
messages it receives from A2 is forwards to any reactors that still may be
registered. We always settle into a #1 topology, but we allow #2 topologies
during the transition to avoid distributed locking.
Once the above migration process settles down, the only remote references
remaining to A1 are the same as for A3 -- the entry in A2's reactors list.
Unfortunately, this points to a remaining feature we need to make Una work
-- remote weak references. If A1 is no longer needed locally, this entry on
A2's reactor list should not prevent it from being collected. I wouldn't be
surprised if this was the hardest part of the story to implement.
So, to answer your question, I see nothing to be gained by directly
supporting object migration inside E itself. Rather, Una, migration,
quorums, etc, are all goods tests of the generality of the primitives
provided by E: Can these all be written in E?
Birds, Boxes, Robots, Trucks, and Nests. Oh my!
>P.S. Object mobility is simple in ToonTalk. An object migrates by giving a
>bird a box with a copy of its robots and its box. The bird flies off to a
>possibly remote host where a robot puts the incoming robots and box in a
>truck and the object is now running on the host where the bird's nest is.
I'm afraid I'm not yet good enough at translating between these worlds.
Could you rephrase in more conventional language terminology? (Sorry)