Unified storage semantics

[sreeja]

This discussion aims to define semantics for Zenoh storage irrespective of the backend technology used. We will also document the cases that the storage technology implementations should take care of.

Guarantees needed from a storage

• Support for PUT, DEL, and GET, for a single key or a set of keys
  The first two operations are updates and the last is a query. If an operation deals with a set of keys, instead of a single key, it will be referred to as a wildcard operation.

• Deterministic behaviour
  The behaviour of the storage upon receiving one or more concurrent or sequential operations must be deterministic.

• The latest value is always retained
  A storage must retain at least the latest value if it receives multiple updates on the same key. HLC timestamp is used as a tiebreaker. This guarantee is applicable per key.

• Convergence
  Consider more than one Zenoh storage storing the same key. A key in all the storages must have the same value if they receive the same set of updates. (Even though this is actually Strong Eventual Consistency, we will simply call this behaviour Eventual Consistency for the purpose of this document).

• Consistent wildcard updates
  A wildcard operation must consider all matching keys existing in the system. This means, if the updates are ordered (first using the partial order obtained from HLC and then using the device ID to obtain total order), all the updates concerning keys matching the key expression of the wild card update are considered.

Metadata required to maintain guarantees

• Tombstones
  Keeps track of the deletes that happened, with their timestamp
• List of wild card updates
• Latest timestamp per key
• List of matching keys corresponding to a key expression with wildcard(s)

Design requirements

• Ensure guarantees described above per storage manager plugin session
• Legacy interface support
  The database when read by an external application other than Zenoh, should maintain the expected behaviour
• Low overhead as much as possible
  Find a sweet-spot in the tradeoff between memory consumption and computational/network usage

Parameters affecting the design choices

• Persistence
  This parameter determines if we should store the data durably. The data should be recoverable even in case of a node crash as long as the hard disk is not corrupted.

  enum Persistence {
    Durable,
    Volatile,
  }

• History
  This parameter decides if a storage wants to keep history or not. The option All keeps all updates, while Latest keeps only the latest update.

  enum History {
    All,
    Latest,
  }

• Location
  To indicate whether a storage is hosted locally or if it is on a remote site, the latter case might incur costly data transfers.

  enum Location {
    Local,
    Remote,
  }

Persistence, History and Location will belong to StorageConfig.

Current implementations

Implementation	Persistence	History	Location
In-memory	Volatile	Latest	Local
In-memory timeseries*	Volatile	All	Local
RocksDB	Durable	Latest	Local
InfluxDB	Durable	All	Local/Remote
File System	Durable	Latest	Local
S3	Durable	Latest	Remote
Timestream*	Durable	All	Remote

_{^{* under discussion}}

Architecture of the storage manager plugin

Traits

/// Trait to be implemented by a Backend.
#[async_trait]
pub trait Volume: Send + Sync {
    fn get_admin_status(&self) -> serde_json::Value;
    async fn create_storage(&mut self, props: StorageConfig) -> ZResult<Box<dyn Storage>>;
}

/// Trait to be implemented by a Storage.
#[async_trait]
pub trait Storage: Send + Sync {
    fn get_admin_status(&self) -> serde_json::Value;
    async fn put(&mut self, sample: Sample) -> ZResult<()>;
    async fn delete(&mut self, sample: Sample) -> ZResult<()>;
    async fn query(&mut self, query: Query) -> ZResult<()>;
    async fn get_all_entries(&self) -> ZResult<Vec<(OwnedKeyExpr, Timestamp)>>;
}

Internal information maintained

• List of tombstones
• List of wildcard updates
• Mapping of latest timestamp processed for each key (optimization)
• Mapping of wildcard key expression to list of matching keys (optimization)

The first two are essential for correct functioning of the storage. The last two are only for optimising datastore hits. The key-timestamp map maintains the metadata which is useful to determine whether or not an incoming operation is outdated, and also for replication. The wildcard to key mapping can be included as part of the key-timestamp map if the key-timestamp map is stored as a trie of key chunks.

Design for each combination of storage

Along with the categories of storages defined earlier, we also have replication that requires metadata from the storage. Hence from now onwards, we consider 4 configurable parameters for a storage: Persistency - History_keeping - Location - Replication.

• If a storage is not persistent, there is no point in placing it in a remote location and performing replication.
• When the storage is Volatile, both tombstones and wildcard updates can be stored in memory. Otherwise, they have to be persisted on disk which brings in the problem of maintaining consistency with the different storages.
• When History-keeping is All we don’t have to maintain a cache with the latest timestamp per replica. (if not configured for replication)
• When the storage is Remote, we need to maintain a cache for optimization. This cache can be reused in case of replication.
• All the metadata is valid per instance of storage manager plugin, ie., if the storage manager plugin process goes down, there is no guarantee on the data stored on it. To ensure correctness, the user is expected to configure replication.
• All the metadata is computed at startup and kept consistent throughout the lifecycle.

Additional storage specific warnings

If the storage is storing data exploiting the key expression hierarchy, it has to take care of conflicts in the following cases:

1. PUT a/b/c followed by PUT a
2. PUT a followed by PUT a/b/c
   The hierarchical storage should have both keys a and a/b/c, and not a/b.

Basically, keep in mind that each chunk in the hierarchy can be either an intermediate path in the key expression that doesn’t store any value, or it actually is the end-point and stores a value.

Further points to discuss

Interceptors

Currently we have a provision for declaring interceptors, both incoming and outgoing. Since it is not yet used anywhere, we may discard that for the time being.

If we decide to maintain interceptors, we need to keep the following in mind:

• If a user provisioned an incoming data interceptor to filter out certain data, it might cause the alignment protocol to go in an infinite loop since the filtered out data will never be present in one storage and it will keep on asking the remote storages.
• Outgoing data interceptor is fine, as long as it doesn;t interfere with alignment protocol outgoing traffic.

[sreeja]

After an internal discussion, the changes are as follows:

• Location to be renamed to ReadCost to clarify the cost of the trade-off begin considered. Instead of an enum, it will be an integer to indicate the cost.
• Persistence, History and ReadCost will be defined as Capability. The backend will have a defined set of capabilities, a volume which is an instantiation of the backend will have a subset of the backend capabilities, and the storage configuration should be a subset of the volume capabilities.
• ReadCost will be part of VolumeConfig and Persistence and History will be part of StorageConfig.