First implementation of K2V (#293)

**Specification:**

View spec at [this URL](https://git.deuxfleurs.fr/Deuxfleurs/garage/src/branch/k2v/doc/drafts/k2v-spec.md)

- [x] Specify the structure of K2V triples
- [x] Specify the DVVS format used for causality detection
- [x] Specify the K2V index (just a counter of number of values per partition key)
- [x] Specify single-item endpoints: ReadItem, InsertItem, DeleteItem
- [x] Specify index endpoint: ReadIndex
- [x] Specify multi-item endpoints: InsertBatch, ReadBatch, DeleteBatch
- [x] Move to JSON objects instead of tuples
- [x] Specify endpoints for polling for updates on single values (PollItem)

**Implementation:**

- [x] Table for K2V items, causal contexts
- [x] Indexing mechanism and table for K2V index
- [x] Make API handlers a bit more generic
- [x] K2V API endpoint
- [x] K2V API router
- [x] ReadItem
- [x] InsertItem
- [x] DeleteItem
- [x] PollItem
- [x] ReadIndex
- [x] InsertBatch
- [x] ReadBatch
- [x] DeleteBatch

**Testing:**

- [x] Just a simple Python script that does some requests to check visually that things are going right (does not contain parsing of results or assertions on returned values)
- [x] Actual tests:
  - [x] Adapt testing framework
  - [x] Simple test with InsertItem + ReadItem
  - [x] Test with several Insert/Read/DeleteItem + ReadIndex
  - [x] Test all combinations of return formats for ReadItem
  - [x] Test with ReadBatch, InsertBatch, DeleteBatch
  - [x] Test with PollItem
  - [x] Test error codes
- [ ] Fix most broken stuff
  - [x] test PollItem broken randomly
  - [x] when invalid causality tokens are given, errors should be 4xx not 5xx

**Improvements:**

- [x] Descending range queries
  - [x] Specify
  - [x] Implement
  - [x] Add test
- [x] Batch updates to index counter
- [x] Put K2V behind `k2v` feature flag

Co-authored-by: Alex Auvolat <alex@adnab.me>
Reviewed-on: https://git.deuxfleurs.fr/Deuxfleurs/garage/pulls/293
Co-authored-by: Alex <alex@adnab.me>
Co-committed-by: Alex <alex@adnab.me>

1 files changed, 141 insertions, 0 deletions

diff --git a/src/garage/tests/k2v/errorcodes.rs b/src/garage/tests/k2v/errorcodes.rs
new file mode 100644
index 00000000..2fcc45bc
--- /dev/null
+++ b/src/garage/tests/k2v/errorcodes.rs
@@ -0,0 +1,141 @@
+use crate::common;
+
+use hyper::Method;
+
+#[tokio::test]
+async fn test_error_codes() {
+	let ctx = common::context();
+	let bucket = ctx.create_bucket("test-k2v-error-codes");
+
+	// Regular insert should work (code 200)
+	let res = ctx
+		.k2v
+		.request
+		.builder(bucket.clone())
+		.method(Method::PUT)
+		.path("root")
+		.query_param("sort_key", Some("test1"))
+		.body(b"Hello, world!".to_vec())
+		.send()
+		.await
+		.unwrap();
+	assert_eq!(res.status(), 200);
+
+	// Insert with trash causality token: invalid request
+	let res = ctx
+		.k2v
+		.request
+		.builder(bucket.clone())
+		.method(Method::PUT)
+		.path("root")
+		.query_param("sort_key", Some("test1"))
+		.signed_header("x-garage-causality-token", "tra$sh")
+		.body(b"Hello, world!".to_vec())
+		.send()
+		.await
+		.unwrap();
+	assert_eq!(res.status(), 400);
+
+	// Search without partition key: invalid request
+	let res = ctx
+		.k2v
+		.request
+		.builder(bucket.clone())
+		.query_param("search", Option::<&str>::None)
+		.body(
+			br#"[
+	{},
+		]"#
+			.to_vec(),
+		)
+		.method(Method::POST)
+		.send()
+		.await
+		.unwrap();
+	assert_eq!(res.status(), 400);
+
+	// Search with start that is not in prefix: invalid request
+	let res = ctx
+		.k2v
+		.request
+		.builder(bucket.clone())
+		.query_param("search", Option::<&str>::None)
+		.body(
+			br#"[
+	{"partition_key": "root", "prefix": "a", "start": "bx"},
+		]"#
+			.to_vec(),
+		)
+		.method(Method::POST)
+		.send()
+		.await
+		.unwrap();
+	assert_eq!(res.status(), 400);
+
+	// Search with invalid json: 400
+	let res = ctx
+		.k2v
+		.request
+		.builder(bucket.clone())
+		.query_param("search", Option::<&str>::None)
+		.body(
+			br#"[
+	{"partition_key": "root"
+		]"#
+			.to_vec(),
+		)
+		.method(Method::POST)
+		.send()
+		.await
+		.unwrap();
+	assert_eq!(res.status(), 400);
+
+	// Batch insert with invalid causality token: 400
+	let res = ctx
+		.k2v
+		.request
+		.builder(bucket.clone())
+		.body(
+			br#"[
+	{"pk": "root", "sk": "a", "ct": "tra$h", "v": "aGVsbG8sIHdvcmxkCg=="}
+		]"#
+			.to_vec(),
+		)
+		.method(Method::POST)
+		.send()
+		.await
+		.unwrap();
+	assert_eq!(res.status(), 400);
+
+	// Batch insert with invalid data: 400
+	let res = ctx
+		.k2v
+		.request
+		.builder(bucket.clone())
+		.body(
+			br#"[
+	{"pk": "root", "sk": "a", "ct": null, "v": "aGVsbG8sIHdvcmx$Cg=="}
+		]"#
+			.to_vec(),
+		)
+		.method(Method::POST)
+		.send()
+		.await
+		.unwrap();
+	assert_eq!(res.status(), 400);
+
+	// Poll with invalid causality token: 400
+	let res = ctx
+		.k2v
+		.request
+		.builder(bucket.clone())
+		.path("root")
+		.query_param("sort_key", Some("test1"))
+		.query_param("causality_token", Some("tra$h"))
+		.query_param("timeout", Some("10"))
+		.signed_header("accept", "application/octet-stream")
+		.send()
+		.await
+		.unwrap();
+	assert_eq!(res.status(), 400);
+}