--- a/core/storagemanager.lua	Sat Mar 18 18:20:03 2023 +0100
+++ b/core/storagemanager.lua	Tue Sep 27 17:46:27 2022 +0100
@@ -203,6 +203,37 @@
 	};
 }
 
+local combined_store_mt = {
+	__index = {
+		-- keyval
+		get = function (self, name)
+			return self.keyval_store:get(name);
+		end;
+		set = function (self, name, data)
+			return self.keyval_store:set(name, data);
+		end;
+		items = function (self)
+			return self.keyval_store:users();
+		end;
+		-- map
+		get_key = function (self, name, key)
+			return self.map_store:get(name, key);
+		end;
+		set_key = function (self, name, key, value)
+			return self.map_store:set(name, key, value);
+		end;
+		set_keys = function (self, name, map)
+			return self.map_store:set_keys(name, map);
+		end;
+		get_key_from_all = function (self, key)
+			return self.map_store:get_all(key);
+		end;
+		delete_key_from_all = function (self, key)
+			return self.map_store:delete_all(key);
+		end;
+	};
+};
+
 local open; -- forward declaration
 
 local function create_map_shim(host, store)
@@ -213,7 +244,49 @@
 	}, map_shim_mt);
 end
 
+local function open_combined(host, store)
+	local driver, driver_name = get_driver(host, store);
+
+	-- Open keyval
+	local keyval_store, err = driver:open(store, "keyval");
+	if not keyval_store then
+		if err == "unsupported-store" then
+			log("debug", "Storage driver %s does not support store %s (keyval), falling back to null driver",
+				driver_name, store);
+			keyval_store, err = null_storage_driver, nil;
+		end
+	end
+
+	local map_store;
+	if keyval_store then
+		-- Open map
+		map_store, err = driver:open(store, "map");
+		if not map_store then
+			if err == "unsupported-store" then
+				log("debug", "Storage driver %s does not support store %s (map), falling back to shim",
+					driver_name, store);
+				map_store, err = setmetatable({ keyval_store = keyval_store }, map_shim_mt), nil;
+			end
+		end
+	end
+
+	if not(keyval_store and map_store) then
+		return nil, err;
+	end
+	local combined_store = setmetatable({
+		keyval_store = keyval_store;
+		map_store = map_store;
+		remove = map_store.remove;
+	}, combined_store_mt);
+	local event_data = { host = host, store_name = store, store_type = "keyval+", store = combined_store };
+	hosts[host].events.fire_event("store-opened", event_data);
+	return event_data.store, event_data.store_err;
+end
+
 function open(host, store, typ)
+	if typ == "keyval+" then -- TODO: default in some release?
+		return open_combined(host, store);
+	end
 	local driver, driver_name = get_driver(host, store);
 	local ret, err = driver:open(store, typ);
 	if not ret then

--- a/spec/core_storagemanager_spec.lua	Sat Mar 18 18:20:03 2023 +0100
+++ b/spec/core_storagemanager_spec.lua	Tue Sep 27 17:46:27 2022 +0100
@@ -196,6 +196,136 @@
 				end);
 			end);
 
+			describe("keyval+ stores", function ()
+				-- These tests rely on being executed in order, disable any order
+				-- randomization for this block
+				randomize(false);
+
+				local store, kv_store, map_store;
+				it("may be opened", function ()
+					store = assert(sm.open(test_host, "test-kv+", "keyval+"));
+				end);
+
+				local simple_data = { foo = "bar" };
+
+				it("may set data for a user", function ()
+					assert(store:set("user9999", simple_data));
+				end);
+
+				it("may get data for a user", function ()
+					assert.same(simple_data, assert(store:get("user9999")));
+				end);
+
+				it("may be opened as a keyval store", function ()
+					kv_store = assert(sm.open(test_host, "test-kv+", "keyval"));
+					assert.same(simple_data, assert(kv_store:get("user9999")));
+				end);
+
+				it("may be opened as a map store", function ()
+					map_store = assert(sm.open(test_host, "test-kv+", "map"));
+					assert.same("bar", assert(map_store:get("user9999", "foo")));
+				end);
+
+				it("may remove data for a user", function ()
+					assert(store:set("user9999", nil));
+					local ret, err = store:get("user9999");
+					assert.is_nil(ret);
+					assert.is_nil(err);
+				end);
+
+
+				it("may set a specific key for a user", function ()
+					assert(store:set_key("user9999", "foo", "bar"));
+					assert.same(kv_store:get("user9999"), { foo = "bar" });
+				end);
+
+				it("may get a specific key for a user", function ()
+					assert.equal("bar", store:get_key("user9999", "foo"));
+				end);
+
+				it("may find all users with a specific key", function ()
+					assert.is_function(store.get_key_from_all);
+					assert(store:set_key("user9999b", "bar", "bar"));
+					assert(store:set_key("user9999c", "foo", "blah"));
+					local ret, err = store:get_key_from_all("foo");
+					assert.is_nil(err);
+					assert.same({ user9999 = "bar", user9999c = "blah" }, ret);
+				end);
+
+				it("rejects empty or non-string keys to get_all", function ()
+					assert.is_function(store.get_key_from_all);
+					do
+						local ret, err = store:get_key_from_all("");
+						assert.is_nil(ret);
+						assert.is_not_nil(err);
+					end
+					do
+						local ret, err = store:get_key_from_all(true);
+						assert.is_nil(ret);
+						assert.is_not_nil(err);
+					end
+				end);
+
+				it("rejects empty or non-string keys to delete_all", function ()
+					assert.is_function(store.delete_key_from_all);
+					do
+						local ret, err = store:delete_key_from_all("");
+						assert.is_nil(ret);
+						assert.is_not_nil(err);
+					end
+					do
+						local ret, err = store:delete_key_from_all(true);
+						assert.is_nil(ret);
+						assert.is_not_nil(err);
+					end
+				end);
+
+				it("may delete all instances of a specific key", function ()
+					assert.is_function(store.delete_key_from_all);
+					assert(store:set_key("user9999b", "foo", "hello"));
+
+					assert(store:delete_key_from_all("bar"));
+					-- Ensure key was deleted
+					do
+						local ret, err = store:get_key("user9999b", "bar");
+						assert.is_nil(ret);
+						assert.is_nil(err);
+					end
+					-- Ensure other users/keys are intact
+					do
+						local ret, err = store:get_key("user9999", "foo");
+						assert.equal("bar", ret);
+						assert.is_nil(err);
+					end
+					do
+						local ret, err = store:get_key("user9999b", "foo");
+						assert.equal("hello", ret);
+						assert.is_nil(err);
+					end
+					do
+						local ret, err = store:get_key("user9999c", "foo");
+						assert.equal("blah", ret);
+						assert.is_nil(err);
+					end
+				end);
+
+				it("may remove data for a specific key for a user", function ()
+					assert(store:set_key("user9999", "foo", nil));
+					do
+						local ret, err = store:get_key("user9999", "foo");
+						assert.is_nil(ret);
+						assert.is_nil(err);
+					end
+
+					assert(store:set_key("user9999b", "foo", nil));
+					do
+						local ret, err = store:get_key("user9999b", "foo");
+						assert.is_nil(ret);
+						assert.is_nil(err);
+					end
+				end);
+			end);
+
 			describe("archive stores", function ()
 				randomize(false);