Subject: [alto] ALTO incremental updates and JSON Patch extension

From: "Y. Richard Yang" <[email-masked]>
Date: Tue, 14 Oct 2014 13:47:04 -0400

Dear all,

Some of us are having an extensive discussion on how to proceed regarding
the ALTO incremental updates WG item. Here is a summary of what we are
thinking. At a high level, we plan to propose an approach of using JSON
Patch (RFC6902), but with some extensions. We want to get your comments and
advice on if you see any problems, and how best to proceed.

Current state:
==========
Both JSON Patch (RFC6902) and
http://tools.ietf.org/html/draft-roome-alto-incr-updates-01 are considered
as candidates of the encoding update message format.

Design goal and problem:
====================
Generality and efficiency. That is, we want an incremental update format
that can handle not only current resources but also future resources. The
recent trend in adopting YANG shows that general mechanisms, not per
protocol patch, have value. Generic encoding of JSON Patch based on XPATH
and a few operators is complete in this sense, but inefficient in key ALTO
cases such as updating cost maps, as pointed out in
http://tools.ietf.org/html/draft-roome-alto-incr-updates-01

Key idea:
=======
A JSON object can be considered as an key-value tree, with each node being
an object and each edge labeled by the key, and the value of the edge
pointing to another object. For example, the ALTO cost map example:
{
            "meta" : {

              "dependent-vtags" : [
                {"resource-id": "my-default-network-map",
                 "tag": "3ee2cb7e8d63d9fab71b9b34cbf764436315542e"
                }
              ],

              "vtag":
                 {"resource-id": "COST-MAP-ID", "tag": "CM-TAG"},

              "cost-type" : {"cost-mode"  : "numerical",
                             "cost-metric": "routingcost"
              }
            },
            "cost-map" : {
              "PID1": { "PID1": 1,  "PID2": 5,  "PID3": 10 },
              "PID2": { "PID1": 5,  "PID2": 1,  "PID3": 15 },
              "PID3": { "PID1": 20, "PID2": 15  }
            }

defines a data tree with 14 leaf nodes:

"meta/dependent-vtags/resource-id": "my-default-network-map",
"meta/dependent-vtags/tag": "3ee2cb7e8d63d9fab71b9b34cbf764436315542e",
...
"cost-map/PID3/PID1": 20,
"cost-map/PID3/PID2": 15

RFC6902 focuses on encoding updating one node on the tree at a time. On the
other hand, one can realize that the cost-map update encoding of
http://tools.ietf.org/html/draft-roome-alto-incr-updates-01 updates a set
of nodes. For example, an update example
{
        "meta": {
             "vtag":
                 {"tag": "NEW-CM-TAG"},
             },
        "cost-map": {
             "PID1": {"PID2": 10, "PID99": null}
             }
   }
updates 3 nodes.

If one thinks about, one will realize that this is a general, interesting
design: consider the data tree of the original object; the update object is
a partial tree of the original, and updates a batch containing all matched
nodes in the partial tree. We call this operator the tree-replace operator.
How may one do this as an extension of RFC6902:

{
 "op" : "tree-replace",
 "path" : "/",    // prefix of update object
 "value" :       // just a copy of the partial object in value
      { "meta": {
             "vtag":
                 {"tag": "NEW-CM-TAG"},
         },
        "cost-map": {
             "PID1": {"PID2": 10, "PID99": null}
          }
      }
}

Hence, we have a simple operator that appears to be able to fix the
cost-map efficiency issue and is still general, not ALTO only.

Next step:
========
- One possibility is to start to work on an extension of RFC 6902 to
introduce this operator, if there is no bug. After this is done, we specify
ALTO incremental updates using the new op. An issue is that this is a
sequential process and may take time.

- Another possibility is that we specify JSON Patch as incremental update
encoding for now, losing efficiency. In parallel, we push for the new op,
and when it is done, ALTO incremental updates implementation can use the
new op.

- A third possibility is that we define the extension operator in ALTO
incremental updates document itself, and proceed quickly.

Any bug in the design? Any comments or suggestions?

Thanks!

Richard, Wendy

---

From: Mark Nottingham <[email-masked]>
Date: Wed, 15 Oct 2014 14:13:49 +1100

Hi Richard,

RFC6902 doesn't allow extension operators; you'd need to define a new media type and specify its behaviour. Of course, you could do that pretty easily by just saying "here's a new media type; it has the same semantics / requirements as JSON Patch, plus this...".

Also, I trust you've seen the new JSON merge-patch RFC (I think we spoke about it before)?
  https://tools.ietf.org/html/rfc7386

Cheers,

On 15 Oct 2014, at 4:47 am, Y. Richard Yang <[email-masked]> wrote:

> Dear all,
> 
> Some of us are having an extensive discussion on how to proceed regarding the ALTO incremental updates WG item. Here is a summary of what we are thinking. At a high level, we plan to propose an approach of using JSON Patch (RFC6902), but with some extensions. We want to get your comments and advice on if you see any problems, and how best to proceed.
> 
> Current state: 
> ==========
> Both JSON Patch (RFC6902) and  http://tools.ietf.org/html/draft-roome-alto-incr-updates-01 are considered as candidates of the encoding update message format.
> 
> Design goal and problem: 
> ====================
> Generality and efficiency. That is, we want an incremental update format that can handle not only current resources but also future resources. The recent trend in adopting YANG shows that general mechanisms, not per protocol patch, have value. Generic encoding of JSON Patch based on XPATH and a few operators is complete in this sense, but inefficient in key ALTO cases such as updating cost maps, as pointed out in http://tools.ietf.org/html/draft-roome-alto-incr-updates-01
> 
> Key idea: 
> =======
> A JSON object can be considered as an key-value tree, with each node being an object and each edge labeled by the key, and the value of the edge pointing to another object. For example, the ALTO cost map example:
> {
>             "meta" : {
>                 
>               "dependent-vtags" : [
> RFC6902 focuses on encoding updating one node on the tree at a time. On the other hand, one can realize that the cost-map update encoding of http://tools.ietf.org/html/draft-roome-alto-incr-updates-01 updates a set of nodes. For example, an update example 
> {
>         "meta": {
>              "vtag":
>                  {"tag": "NEW-CM-TAG"},
>              },
>         "cost-map": {
> If one thinks about, one will realize that this is a general, interesting design: consider the data tree of the original object; the update object is a partial tree of the original, and updates a batch containing all matched nodes in the partial tree. We call this operator the tree-replace operator. How may one do this as an extension of RFC6902: 
> 
> {
>  "op" : "tree-replace",
> Hence, we have a simple operator that appears to be able to fix the cost-map efficiency issue and is still general, not ALTO only. 
> 
> Next step:
> ========
> - One possibility is to start to work on an extension of RFC 6902 to introduce this operator, if there is no bug. After this is done, we specify ALTO incremental updates using the new op. An issue is that this is a sequential process and may take time.
> 
> - Another possibility is that we specify JSON Patch as incremental update encoding for now, losing efficiency. In parallel, we push for the new op, and when it is done, ALTO incremental updates implementation can use the new op.
> 
> - A third possibility is that we define the extension operator in ALTO incremental updates document itself, and proceed quickly.
> 

--
Mark Nottingham   https://www.mnot.net/

---

From: "Y. Richard Yang" <[email-masked]>
Date: Wed, 15 Oct 2014 00:07:34 -0400

Dear Mark,

Thanks a lot for the quick response! I did not remember reading
merge-patch. After just reading it, I found that it is doing exactly what
we wanted to do, and we called it tree-replace, to be similar to the
replace operator defined in RFC6902. We will see how we may use it in our
design.

Since we are at JSON patch extensions, here is another issue that we want
to resolve: set operations on an array. Consider a JSON object
{
  "pid1" : ["prefix1", "prefix2", "prefix3"]
  "pid2" : ["prefix3", "prefix4", "prefix5"]
}

To delete "prefix2" from the value of "pid1", we need to write

op : remove
path : /pid1/1

However, the real intention of the values of "pid1" and "pid2" are sets,
but JSON has no concept of a set (not multi set), as discussed before. The
set semantics guarantees no duplicates, and hence we may eliminate the
burden on an application to keep track of the array index, if we are
allowed to extend the JSON Pointer (rfc6901), in particular, when the case
of the currently referenced value is a JSON array, by allowing functions or
other chars, for example, to denote a set, or index look up--the current
definition allows only numerical index or - and hence one can resolve
ambiguity...

Make sense?

Richard

On Tue, Oct 14, 2014 at 11:13 PM, Mark Nottingham <[email-masked]> wrote:

> Hi Richard,
>
> RFC6902 doesn't allow extension operators; you'd need to define a new
> media type and specify its behaviour. Of course, you could do that pretty
> easily by just saying "here's a new media type; it has the same semantics /
> requirements as JSON Patch, plus this...".
>
> > Some of us are having an extensive discussion on how to proceed
> regarding the ALTO incremental updates WG item. Here is a summary of what
> we are thinking. At a high level, we plan to propose an approach of using
> JSON Patch (RFC6902), but with some extensions. We want to get your
> comments and advice on if you see any problems, and how best to proceed.
> >
> > Current state:
> > ==========
> http://tools.ietf.org/html/draft-roome-alto-incr-updates-01 are
> considered as candidates of the encoding update message format.
> >
> > Design goal and problem:
> > ====================
> > A JSON object can be considered as an key-value tree, with each node
> being an object and each edge labeled by the key, and the value of the edge
> > RFC6902 focuses on encoding updating one node on the tree at a time. On
> the other hand, one can realize that the cost-map update encoding of
> > If one thinks about, one will realize that this is a general,
> interesting design: consider the data tree of the original object; the
> update object is a partial tree of the original, and updates a batch
> containing all matched nodes in the partial tree. We call this operator the
> tree-replace operator. How may one do this as an extension of RFC6902:
> >
> > {
> >  "op" : "tree-replace",
> > - Another possibility is that we specify JSON Patch as incremental
> update encoding for now, losing efficiency. In parallel, we push for the
> new op, and when it is done, ALTO incremental updates implementation can
> use the new op.
> >

---

From: Xiao SHI <[email-masked]>
Date: Wed, 15 Oct 2014 07:04:46 -0400

Hi folks,

Based on a cursory reading of the merge-patch, one possible (but clumsy)
solution is to use the assumption that JSON names SHOULD be unique in a
JSON object. Hence if you have for example:
====
{
  "pid1" : {"prefix1" : {}, "prefix2" : {}, "prefix3" :{}}
  "pid2" : {"prefix3" : {}, "prefix4" : {}, "prefix5" : {}}
}
====
Now, to delete "prefix2" from the value of "pid1", one can do:
====
op : remove
path : /pid1/prefix2
====

Building on top of what Richard said, the set-like array may also be an
issue if it is in the middle of the targeted path. For example, if I have
the following object (Sec. 11.4.1.6 of RFC7285 with one added element in
the dependent-vtags array):
====
{
  "meta" : {
    "dependent-vtags" : [
      {
        "resource-id": "my-default-network-map",
        "tag": "7915dc0290c2705481c491a2b4ffbec482b3cf62"
      },
      {
        "resource-id": "my-alternative-network-map",
        "tag": "3ee2cb7e8d63d9fab71b9b34cbf764436315542e"
      }
    ]
  }
}
====
Let's say we want to modify the tag of the default-network-map (which seems
reasonable). Correct me if I'm wrong, but without knowing the specific
index of the array, this task would not be possible with JSON patch or
merge patch (since merge patch does not iterate through arrays).

Best,
Xiao

On Wed, Oct 15, 2014 at 12:07 AM, Y. Richard Yang <[email-masked]> wrote:

>> > Generality and efficiency. That is, we want an incremental update
>> format that can handle not only current resources but also future
>> resources. The recent trend in adopting YANG shows that general mechanisms,
>> not per protocol patch, have value. Generic encoding of JSON Patch based on
>> XPATH and a few operators is complete in this sense, but inefficient in key
>> ALTO cases such as updating cost maps, as pointed out in
>> http://tools.ietf.org/html/draft-roome-alto-incr-updates-01 updates a
>> set of nodes. For example, an update example
>> > {
>> >         "meta": {
>> >              "vtag":
>> >                  {"tag": "NEW-CM-TAG"},
>> >              },
>> >         "cost-map": {
> _______________________________________________
> alto mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/alto
>
>

---

From: "Y. Richard Yang" <[email-masked]>
Date: Wed, 15 Oct 2014 15:06:02 -0400

Hi Xiao,

> Now, to delete "prefix2" from the value of "pid1", one can do:
The preceding is quite clever!! It can be a generic way to encode set. My
concern is that it could be considered as only a clever hack :-)

> Let's say we want to modify the tag of the default-network-map (which
> seems reasonable). Correct me if I'm wrong, but without knowing the
> specific index of the array, this task would not be possible with JSON
> patch or merge patch (since merge patch does not iterate through arrays).
>

Very interesting example! The only way I could think of now, using your
preceding hack, if we use hash as name in array name:
h1 = hash({
        "resource-id": "my-default-network-map",
        "tag": "7915dc0290c2705481c491a2b4ffbec482b3cf62"
      })
h2 = hash({
        "resource-id": "my-alternative-network-map",
        "tag": "3ee2cb7e8d63d9fab71b9b34cbf764436315542e"
      })
{
     h1 : {
        "resource-id": "my-default-network-map",
        "tag": "7915dc0290c2705481c491a2b4ffbec482b3cf62"
      },
      h2 : {
        "resource-id": "my-alternative-network-map",
        "tag": "3ee2cb7e8d63d9fab71b9b34cbf764436315542e"
      }
 }

We might be getting more and more academic, but it will be cool to hear
what others think, if any.

Thanks!

Richard

>>> > RFC6902 focuses on encoding updating one node on the tree at a time.
>>> On the other hand, one can realize that the cost-map update encoding of

---

From: wangxin <[email-masked]>
Date: Thu, 16 Oct 2014 12:45:15 +0000

Hi, Xiao,
It seems that you use object to represent a set instead of array, and you make merge-patch also available by using an empty object (here, i wonder that is merge-patch still available if we want to add an object with a null value?).
I also think that using array to represent a set is very hard since it seems that the only way to access the item is using the number of item in array (merge-patch can only replace the whole array instead of adding or removing).
As for "meta", i think using "resource-id":"tag" can work:
{  "meta" : {    "dependent-vtags" : {       "my-default-network-map": "7915dc0290c2705481c491a2b4ffbec482b3cf62",       "my-alternative-network-map": "3ee2cb7e8d63d9fab71b9b34cbf764436315542e"    }  }}
or, if we need to add more information in "resource-id" for future work:
{  "meta" : {    "dependent-vtags" : {       "my-default-network-map": {                 "tag":"7915dc0290c2705481c491a2b4ffbec482b3cf62"        }       "my-alternative-network-map": {                 "tag":"3ee2cb7e8d63d9fab71b9b34cbf764436315542e"        }    }  }}
Thanks,Xin
From: [email-masked]
Date: Wed, 15 Oct 2014 07:04:46 -0400
To: [email-masked]
CC: [email-masked]; [email-masked]; [email-masked]
Subject: Re: [alto] ALTO incremental updates and JSON Patch extension

Hi folks,
Based on a cursory reading of the merge-patch, one possible (but clumsy) solution is to use the assumption that JSON names SHOULD be unique in a JSON object. Hence if you have for example:===={  "pid1" : {"prefix1" : {}, "prefix2" : {}, "prefix3" :{}}  "pid2" : {"prefix3" : {}, "prefix4" : {}, "prefix5" : {}}}====Now, to delete "prefix2" from the value of "pid1", one can do:====op : removepath : /pid1/prefix2====
Building on top of what Richard said, the set-like array may also be an issue if it is in the middle of the targeted path. For example, if I have the following object (Sec. 11.4.1.6 of RFC7285 with one added element in the dependent-vtags array):===={  "meta" : {    "dependent-vtags" : [      {        "resource-id": "my-default-network-map",        "tag": "7915dc0290c2705481c491a2b4ffbec482b3cf62"      },      {        "resource-id": "my-alternative-network-map",        "tag": "3ee2cb7e8d63d9fab71b9b34cbf764436315542e"      }    ]  }}====Let's say we want to modify the tag of the default-network-map (which seems reasonable). Correct me if I'm wrong, but without knowing the specific index of the array, this task would not be possible with JSON patch or merge patch (since merge patch does not iterate through arrays).
Best,Xiao

On Wed, Oct 15, 2014 at 12:07 AM, Y. Richard Yang <[email-masked]> wrote:
Dear Mark,
Thanks a lot for the quick response! I did not remember reading merge-patch. After just reading it, I found that it is doing exactly what we wanted to do, and we called it tree-replace, to be similar to the replace operator defined in RFC6902. We will see how we may use it in our design. 
Since we are at JSON patch extensions, here is another issue that we want to resolve: set operations on an array. Consider a JSON object {  "pid1" : ["prefix1", "prefix2", "prefix3"]  "pid2" : ["prefix3", "prefix4", "prefix5"]}
To delete "prefix2" from the value of "pid1", we need to write
op : removepath : /pid1/1
However, the real intention of the values of "pid1" and "pid2" are sets, but JSON has no concept of a set (not multi set), as discussed before. The set semantics guarantees no duplicates, and hence we may eliminate the burden on an application to keep track of the array index, if we are allowed to extend the JSON Pointer (rfc6901), in particular, when the case of the currently referenced value is a JSON array, by allowing functions or other chars, for example, to denote a set, or index look up--the current definition allows only numerical index or - and hence one can resolve ambiguity...

Make sense?
Richard

Cheers,

--

alto mailing list

[email-masked]