NLnet task 3 #667

Merged

lx merged 60 commits from nlnet-task3 into next-0.10 2024-01-11 10:58:08 +00:00

Conversation 0 Commits 60 Files Changed 41 +3284 -1668

lx commented 2023-11-08 14:42:02 +00:00

Owner

Copy Link

This PR tracks the progress of NLnet task 3, fixing #495 - read-after-write consistency when layout changes.

Subtask 1 (Jepsen testing): See PR #544 for details.

• Jepsen testing was achieved
  • Without layout changes, Jepsen found no consistency anomalies
  • When introducing layout changes, anomalies began to occur

Subtask 2 (write and prove solution):

• Think of a solution.
• Write down some notes on the solution and sketch a proof.

Subtask 3 (implementation): Mostly in this PR:

• Change layout data structure to keep track of layout history and update trackers (that track the sync status of all nodes in the cluster)
• Naively adapt existing code to new layout data structures
• Add layout manager that handles update trackers
• Adapt the resync procedure to take into account the layout history, and to correctly update the update trackers
• Adapt the table read/write functions to access correct nodes given current layout history and values of update trakcers
  • Table::insert
  • Table::insert_many
  • BlockManager::rpc_put_block
• Layout ACK locking while writes are in progress
• Make sure data blocks also can still be found, since block moving is not taken into account in sync_map
• Caching of current ack and sync values in layout history / update tracker
• Adapt System::health()
• Update the CLI to make info from the update trackers visible
• Update the admin API as well
• Add a command to consider a node or set of nodes "dead" and forcibly advance the update trackers for that node

--

FIXES:

• gateways must also ack!
• improve recovery procedure when nodes are unavailable, by allowing individual node sync operations to be marked as completed in sync_map even if not all sync targets were completed successfully, as long as a quorum among all write sets was achieved
• similarly, ack_sync can progress even if not all nodes have finished a sync, as long as a quorum among all write sets of all partitions was achieved

--

• Hand testing
• Proof-reading

LEFT FOR FUTURE PRs:

• Add garage layout skip-dead-nodes equivalent to admin API?
• ack_map could be forcibly increased after a certain delay (15 minutes?), to avoid user having to call garage layout skip-dead-nodes when some nodes are unavailable
• Can GC be improved to benefit from the update trackers? See #151. Also just fix GC that is probably broken (but always has been?)
• Improve/fix/refactor K2V RPCs (for insertion and for polling)

Subtask 4 (re-testing): WIP, some is also in PR #544

• Jepsen

  • Final results: BEFORE PATCH, AFTER PATCH

This PR tracks the progress of NLnet task 3, fixing #495 - read-after-write consistency when layout changes. **Subtask 1 (Jepsen testing):** See PR #544 for details. - [x] Jepsen testing was achieved - [x] Without layout changes, Jepsen found no consistency anomalies - [x] When introducing layout changes, anomalies began to occur **Subtask 2 (write and prove solution):** - [x] Think of a solution. - [x] Write down some notes on the solution and sketch a proof. **Subtask 3 (implementation):** Mostly in this PR: - [x] Change layout data structure to keep track of layout history and update trackers (that track the sync status of all nodes in the cluster) - [x] Naively adapt existing code to new layout data structures - [x] Add layout manager that handles update trackers - [x] Adapt the resync procedure to take into account the layout history, and to correctly update the update trackers - [x] Adapt the table read/write functions to access correct nodes given current layout history and values of update trakcers - [x] Table::insert - [x] Table::insert_many - [x] BlockManager::rpc_put_block - [x] Layout ACK locking while writes are in progress - [x] Make sure data blocks also can still be found, since block moving is not taken into account in sync_map - [x] Caching of current ack and sync values in layout history / update tracker - [x] Adapt `System::health()` - [x] Update the CLI to make info from the update trackers visible - [x] Update the admin API as well - [x] Add a command to consider a node or set of nodes "dead" and forcibly advance the update trackers for that node -- FIXES: - [x] gateways must also ack! - [x] improve recovery procedure when nodes are unavailable, by allowing individual node sync operations to be marked as completed in sync_map even if not all sync targets were completed successfully, as long as a quorum among all write sets was achieved - [x] similarly, ack_sync can progress even if not all nodes have finished a sync, as long as a quorum among all write sets of all partitions was achieved -- - [x] Hand testing - [x] Proof-reading LEFT FOR FUTURE PRs: - Add `garage layout skip-dead-nodes` equivalent to admin API? - ack_map could be forcibly increased after a certain delay (15 minutes?), to avoid user having to call `garage layout skip-dead-nodes` when some nodes are unavailable - Can GC be improved to benefit from the update trackers? See #151. Also just fix GC that is probably broken (but always has been?) - Improve/fix/refactor K2V RPCs (for insertion and for polling) **Subtask 4 (re-testing):** WIP, some is also in PR #544 - [x] Jepsen - Final results: [BEFORE PATCH](https://git.deuxfleurs.fr/Deuxfleurs/garage/src/commit/fa9247f11b89c960dffe82d6bf990ed4335788e3/script/jepsen.garage/results/Results-2023-12-13-tsfix2.png), [AFTER PATCH](https://git.deuxfleurs.fr/Deuxfleurs/garage/src/commit/fa9247f11b89c960dffe82d6bf990ed4335788e3/script/jepsen.garage/results/Results-2023-12-13-task3c.png)

lx added 2 commits 2023-11-08 14:42:02 +00:00

0962313ebd

garage_rpc: reorder functions in layout.rs

12d1dbfc6b

remove Ring and use ClusterLayout everywhere

lx added 1 commit 2023-11-08 15:41:18 +00:00

4a9c94514f

avoid using layout_watch in System directly

lx added 2 commits 2023-11-08 18:28:56 +00:00

fe9af1dcaa

WIP: garage_rpc: store layout version history

8dccee3ccf

cluster layout: adapt all uses of ClusterLayout to LayoutHistory

lx added 1 commit 2023-11-08 18:31:17 +00:00

1da0a5676e

bump garage protocol version tag to 0x000A (0.10)

lx added 1 commit 2023-11-09 10:20:06 +00:00

523d2ecb95

layout: use separate CRDT for staged layout changes

lx added 1 commit 2023-11-09 11:55:58 +00:00

8a2b1dd422

wip: split out layout management from System into separate LayoutManager

lx added 2 commits 2023-11-09 13:12:22 +00:00

19ef1ec8e7

layout: more refactoring

bfb1845fdc

layout: refactor to use a RwLock on LayoutHistory

lx added 1 commit 2023-11-09 13:53:54 +00:00

94caf9c0c1

layout: separate code path for synchronizing update trackers only

lx added 1 commit 2023-11-09 14:32:17 +00:00

03ebf18830

layout: begin managing the update tracker values

lx added 1 commit 2023-11-09 14:42:29 +00:00

bad7cc812e

layout admin: add missing calls to update_hash

lx added 1 commit 2023-11-09 14:53:00 +00:00

9d95f6f704

layout: fix tracker bugs

lx changed title from WIP: NLnet task 3 to WIP: NLnet task 3 subtask 3 (implementation) 2023-11-09 14:54:11 +00:00

lx added 1 commit 2023-11-09 15:32:50 +00:00

df36cf3099

layout: add helpers to LayoutHistory and prepare integration with Table

lx added 1 commit 2023-11-11 11:08:56 +00:00

ce89d1ddab

table sync: adapt to new layout history

lx force-pushed nlnet-task3 from 0f319a1c04 to df24bb806d 2023-11-11 11:44:34 +00:00 Compare

lx added 1 commit 2023-11-11 12:11:16 +00:00

9a491fa137

layout: fix test

lx added 1 commit 2023-11-14 11:48:56 +00:00

8e292e06b3

layout: some refactoring of nongateway nodes

lx force-pushed nlnet-task3 from 74109c699e to 1aab1f4e68 2023-11-14 12:12:41 +00:00 Compare

lx added 1 commit 2023-11-14 12:29:40 +00:00

83a11374ca

layout: fixes in schema

lx added 2 commits 2023-11-14 13:28:36 +00:00

866196750f

system: add todo wrt new layout

3b361d2959

layout: prepare for write sets

lx added 1 commit 2023-11-14 14:41:13 +00:00

90e1619b1e

table: take into account multiple write sets in inserts

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

7ef2c23120

layout: fix test

lx added 1 commit 2023-11-15 11:16:24 +00:00

b3e729f4b8

layout history merge: rm invalid versions when valid versions are added

lx added 2 commits 2023-11-15 12:07:56 +00:00

46007bf01d

integration test: print stdout and stderr on subcommand crash

acd49de9f9

rpc: fix write set quorums

lx added 2 commits 2023-11-15 13:21:24 +00:00

65066c7064

layout: wip cache global mins

393c4d4515

layout: add helper for cached/external values to centralize recomputation

lx added 1 commit 2023-11-15 14:40:58 +00:00

33c8a489b0

layou: implement ack locking

lx added 1 commit 2023-11-15 14:57:10 +00:00

d4df03424f

layout: fix test

lx added 1 commit 2023-11-16 12:27:04 +00:00

ad5c6f779f

layout: split helper in separate file; more precise difference tracking

lx added 1 commit 2023-11-16 12:52:09 +00:00

707442f5de

layout: refactor digests and add "!=" assertions before epidemic bcast

lx added 2 commits 2023-11-16 15:42:00 +00:00

22f38808e7

rpc_helper: don't use tokio::spawn for individual requests

3ecd14b9f6

table: implement write sets for insert_many

lx changed title from WIP: NLnet task 3 subtask 3 (implementation) to WIP: NLnet task 3 2023-11-16 15:43:39 +00:00

lx added 1 commit 2023-11-27 10:53:32 +00:00

d6d239fc79

block manager: read_block using old layout versions if necessary

lx added 1 commit 2023-11-27 11:10:46 +00:00

78362140f5

rpc: update system::health to take into account write sets for all partitions

lx added 1 commit 2023-11-27 12:19:18 +00:00

539a920313

cli: show when nodes are draining metadata

lx force-pushed nlnet-task3 from a081e74bd7 to c539077d30 2023-11-27 15:22:34 +00:00 Compare

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

539af6eac4

rpc helper: write comments + small refactoring of tracing

lx added 1 commit 2023-11-28 13:25:21 +00:00

c04dd8788a

admin: more info in admin GetClusterStatus

lx added 1 commit 2023-12-07 09:30:52 +00:00

c8356a91d9

layout updates: fix the set of nodes among which minima are calculated

lx force-pushed nlnet-task3 from 9358658cc5 to 95eb13eb08 2023-12-07 09:57:29 +00:00 Compare

lx added 1 commit 2023-12-07 10:27:47 +00:00

d90de365b3

table sync: use write quorums to report global success or failure of sync

lx added 1 commit 2023-12-07 10:56:22 +00:00

aa59059a91

layout cli: safer skip-dead-nodes command

lx force-pushed nlnet-task3 from 2b93daa78d to 9cecea64d4 2023-12-07 13:51:31 +00:00 Compare

lx added 1 commit 2023-12-07 14:16:15 +00:00

431b28e0cf

fix build with discovery features

lx added 1 commit 2023-12-08 09:36:53 +00:00

91b874c4ef

rpc: fix system::health

lx added 1 commit 2023-12-08 10:24:50 +00:00

7f2541101f

cli: improvements to the layout commands when multiple layouts are live

lx added 1 commit 2023-12-08 10:51:13 +00:00

063294dd56

layout version: refactor get_node_zone

lx added 1 commit 2023-12-08 11:03:07 +00:00

5dd200c015

layout: move block_read_nodes_of to rpc_helper to avoid double-locking ...

(in theory, this could have caused a deadlock)

lx added 1 commit 2023-12-08 11:18:26 +00:00

64a6e557a4

rpc helper: small refactorings

lx added 1 commit 2023-12-08 13:16:06 +00:00

4dbf254512

layout: refactoring, merge two files

lx added 1 commit 2023-12-08 13:54:32 +00:00

f8df90b79b

table: fix insert_many to not send duplicates

lx added 1 commit 2023-12-11 13:58:07 +00:00

e4f493b481

table: remove redundant tracing in insert_many

lx added 1 commit 2023-12-11 14:32:03 +00:00

85b5a6bcd1

fix some clippy lints

lx added 1 commit 2023-12-11 14:46:50 +00:00

adccce1145

layout: refactor/fix bad while loop

lx added 1 commit 2023-12-11 15:09:47 +00:00

0041b013a4

layout: refactoring and fix in layout helper

lx changed target branch from main to next-0.10 2024-01-11 10:57:14 +00:00

lx changed title from WIP: NLnet task 3 to NLnet task 3 2024-01-11 10:57:29 +00:00

lx merged commit 8a6ec1d611 into next-0.10 2024-01-11 10:58:08 +00:00

lx deleted branch nlnet-task3 2024-01-11 10:58:09 +00:00

lx referenced this issue from a commit 2024-01-11 10:58:10 +00:00

Merge pull request 'NLnet task 3' (#667) from nlnet-task3 into next-0.10

lx referenced this pull request 2024-01-11 11:03:30 +00:00

Garage v1.0 #683

Sign in to join this conversation.

Reviewers

No reviewers

Labels

Clear labels   

AdminAPI

Issues concerning the administration API

  

Bug

  

Check AWS

The behaviour should be checked against AWS S3

  

CI

Issues with Nix, Drone, Rust Compiler, etc.

  

Correctness

Issues of theoretical correctness that may impact edge-case scenarios

  

Critical

  

Documentation

  

Ideas

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

  

Improvement

  

Low priority

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

  

Newcomer

A bug that should be newcomer friendly.

  

Performance

  

S3 Compatibility

  

Testing

  

Usability

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

No Label

AdminAPI

Bug

Check AWS

CI

Correctness

Critical

Documentation

Ideas

Improvement

Low priority

Newcomer

Performance

S3 Compatibility

Testing

Usability

Milestone

Clear milestone

No items

No Milestone

Assignees

Clear assignees

No Assignees

1 Participants

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#667

No description provided.