K2V PollRange, version 2 #471

Merged

lx merged 18 commits from k2v-watch-range-2 into main 2023-01-26 16:19:05 +00:00

Conversation 0 Commits 18 Files changed 23 +1125 -198

lx commented 2023-01-10 09:36:22 +00:00

Owner

Copy link

This PR is the second proposal of an implementation of PollRange for K2V, and the one we will keep.

The hard part with implementing this new endpoint is that we need to define a "seen marker" type, which is compact enough but yet transmits enough information so that items that have already been seen will not be retransmitted upon further PollRange call, but most importantly, that items will never be missed, which could happen for example if they arrive out of order at the various storage nodes (because we do not have something like causal-order delivery).

The first version, which we abandonned, required to store the history of all K2V operations in a dedicated history table. This provided a seen marker that is just a vector clock (like an item's causality token), but it is too costly server side, so we developped this version 2, which reports the cost on the caller of PollRange. The "seen marker" type can be bigger in some cases, because it is a vector clock + a set of causality tokens for items not covered by the vector clock, but no further complexity on the server side is needed (except one thing: we made k2v timestamps globally increasing on each node, which requires to reinforce the transactional nature of K2V insertions).

• Subscription to ranges and not just items
• Make item timestamps globally increasing on each node
• Type for a range "seen marker"
  • Definition
  • Helper functions to mark new things as seen
  • Serialization with rmp+zstd+base64
• PollRange RPC
• PollRange API endpoint
  • Specification
  • Implementation
• API client
• Tests

This PR is the second proposal of an implementation of PollRange for K2V, and the one we will keep. The hard part with implementing this new endpoint is that we need to define a "seen marker" type, which is compact enough but yet transmits enough information so that items that have already been seen will not be retransmitted upon further PollRange call, but most importantly, that items will never be missed, which could happen for example if they arrive out of order at the various storage nodes (because we do not have something like causal-order delivery). The first version, which we abandonned, required to store the history of all K2V operations in a dedicated history table. This provided a seen marker that is just a vector clock (like an item's causality token), but it is too costly server side, so we developped this version 2, which reports the cost on the caller of PollRange. The "seen marker" type can be bigger in some cases, because it is a vector clock + a set of causality tokens for items not covered by the vector clock, but no further complexity on the server side is needed (except one thing: we made k2v timestamps globally increasing on each node, which requires to reinforce the transactional nature of K2V insertions). - [x] Subscription to ranges and not just items - [x] Make item timestamps globally increasing on each node - [x] Type for a range "seen marker" - [x] Definition - [x] Helper functions to mark new things as seen - [x] Serialization with rmp+zstd+base64 - [x] PollRange RPC - [x] PollRange API endpoint - [x] Specification - [x] Implementation - [x] API client - [x] Tests

lx added 1 commit 2023-01-10 09:36:23 +00:00

K2V: Subscription to ranges of items a48e2e0cb2

lx force-pushed k2v-watch-range-2 from be152c2dae to 9f5419f465 2023-01-10 10:03:57 +00:00 Compare

lx added 1 commit 2023-01-10 11:00:10 +00:00

Type definition for range seen marker 789540ca37

lx added 1 commit 2023-01-10 11:54:36 +00:00

PollRange RPC 43fd6c1526

lx force-pushed k2v-watch-range-2 from ed3e44c34e to ba00e81a42 2023-01-10 13:59:25 +00:00 Compare

lx force-pushed k2v-watch-range-2 from ba00e81a42 to 8bf06e0ba6 2023-01-10 14:06:48 +00:00 Compare

lx force-pushed k2v-watch-range-2 from 8bf06e0ba6 to 57eabe7879 2023-01-10 14:22:23 +00:00 Compare

lx added 1 commit 2023-01-10 14:22:35 +00:00

Implement PollRange API endpoint b83517d521

lx added 1 commit 2023-01-11 09:05:00 +00:00

PollRange integration test de1111076b

lx force-pushed k2v-watch-range-2 from 01a948edc4 to 32aab06929 2023-01-11 10:14:35 +00:00 Compare

lx added 1 commit 2023-01-11 10:35:48 +00:00

Lock once for insert_many 09a3dad0f2

lx added 1 commit 2023-01-11 11:03:37 +00:00

PollRange: return immediately if no seen marker is provided ba384e61c0

lx added 1 commit 2023-01-11 11:27:35 +00:00

Correctly return bad requests when seeh marker is invalid bba13f40fc

lx added 1 commit 2023-01-11 14:03:25 +00:00

PollRange & PollItem: min timeout = 1 sec cbfae673e8

lx added 1 commit 2023-01-11 14:17:40 +00:00

Poll cleanup 5b5ca63cf6

lx added 1 commit 2023-01-11 14:20:00 +00:00

add precision in pollrange doc 399f137fd0

lx added 1 commit 2023-01-11 15:13:47 +00:00

PollRange: add extra RPC delay after quorum is achieved, ... 638c5a3ce0

to give a chance to the 3rd node to respond

lx changed title from WIP: K2V PollRange, version 2 to K2V PollRange, version 2 2023-01-11 15:27:36 +00:00

lx added 1 commit 2023-01-11 16:09:45 +00:00

Merge branch 'main' into k2v-watch-range-2 dac254a6e7

lx added 1 commit 2023-01-26 15:46:47 +00:00

Merge branch 'main' into k2v-watch-range-2 590a0a8450

lx added 1 commit 2023-01-26 16:06:14 +00:00

fix clippy 1dff62564f

lx merged commit 246f7468cd into main 2023-01-26 16:19:05 +00:00

lx referenced this pull request from a commit 2023-01-26 16:19:05 +00:00

Merge pull request 'K2V PollRange, version 2' (#471) from k2v-watch-range-2 into main

lx referenced this pull request 2023-05-09 09:56:54 +00:00

K2V range watch and range diff #412

Sign in to join this conversation.

Reviewers

No reviewers

Labels

Clear labels   

action

check-aws

The behaviour should be checked against AWS S3

  

action

discussion-needed

We need to discuss if the feature is desirable and/or better specify the envisioned behavior or technical implementation

  

action

for-external-contributors

Core team does not plan working on this in the near future however an external contribution will be reviewed & merged

  

action

for-newcomers

An issue that should be newcomer friendly.

  

action

more-info-needed

More information is needed to investigate this issue

  

action

need-funding

This issue represents lots of work, we need to find money to pay our core team work

  

action

triage-required

It's not very clear what we want to do with this issue yet, more thoughts is required

  

kind

correctness

Issues of theoretical correctness that may impact edge-case scenarios

  

kind

ideas

For abstract ideas/proposal to make Garage better, to better communicate our not yet achieved aims

  

kind

improvement

Feature requests that do not fall in other categories

  

kind

performance

Deceptive performance observed OR idea to improve performances

  

kind

testing

Functional tests, integration tests, Jepsen, etc.

  

kind

usability

Propositions to make Garage easier to operate, by improving error reporting, CLI, etc.

  

kind

wrong-behavior

Unintended behavior

  

prio

critical

Could impact integrity or availability of production clusters

  

prio

low

For issues that we don't want to spend time on until made absolutely necessary

  

scope

admin-api

Issues concerning the administration API

  

scope

background-healing

Background healing covers repair tasks, anti-entropy, merkle trees, etc. ; everything related to replicating data appropriately.

  

scope

build

Issues with Nix, Drone, Rust Compiler, etc.

  

scope

documentation

  

scope

k8s

Kubernetes related, including Helm Charts

  

scope

layout

Linked to the cluster layout and storage management

  

scope

metadata

Metadata Engine (LMDB, sqlite, etc.)

  

scope

ops

Operations related to operations/maintenance issue, tooling related (like CLI missing info ; impossible, too dangerous, too complicated migration, etc.)

  

scope

rpc

Linked to RPC

  

scope

s3-api

Related to the S3 API (especially compatibility issues).

  

scope

security

Cryptography-related, auth-related, authorization-related issues

  

scope

telemetry

OpenTelemetry (traces, metrics, etc.)

No labels

action

check-aws

action

discussion-needed

action

for-external-contributors

action

for-newcomers

action

more-info-needed

action

need-funding

action

triage-required

kind

correctness

kind

ideas

kind

improvement

kind

performance

kind

testing

kind

usability

kind

wrong-behavior

prio

critical

prio

low

scope

admin-api

scope

background-healing

scope

build

scope

documentation

scope

k8s

scope

layout

scope

metadata

scope

ops

scope

rpc

scope

s3-api

scope

security

scope

telemetry

Milestone

Clear milestone

No items

No milestone

Projects

Clear projects

No items

No project

Assignees

Clear assignees

No assignees

1 participant

Notifications

Subscribe

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference: Deuxfleurs/garage#471

No description provided.