Subject: [netmod] Key-value data structures in YANG/JSON encoding

From: "Y. Richard Yang" <[email-masked]>
Date: Tue, 30 Sep 2014 16:31:03 -0400

Hi all,

A few of us are doing an exercise of defining a YANG module to express the
ALTO protocol (RFC7285). Multiple problems come up and here is one problem
we encounter.

First, the context. A design decision of the ALTO protocol is to use
key-value stores (maps), which are different from lists or containers. Many
large-scale systems are designed based on key-value stores, and many
programming frameworks provide hash maps.

A particular example of using key-value map is the network-map, which is
defined as a key-value store to enforce that each named endpoint address
group has a unique name. A specific example is in Section 11.2.1.7 of RFC
7285 (http://www.rfc-editor.org/rfc/rfc7285.txt):

         "network-map" : {
           "PID1" : {
             "ipv4" : [
               "192.0.2.0/24",
               "198.51.100.0/25"
             ]
           },
           "PID2" : {
             "ipv4" : [
               "198.51.100.128/25"
             ]
           },
           "PID3" : {
             "ipv4" : [
               "0.0.0.0/0"
             ],
             "ipv6" : [
               "::/0"
             ]
           }

One way to express this in YANG is the following:
===example YANG===
list network-map {
  key "pid";
  leaf pid {
    type string;
  }
  leaf endpoint-address-group ... {
    // ...
  }
}
==================

Following the currently defined json encoding, the output will be:
{
  "network-map" : [
    {
      "pid" : "PID1",
       // ...
    },
    {
      "pid" : "PID2",
      // ...
    },
    {
      "pid" : "PID3",
      // ...
    }
  ]
}

But this not what we want, because it is using an array, not a map. One
does not have to use an array to store the map.

We see two possibilities, if to produce the output. One is in the encoding
process: define such outputs on matching a template:

list MyList {
  key x;
  leaf x {
    type string;
  }
  leaf y {
   ...
  }
}

The second is that maybe this should be resolved in YANG; i.e., introducing
a new data type (beyond list, container), but something like key-value
store, say named map:

map MyMap {
  key my-key {
    ...
  };
  value my-value {
  }
}

Note that the second mapping involves work if the key type is not a simple
type (say string or numbers). A typical approach in some software framework
is to define a hash function on key.

We have discussed the issue with Lada, and now take the issue to the
mailing list. If anyone else has encountered similar problems, please let
us know. We also want to get a sense of any interest in introducing the
data type in YANG. Any comments will be appreciated.

Thanks!

Richard

---

From: "Thomas D. Nadeau" <[email-masked]>
Date: Tue, 30 Sep 2014 13:55:20 -0700

I was discussing this very same issue here at the ODL Yangathon yesterday.  Others are stumbling onto this same issue.

	--Tom

> Hi all,
> 
> A few of us are doing an exercise of defining a YANG module to express the ALTO protocol (RFC7285). Multiple problems come up and here is one problem we encounter. 
> 
> First, the context. A design decision of the ALTO protocol is to use key-value stores (maps), which are different from lists or containers. Many large-scale systems are designed based on key-value stores, and many programming frameworks provide hash maps.
> 
> A particular example of using key-value map is the network-map, which is defined as a key-value store to enforce that each named endpoint address group has a unique name. A specific example is in Section 11.2.1.7 of RFC 7285 (http://www.rfc-editor.org/rfc/rfc7285.txt):
> 
>          "network-map" : {
>            "PID1" : {
>              "ipv4" : [
>                "192.0.2.0/24",
>                "198.51.100.0/25"
>              ]
>            },
>            "PID2" : {
>              "ipv4" : [
>                "198.51.100.128/25"
>              ]
>            },
>            "PID3" : {
>              "ipv4" : [
>                "0.0.0.0/0"
>              ],
>              "ipv6" : [
>                "::/0"
>              ]
>            }
> 
> But this not what we want, because it is using an array, not a map. One does not have to use an array to store the map.
> 
> We see two possibilities, if to produce the output. One is in the encoding process: define such outputs on matching a template:
> 
> list MyList {
>   key x;
>   leaf x {
>     type string;
>   }
>   leaf y { 
>    ...
>   }
> }
> 
> The second is that maybe this should be resolved in YANG; i.e., introducing a new data type (beyond list, container), but something like key-value store, say named map:
> 
> map MyMap {
>   key my-key {
>     ...
>   };
>   value my-value {
>   }
> }
> 
> Note that the second mapping involves work if the key type is not a simple type (say string or numbers). A typical approach in some software framework is to define a hash function on key. 
> 
> We have discussed the issue with Lada, and now take the issue to the mailing list. If anyone else has encountered similar problems, please let us know. We also want to get a sense of any interest in introducing the data type in YANG. Any comments will be appreciated.
> 
> Thanks!
> 
> Richard
> _______________________________________________
> netmod mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/netmod

---

From: Andy Bierman <[email-masked]>
Date: Tue, 30 Sep 2014 14:16:54 -0700

Hi,

On Tue, Sep 30, 2014 at 1:55 PM, Thomas D. Nadeau <[email-masked]>
wrote:

>
> I was discussing this very same issue here at the ODL Yangathon
> yesterday.  Others are stumbling onto this same issue.
>
>
Do you mean you want control over the YANG to JSON mapping?
IMO, YANG needs to be independent of the protocol message encoding.
The implementation burden on servers is already too high.
There should only be 1 mapping for each encoding format.

How would you change YANG to get this JSON encoding?

--Tom
Andy

> The second is that maybe this should be resolved in YANG; i.e.,
> introducing a new data type (beyond list, container), but something like
> key-value store, say named map:
>
> map MyMap {
>   key my-key {
>     ...
>   };
>   value my-value {
>   }
> }
>

---

From: "Y. Richard Yang" <[email-masked]>
Date: Tue, 30 Sep 2014 17:37:59 -0400

Cool! It us good to know that we are not the only one.

Richard

---

From: "Y. Richard Yang" <[email-masked]>
Date: Tue, 30 Sep 2014 17:48:35 -0400

> Do you mean you want control over the YANG to JSON mapping?

Yes and no. The issue is raised in the context of encoding. But it is a
more general issue regarding completeness of data types in YANG:

- list is an ordered array

- container is a static, heterogeneous associate array

- key-value store is a dynamic (size unknown at compile time), homogeneous
array. It is a commonly used data type.

> How would you change YANG to get this JSON encoding?

There are at least two possibilities. Please see previous email. Make sense?

Richard
>
>
>
>> --Tom
>>
>>
>
> Andy
>
>>>
>>> Hi all,
>>>
>>> A few of us are doing an exercise of defining a YANG module to express
the ALTO protocol (RFC7285). Multiple problems come up and here is one
problem we encounter.
>>>
>>> A particular example of using key-value map is the network-map, which
is defined as a key-value store to enforce that each named endpoint address
group has a unique name. A specific example is in Section 11.2.1.7 of RFC
>>>
>>> We see two possibilities, if to produce the output. One is in the
introducing a new data type (beyond list, container), but something like
key-value store, say named map:
>>>
>>> map MyMap {
>>>   key my-key {
>>>     ...
>>>   };
>>>   value my-value {
>>>   }
>>> }
>>>
>>> Note that the second mapping involves work if the key type is not a
simple type (say string or numbers). A typical approach in some software
framework is to define a hash function on key.

---

From: "Thomas D. Nadeau" <[email-masked]>
Date: Tue, 30 Sep 2014 15:00:06 -0700

On Sep 30, 2014:2:16 PM, at 2:16 PM, Andy Bierman <[email-masked]> wrote:

> Hi,
> 
> 
> On Tue, Sep 30, 2014 at 1:55 PM, Thomas D. Nadeau <[email-masked]> wrote:
> 	

	That isn't what I was getting at - the key-value pair representation was asked about. It is a pain representing this as a list.

	--Tom

---

From: Kent Watsen <[email-masked]>
Date: Wed, 1 Oct 2014 01:37:36 +0000

>From a data-modeling perspective, it makes sense to be able to define
maps.  For instance, one can envision said information being used during
code-generation for in-memory and persisted datastores.

*If* it is not required that the JSON encoding be a JSON map, your yang
module could create a derived type:

    typedef map {
      type list;
    }

    container network-map {
      map entry {
        key "pid";
        leaf pid {
          type string;
        }
        leaf-list ipv4 {
          type inet:ipv4-prefix;
        }
        leaf-list ipv6 {
          type inet:ipv6-prefix;
        }
      }
    }

I actually just tried this (see attached file), but pyang complains:

  pyang --strict alto-test.yang

  alto-test.yang:7: warning: imported module ietf-inet-types not used
  alto-test.yang:25: error: type "list" not found in module alto-test
  alto-test.yang:30: error: unexpected keyword "map"

RFC 6020 doesn't limit which types can be used in a typedef statement, so
this might be a bug in pyang...

Kent

From:  "Y. Richard Yang" <[email-masked]>
Date:  Tuesday, September 30, 2014 at 1:31 PM
To:  "[email-masked]" <[email-masked]>
Cc:  IETF ALTO <[email-masked]>
Subject:  [netmod] Key-value data structures in YANG/JSON encoding

Hi all,

First, the context. A design decision of the ALTO protocol is to use
key-value stores (maps), which are different from lists or containers.
Many large-scale systems are designed based
 on key-value stores, and many programming frameworks provide hash maps.

A particular example of using key-value map is the network-map, which is
defined as a key-value store to enforce that each named endpoint address
group has a unique name. A specific
 example is in Section 11.2.1.7 of RFC 7285
(http://www.rfc-editor.org/rfc/rfc7285.txt):

         "network-map" : {
           "PID1" : {
             "ipv4" : [
               "192.0.2.0/24 <http://192.0.2.0/24>",
               "198.51.100.0/25 <http://198.51.100.0/25>"
             ]
           },
           "PID2" : {
             "ipv4" : [
               "198.51.100.128/25 <http://198.51.100.128/25>"
             ]
           },
           "PID3" : {
             "ipv4" : [
               "0.0.0.0/0 <http://0.0.0.0/0>"
             ],
             "ipv6" : [
               "::/0"
             ]
           }

We see two possibilities, if to produce the output. One is in the encoding
process: define such
 outputs on matching a template:

list MyList {
  key x;
  leaf x {
    type string;
  }
  leaf y { 
   ...
  }
}

key-value store, say
 named map:

map MyMap {
  key my-key {
    ...
  };
  value my-value {
  }
}

Note that the second mapping involves work if the key type is not a simple
type (say string or numbers). A typical approach in some software
framework is to
 define a hash function on key.

We have discussed the issue with Lada, and now take the issue to the
mailing list. If anyone else has encountered similar problems, please let
us know. We also want to get a sense of any interest in introducing the
data type in YANG. Any comments will
 be appreciated.

Thanks!

Richard

---

From: Xiao SHI <[email-masked]>
Date: Tue, 30 Sep 2014 21:59:07 -0400

Hi Kent,

That's a viable solution, but I still have a few questions about it.

In RFC6020 Sec. 7.4, the type statement takes an argument that's a built-in
type or derived type (which are all based in built-in types), but in Sec.
4.2.4 Built-in types do not include "list." I think "list" is handled as a
statement rather than a type in YANG. Regardless, it would require some
extension in YANG to express the key-value structure.

In addition, I do think it is important that the JSON representation is a
JSON map object, which encodes what element the key is and also
automatically enforces uniqueness.

Cheers,
Xiao

---

From: Kent Watsen <[email-masked]>
Date: Wed, 1 Oct 2014 02:31:40 +0000

> In RFC6020 Sec. 7.4, the type statement takes an argument that's a built-in type or derived type (which are all based in built-in types), but in Sec. 4.2.4 Built-in types do not include "list."
> I think "list" is handled as a statement rather than a type in YANG.

Ah, yes, that explains it - good catch.  So a new statement would be needed after all...

Thanks,
Kent

---

From: Thomas Nadeau <[email-masked]>
Date: Tue, 30 Sep 2014 19:37:09 -0700

Please note this as an issue for a future version of yang. 

Tom 

> On Sep 30, 2014, at 7:31 PM, Kent Watsen <[email-masked]> wrote:
> 
>