Jetstream kv store - Prefix search / Wildcard search

[codeKrowe]

Hi,

Are there plans to support wild card searching of keys in the Jetstream kv store?

For example if these are my keys, I want to be able to pass a prefix to either the Keys() or the Get() method

my_store/foo/a
my_store/foo/b
my_store/foo/c

my_store/bar/a
my_store/bar/b
my_store/bar/c

So using Get("my_store/foo/") would give me

my_store/foo/a
my_store/foo/b
my_store/foo/c

At the moment, I use the Keys() method and then filter out results.

Thanks!

[derekcollison]

If you use '.' instead in your key name that would present as different tokens to NATS and you can use wildcards to filter there.

So if I add the following to a simple KV..

> nats kv add dkv
> nats kv put dkv foo.bar HELLO
> nats kv put dkv foo.baz HELLO
> nats kv put dkv bar.bar HELLO
> nats kv put dkv bar.baz HELLO

I can then attach a consumer and use wildcards.

> nats consumer add KV_dkv
? Consumer name d
? Delivery target (empty for Pull Consumers)
? Start policy (all, new, last, subject, 1h, msg sequence) all
? Acknowledgement policy explicit
? Replay policy instant
? Filter Stream by subject (blank for all) $KV.dkv.foo.*
? Maximum Allowed Deliveries -1
? Maximum Acknowledgements Pending 0
? Deliver headers only without bodies No
? Add a Retry Backoff Policy No

> nats consumer next KV_dkv d
[11:51:55] subj: $KV.dkv.foo.bar / tries: 1 / cons seq: 1 / str seq: 1 / pending: 1

HELLO

Acknowledged message

> nats consumer next KV_dkv d
[11:51:59] subj: $KV.dkv.foo.baz / tries: 1 / cons seq: 2 / str seq: 2 / pending: 0

HELLO

[ripienaar]

That's essentially a watch that you terminate once caught up - watch already support key ranges.

[codeKrowe]

That's great, thank you!

[HeavyHorst]

I tried this and noticed that the performance degenerates a lot when there are a lot of KVs.
I have added 3 million entries (just experimenting with the KV store atm) like: main.User.2999706 and 10 entries like main.Person.2999706.

I used a watcher like this:

	watcher, err := kv.Watch(main.Person.*", nats.IgnoreDeletes())
	if err != nil {
		return err
	}
	defer watcher.Stop()

	for entry := range watcher.Updates() {
		if entry == nil {
			break
		}
                ...
        }

This gives me the 10 entries in ~400ms on my system.

This Method https://github.com/nats-io/nats-server/blob/main/server/filestore.go#L1771 seems to be iterating over all subjects and then filters out all that don't match the wildcards.

If i only add 10 entries the watcher completes in 754.831µs.

[derekcollison]

What server version?

[HeavyHorst]

nats-server: v2.9.16-RC.8 compiled from master a few minutes ago :)

[derekcollison]

Is the KV file based and if so what is your disk subsystem look like?

[HeavyHorst]

Yes, file based.
Disk is a 1TB Crucial NVME SSD.

nvme0n1 931,5G CT1000P2SSD8
according to lsblk.

Disk is formatted with ext4.

[derekcollison]

We will be looking to make more improvements for 2.10 release around KV, especially with interior delete management but also KV watchers setup and I will check this one as well.

If you want to share the underlying stream by doing a snapshot we can use the test data as we work on improvements now that we are getting 2.9.16 out the door.

[HeavyHorst]

Sounds great!

Any preferences how i should send you the snapshot? It is too large to upload here .

[HeavyHorst]

for what it's worth:

I experimented a little bit and changed the msgBlock fss data structure from a map (map[string]*SimpleState) to a btree (*btree.Map[string, *SimpleState]) so that it is possible to iterate over a prefix efficiently.

As long as the fss data is cached/in memory this is reasonably efficient and creating the same watcher as above (watcher, err := kv.Watch(main.Person.*", nats.IgnoreDeletes())) takes around 1ms to get the 10 values instead of 400ms.

This doesn't help really because the data is only cached for around 5s it seems but maybe its interesting nonetheless.

You can find my experiment here: HeavyHorst/nats-server@d059195

[derekcollison]

We have plans to use a sublist (patricia tree) in 2.10, so you were on the right path, thanks.

[HeavyHorst]

I think this hasn't made it to the latest 2.10 release?
No problem, just wanted to make sure its expected that this has not improved yet.

[gabel]

Any code / PR reference for the change to track its release?

[derekcollison]

You can put it in an object store on demo.nats.io if you want.

[HeavyHorst]

Of course :)

nats --context demo object ls discussions_957
╭──────────────────────────────────────────────────────╮
│ Bucket Contents │
├─────────────────┬────────┬───────────────────────────┤
│ Name │ Size │ Time │
├─────────────────┼────────┼───────────────────────────┤
│ snapshot.tar.xz │ 62 MiB │ 2023-04-17T16:14:18+02:00 │
│ demo.go │ 611 B │ 2023-04-17T16:17:24+02:00 │
╰─────────────────┴────────┴───────────────────────────╯

The digest/hashsum of the archive is: Digest: SHA-256 d7eca983d0aaf19657b6b7e8b107ce884e3784adaba52bdf1e769e280f78