Subject: Re: [alto] JSON Patch vs. custom representation for incremental updates

From: Wendy Roome <[email-masked]>
Date: Fri, 01 Aug 2014 10:17:44 -0400

Richard,

Here are my answers to your questions:

#1: Draft 27, section 11.2.3.6, defines a cost map as a map from (src,dest)
to JSONValues, not just numbers. I believe that was added at some point to
allow for multi-cost arrays and string-valued costs. The document does go on
to say:

> An implementation of the protocol in this document
> 
> SHOULD assume that the cost is a JSONNumber and fail to parse if it
> 
> is not, unless the implementation is using an extension to this
> 
> document that indicates when and how costs of other data types are
> 
> signaled.
> 
> 
Incremental update is indeed an extension, so allowing nulls does not
violate the base protocol.

#2: Here's my assessment of how well that approach -- "use full-map message
to present the deltas" -- would work for incremental update for other
full-map services:

Network Map: The incremental-update message would give new pattern arrays
for all PIDs that changed. This works, but is inefficient if PIDs have 100's
of CIDRs, and only a few change.

Cost Map with Multi-Cost Extension: If any cost in the set changes for a
src/dest pair, the incremental update message would give the full array for
that pair. This works, although it may be inefficient when only one cost in
the set changes.

PID Property Map Extension: The incremental update message would give the
new value for any pid/property pair that changed, or null for any property
that was deleted. This works just as well as for cost maps.

- Wendy Roome
From:  "Y. Richard Yang" <[email-masked]>
Date:  Thu, July 31, 2014 at 15:34
 
> Turns out that our JSON cost-map representation is also perfect
> representation of an incremental update. Just change the semantics
> slightly:
> 
> * Start with the previous cost matrix, rather than an empty matrix.
> * For a null-valued cost point, remove that point from the previous
> version, if it existed.
> * For a non-null cost point, add it to the matrix, either replacing the
> previous value or creating a new one.

Two comments:

1. A small technical question: what is the JSON type for each element of the
cost matrix? It is a JSON number before. Now it is JSON number \union null?

The more general, intended question is whether it will be beneficial to
introduce a generic data type to denote operations.

2. A more general question is: how widely applicable is your design (i.e.,
using the original data type plus some small annotation to convey updates?
Or more interestingly, where the design does not work (well)?

> So for cost maps, efficient custom patch messages are "free². Or at least
> "no additional work." :-)
> 
> For network maps, the case isn't as clear. The data structure that best
> captures the semantics of a network map is a lookup table from CIDRs to
> PID names. Alternatively, a network map is a lookup table from PID names
> to sets of CIDRs, with the additional assertion that a CIDR is in only one
> set. Our JSON representation is a lookup table from PID names to arrays of
> CIDRs.
> 
> Our JSON network map message does not do a good job of representing
> network map deltas such as "move 1.0.0.0/16 <http://1.0.0.0/16>  from PID1 to
> PID2".
> 
> On the other hand, JSON patch doesn't do a good job of representing
> network map changes either, if only because we use an array to represent a
> set, so JSON patch thinks the order matters.
> 
> On top of that, I claim that incremental update simply isn't that
> important for network maps. A fundamental assumption behind the design of
> ALTO is that network maps will not change very often. When a network map
> changes, it completely invalidates all previously retrieved cost maps. Any
> change to a network map, no matter how simple, is a flag day.
> 
> So how about this compromise: for cost maps, define incremental update
> using our existing cost map message format. If the JSON group asks why
> don't we use JSON patch, just say that our message format perfectly
> captures the semantics of all legal cost map changes, and ALTO clients and
> servers already support it, so we don't need any additional patch
> mechanism.
> 

This compromise looks reasonable to me. To proceed, it will be great if the
overall update framework is laid out (e.g., indicate the default as well as
the patch mechanism(s) for each data type), so that we can claim that ALTO
has a complete patch mechanism?

> For network maps, do not define incremental update at this time. Wait
> until some ALTO servers actually implement incremental cost map update --
> and clients use it! -- and then see if there is any demand for incremental
> update for network maps.
> 

See above. 

Richard

---

From: Wendy Roome <[email-masked]>
Date: Fri, 01 Aug 2014 11:03:10 -0400

Although it's tempting to extend JSON patch, I think that doing that from
the context of the ALTO WG is a bad idea, both technically and politically.

Here's another take on my approach to representing incremental update. Every
ALTO full map service is, at a high level, a map from KEY to VALUE. For cost
maps, the key is a src/dest pair, and the value is a number (or for
multi-cost, an array). For network maps, the key is a PID-name/address-type
pair, and the value is an array of addresses of that type. For PID property
maps, the key is a PID-name/property-name pair, and the value is the string
value.

Because JSON does not allow lookup-table keys to be pairs of strings, we
encode those maps as nested lookup tables.

For ALTO maps, an incremental update involves replacing the value for a key,
or deleting a key. That's it; a server cannot make any other changes.

Given that updates are that well structured, I think a reasonable
alternative to JSON patch is to use the same message format as for the
original data, with the semantics that the client adds these new values to
the previous version of the table, and a null value means delete that key.

This should be easy for any client to handle. And it is efficient, provided
that we can regard the value as an atomic unit. It may break down with
something like a network map, if (say) a CIDR moves from one large PID to
another. In this case, JSON Patch may be more efficient. However, because we
represent a CIDR set as a JSON array, when an ALTO server asks a JSON patch
library to calculate the patch from an "old" to "new" network map, the ALTO
server must preserve the order of addresses in those CIDR arrays. If not,
the JSON patch representation may be very inefficient.

Incidentally, for network maps, an alternative incremental update message
would be a map from CIDRs to PID names. Remove the CIDR from whatever PID it
was in before, and put it the new PID. Null means that CIDR is no longer
used.

Arguably, that would have been a better model for the network map message in
the first place, because it captures the semantics of a network map better
than the current network map message.

- Wendy Roome

From:  "Y. Richard Yang" <[email-masked]>
Date:  Thu, July 31, 2014 at 16:50
To:  Wendy Roome <[email-masked]>
Cc:  Mark Nottingham <[email-masked]>, Paul Bryan <[email-masked]>, IETF
ALTO <[email-masked]>
Subject:  Re: [alto] JSON Patch vs. custom representation for incremental
updates

To make progress, here is one straw-man proposal encoding that combines
JASON PATCH (RFC6902) and in-place edit. Specifically, JSON PATCH defines a
set of ops. How about we define a new op, as an extension of JSON PATCH,
that provides in-place override, as in Wendy's design. One possibility is to
name it "override", or another name you like. It still has "path", to
indicate the place of "override". Its "value" will be Wendy's encoding.

---

From: "Paul C. Bryan" <[email-masked]>
Date: Sun, 27 Jul 2014 20:52:20 -0700

On Mon, 2014-07-28 at 12:48 +1000, Mark Nottingham wrote:

> Just that the PATCH method is defined for generic mechanisms, not
> application-specific ones; if your payload is application-specific,
> you might as well use POST.

If the intent is for the operation to be idempotent, then I believe
PATCH can still be more suitable for an application-specific payload.

Paul

---

From: "Paul C. Bryan" <[email-masked]>
Date: Sun, 27 Jul 2014 21:15:48 -0700

On Mon, 2014-07-28 at 13:54 +1000, Mark Nottingham wrote:

> PATCH isn't idempotent.

Ah, d'oh, yeah I was clearly on drugs when I wrote that. I was thinking
of the text that reads "[a] PATCH request can be issued in such a way as
to be idempotent..." but of course POST can use conditionals too. So,
what Mark said. :-)

Paul