Deuxfleurs/garage
34
65
Fork 83
Code Issues95 Pull requests16 Releases32 Wiki Activity

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

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
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
lx added 1 commit 2023-01-10 11:54:36 +00:00
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
lx added 1 commit 2023-01-11 09:05:00 +00:00
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
lx added 1 commit 2023-01-11 11:03:37 +00:00
lx added 1 commit 2023-01-11 11:27:35 +00:00
lx added 1 commit 2023-01-11 14:03:25 +00:00
lx added 1 commit 2023-01-11 14:17:40 +00:00
lx added 1 commit 2023-01-11 14:20:00 +00:00
lx added 1 commit 2023-01-11 15:13:47 +00:00 
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
lx added 1 commit 2023-01-26 15:46:47 +00:00
lx added 1 commit 2023-01-26 16:06:14 +00:00
lx merged commit 246f7468cd into main 2023-01-26 16:19:05 +00:00
Sign in to join this conversation.
No reviewers
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/experimental
kind
ideas
kind
improvement
kind
performance
kind
testing
kind
usability
kind
wrong-behavior
prio
critical
prio
low
scope
admin-api
scope
admin-sdk
scope
background-healing
scope
build
scope
documentation
scope
k8s
scope
layout
scope
metadata
scope
ops
scope
rpc
scope
s3-api
scope
security
scope
telemetry
No milestone
No project
No assignees
1 participant
Notifications
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.
Delete branch "k2v-watch-range-2"

Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?