Skip to main content

OrderedMap

A larger than memory map / dictionary, sorted by its keys. It supports insertion, removal, sorted range queries, and point-lookup queries.

Keys are strings and can be associated with a Value, bytes, or Any object when inserted into an OrderedMap.

  • Value represents a dynamically typed value which can be either null, a number, a string, a boolean, a recursive struct value, or a list of values. A producer of a Value is expected to set one of these variants; the absence of any variant indicates an error. This type is meant to represent all possible JSON values.
  • bytes is used to store a string of bytes.
  • Any wraps a protobuf message, for code that already has one.

OrderedMaps are frequently used to create indexes of other state types, but can also be used to efficiently store large collections of primitive values.

For example:

  • To index a data type in its natural state-ID order, you can create a OrderedMap with the type's ID as keys and empty values. This is effectively a sorted set.
  • To index a data type by creation time, you can use time-ordered UUIDs (such as UUIDv1 or UUIDv7) as keys and the data type's state-ID as values.
  • To store a large collection of records, you can use a key of your choice and each record, serialized, as a value.

To use an OrderedMap in your application, you typically want to choose an ID for the map and store it somewhere (e.g., as a field in the appropriate state data type). To use the map, first get a ref() to the map using its ID and then invoke the appropriate operations. The map will be implicitly constructed when the first writer method is invoked (e.g., insert()) or can be explicitly constructed with create().

Imports and set up​

To use an OrderedMap, import the library where you would like to use it.

from reboot.std.collections.ordered_map.v1.ordered_map import OrderedMap

Also make sure to include the OrderedMap library when starting up your Application. (Note: this import is different from above.)

from reboot.std.collections.ordered_map.v1.ordered_map import ordered_map_library

async def main():
    application = Application(
        servicers=[MyServicer],
        libraries=[ordered_map_library()],
    ).run()

Authorizer​

By default, OrderedMap allows internal calls from the application to the library. However, this can be overridden by providing your own authorizer.

authorizer = OrderedMap.Authorizer(
    insert=allow_if(all=[is_app_internal]),
    search=allow(),
)

application = Application(
    servicers=[MyServicer],
    libraries=[ordered_map_library(authorizer=authorizer)],
)

OrderedMap​

Each OrderedMap you create will need a unique ID. Using a reference to that OrderedMap, you will be able to perform operations on keys and associated data.

Getting a reference​

This creates a reference to an OrderedMap with ID "my-map".

my_map = OrderedMap.ref("my-map")

Methods​

Create​

An optional call to create an ordered map with construction options.

  • degree specifies the maximum number of continuously stored items per node (an OrderedMap is implemented as a B+Tree, so increasing degree will decrease the total depth of the tree). Note that this defaults to 128 if the map is implicitly created via insert.
  • maintain_size controls whether the map tracks the total number of entries. When true, total_size is returned in range responses, but every insert and remove requires a write to the root — which serializes all mutations. When false (default), mutations to different parts of the tree can execute concurrently.

create is idempotent: calling it multiple times with the same options is a no-op. Calling it with different options after the map has been created will raise a StateAlreadyConstructed error.

By default, OrderedMaps are implicitly created on the first insert call. create is only necessary to override defaults or to ensure the map exists before reading.

await my_map.create(
    context,
    degree=128,
    maintain_size=True,
)

Insert​

Insert a key and its associated data into the OrderedMap.

You can optionally pass degree and maintain_size to insert(). On the first insert() (when the map does not yet exist), these are used as construction options — equivalent to calling create first. On subsequent insert calls, if set, they are validated to match the existing configuration. Note that you do not have to pass the options after the map has been constructed, but this pattern is useful when you don't know whether the map has been created or not and you want to ensure the correct options get applied upon implicit construction.

# Implicitly creates with degree=64 if not yet
# created, or validates that the existing map
# was created with degree=64.
await my_map.insert(
    context,
    key="key-a",
    value=from_str("a value!"),
    degree=64,
)

Keys which are already in the map will be overwritten.

Only one of value, bytes, or any can be set.

The examples below show the different ways data can be associated with a key, but in practice, you should use a uniform structure for your value. For more information on how to format data, check out the Value and Any docs for Items.

from reboot.protobuf import as_str

await my_map.insert(
    context,
    key="key-a",
    value=from_str("a value!"),
)

await my_map.insert(
    context,
    key="key-b",
    bytes=b"some bytes",
)

await my_map.insert(
    context,
    key="key-c",
    any=<Any>,
)

Bulk Insert​

Insert many key-value pairs in a single call using the entries parameter. This is significantly more efficient than inserting keys one at a time because the entries are merged and dispatched through the tree concurrently.

Keys which are already in the map will be overwritten. When using entries, the single-key fields (key, value, bytes, any) must all be unset.

Each entry's value is specified as an Item.

from rbt.std.item.v1.item_pb2 import Item
from reboot.protobuf import from_str

await my_map.insert(
    context,
    entries={
        "key-a": Item(value=from_str("a value!")),
        "key-b": Item(bytes=b"some bytes"),
    },
)

Search for whether a given key is in the OrderedMap.

Returns whether or not the key exists. If the key exists, this will also return the associated Value, bytes, or Any.

# Search for key with associated `Value`.
response = await my_map.search(context, key="key-a")
print(response.value)

# Search for key with associated `bytes`.
response = await my_map.search(context, key="key-b")
print(response.bytes)

# Search for key with associated `Any`.
response = await my_map.search(context, key="key-c")
print(response.any)

# Search for key with no associated data.
missing_response = await my_map.search(context, key="missing-key")
assert missing_response.found == False

Remove​

Remove a key and its associated data from the OrderedMap.

Any key that is not present will be ignored.

await my_map.remove(context, key="key-a")

Bulk Remove​

Remove many keys in a single call using the keys parameter. This is significantly more efficient than removing keys one at a time because the removals are dispatched through the tree concurrently.

Keys that are not present are silently ignored. When using keys, the single-key key field must be unset.

await my_map.remove(
    context,
    keys=["key-a", "key-b", "key-c"],
)

Range​

Read a range of data in ascending key order from the OrderedMap.

You can optionally specify a start_key (Python) / startKey (TypeScript) to limit the lower bound (inclusive) of the returned entries. If start_key (Python) / startKey (TypeScript) is not set, the range will start from the smallest key.

You will receive up to limit items in the response. The limit argument is always required to avoid exhausting memory in the client or server.

This returns entries that have a key and one of value, bytes, or any set dependent on how you inserted the data.

range1 = await my_map.range(
    context,
    start_key="key-b",
    limit=2,
)

for entry in range1.entries:
    print(entry.key, entry.value, entry.bytes, entry.any)

# Returns entries associated with the 3 smallest keys.
range2 = await my_map.range(context, limit=3)

If you have an error in your range request (i.e. you don't specify a limit), you'll receive an InvalidRangeError explaining why your range is not valid.

Reverse Range​

Read a range of data in descending key order from the OrderedMap. This is similar to range but reads data in reverse order.

You can optionally specify a start_key (Python) / startKey (TypeScript) to limit the upper bound (inclusive) of the returned entries. If start_key (Python) / startKey (TypeScript) is not set, the range will start from the largest key.

You will receive up to limit items in the response. The limit argument is always required to avoid exhausting memory in the client or server.

This returns entries that have a key and one of value, bytes, or any set dependent on how you inserted the data.

range1 = await my_map.reverse_range(
    context,
    start_key="key-z",
    limit=2,
)

for entry in range1.entries:
    print(entry.key, entry.value, entry.bytes, entry.any)

# Returns entries associated with the 3 largest keys.
range2 = await my_map.reverse_range(context, limit=3)

If you have an error in your range request (i.e. you don't specify a limit), you'll receive an InvalidRangeError explaining why your range is not valid.

Errors​

InvalidRangeError​

See range and reverse_range/reverseRange. Raised when the requested range is not valid.

The message field of the error contains the string explaining why the range is not valid.

from reboot.std.collections.ordered_map.v1.ordered_map import (
    InvalidRangeError,
    OrderedMap,
)

try:
    await my_map.range(context)
except OrderedMap.RangeAborted as e:
    # isinstance(e.error, InvalidRangeError) == True
    print(e.error.message)

React​

Once you've set up your React app to call into your Reboot API, you can also use OrderedMap directly from your React app.

First, on your backend, you will need to override the authorizer to allow calls from your frontend directly to OrderedMap methods.

Second, add @reboot-dev/reboot-std-api to your package.json.

npm install -S @reboot-dev/reboot-std-api

Third, import the React library for OrderedMap in your React app.

import { useOrderedMap } from "@reboot-dev/reboot-std-api/collections/ordered_map/v1/ordered_map_rbt_react.js";

Then, you can access your OrderedMap. For example, you can call a writer method, such as insert():

const map = useOrderedMap({ id: "my-map" });

const handleClick = () => {
  map.insert({ key: "my-key", value: Value.fromJson("new value") });
};

return (
  <button id="button" onClick={handleClick}>
    Insert New Value
  </button>
);

Or a reader, such as search():

const map = useOrderedMap({ id: "my-map" });

const { aborted, response } = map.useSearch({ key: "my-key" });

if (aborted !== undefined) {
  return <div id="error">Errored while searching.</div>;
} else if (response === undefined) {
  return <div id="loading">Loading...</div>;
} else if (!response.found) {
  return <div id="not-found">Not found</div>;
} else {
  return <div id="map-value">{response.value?.toJson() as string}</div>;
}

See Call your API from React to learn more about how to call methods from React.