KVS-BGP

A Key/Value store that allows for eventually consistent, distributed synchronization using BGP

Why BGP?

• BGP is a reliable way to distribute bytes over an arbitrary number of participating peers
  • Using eBGP, we can guarantee every peer will have a consistent view of the data
  • As long as one peer remains online, your data will be around
• Community support for adding categories to KeyValue pairs
  • Allows participating nodes to Pub/Sub to specific categories
  • Use BGP Policy to filter inbound/outbound synchronization of categories
• Many tools exist to inject the BGP routes into a peer mesh
  • E.g. exabgp, gobgp, bgpd-rs

HTTP API for KeyValue CRUD

Your favorite HTTP client can make requests to get/insert/remove KeyValue pairs:

$ curl http://localhost:8179/insert/name/Mat --request PUT
$ curl http://localhost:8179/get/name
Mat
$ curl http://localhost:8179/insert/favorite::protocol/BGP --request PUT
$ curl http://localhost:8179/insert/favorite::food/Pizza --request PUT
$ curl http://localhost:8179/insert/favorite::drink/Scotch --request PUT
$ curl http://localhost:8179/get/favorite::drink
Scotch
$ curl http://localhost:8179/get/favorite::protocol
BGP
$ curl http://localhost:8179/get/favorite::food
Pizza

Key/Value API

The current API is just PoC and should likely replicate other successful KeyValue APIs to work with existing clients (Eg. Redis)

Run kvs-bgp locally

See how to setup and run a kvs-bgp environment locally in the Examples directory.

Internal representation of KeyValue pairs

Supports encoding/decoding pairs as BGP update messages using IPv6 Unicast Prefix & NextHop

KeyValue Pairs

Each KeyValue is allowed ~768 Kbytes (65,535 * 96 bits). Data is serialized as Prefixes with sorted sequence numbers.

Prefix encoding is as follows:

First prefix for a KeyValue pair:

bits: | 16 :  16    :    16      :     16       :      64        |
addr: |BF51: seq #  : key length : value length :     data       | /128

Subsequent prefixes for a KeyValue pair:

bits: | 16 :  16    :                   96                       |
addr: |BF51: seq #  :                  data                      | /128

Notes:

• BF51 Prefix
  • Used for easy identification and to make sure this doesn't clobber public routes
• Sequence Number
  • Provides ordering for data decoding and creates unique routes so best-path selection doesn't filter prefixes
  • Allows for 65_535 prefixes per KeyValue pair, and given 12 bytes per prefix provides ~768 Kb per KeyValue pair
• Data
  • Serialized to bytes using Serde with bincode serialization

NextHop encoding is as follows:

bits: | 16 :   16    :  16   :    16    :          64            |
addr: |BF51: version : seq # : # routes :       key hash         | /128

Notes:

• Version
  • Encoding of the KeyValue version number
  • During convergence of an updated KeyValue pair, will provide unique Prefix/NextHop route so bytes of different versions aren't interlaced together
• Sequence Number
  • Provides ordering for data decoding and creates unique routes so best-path selection doesn't filter prefixes
• Number of Routes
  • Count of routes included in this version
  • Used to confirm when all routes have been received before decoding
• Key Hash
  • Hash of the KeyValue Key, to differentiate this NextHop from other KeyValue NextHops

Example

The KeyValue pair "MyKey" : "Some Value" would be represented as:

| Seq # | Prefix                                   | NextHop                        |
| 0     | BF51:0:D:12:500::                   /128 | BF51::3:7911:E0FA:7BEA:920B    |
| 1     | BF51:1:4D79:4B65:790A::             /128 | BF51:0:1:3:7911:E0FA:7BEA:920B |
| 2     | BF51:2:53:6F6D:6520:5661:6C75:6500  /128 | BF51:0:2:3:7911:E0FA:7BEA:920B |