| 1 | // 🤖 Tests for the global id allocator. Two harnesses: |
| 2 | // |
| 3 | // - memCounter: an in-memory, CAS-correct fake of the counterStore interface |
| 4 | // for the block/refill/retry LOGIC — deterministic, no HTTP. |
| 5 | // - fakeCASS3: an httptest S3 fake that speaks conditional writes (If-Match / |
| 6 | // If-None-Match → 412), driven by the REAL aws-sdk-go-v2 client via New's |
| 7 | // Endpoint override — the same fake-endpoint pattern s3blobstore_test.go |
| 8 | // uses, so the production S3 code path (conditional PutObject, ETag reads, |
| 9 | // 412 → retry) is exercised for real. The repo has no shared S3 fake with |
| 10 | // conditional-write support, so this one is scoped to exactly the CAS |
| 11 | // operations the allocator uses. |
| 12 | package idalloc |
| 13 | |
| 14 | import ( |
| 15 | "context" |
| 16 | "fmt" |
| 17 | "io" |
| 18 | "net/http" |
| 19 | "net/http/httptest" |
| 20 | "sync" |
| 21 | "testing" |
| 22 | ) |
| 23 | |
| 24 | // --- in-memory CAS fake ------------------------------------------------------ |
| 25 | |
| 26 | // memCounter is a faithful compare-and-swap over one value: a swap succeeds only |
| 27 | // if its token matches the current version, exactly like S3's ETag conditional. |
| 28 | type memCounter struct { |
| 29 | mu sync.Mutex |
| 30 | value uint64 |
| 31 | exists bool |
| 32 | ver int // bumps on every successful swap; token is "v<ver>" |
| 33 | loads int |
| 34 | swapOK int // successful swaps = blocks reserved |
| 35 | } |
| 36 | |
| 37 | func (m *memCounter) tokenLocked() string { |
| 38 | if !m.exists { |
| 39 | return "" |
| 40 | } |
| 41 | return fmt.Sprintf("v%d", m.ver) |
| 42 | } |
| 43 | |
| 44 | func (m *memCounter) load(ctx context.Context) (uint64, string, error) { |
| 45 | m.mu.Lock() |
| 46 | defer m.mu.Unlock() |
| 47 | m.loads++ |
| 48 | return m.value, m.tokenLocked(), nil |
| 49 | } |
| 50 | |
| 51 | func (m *memCounter) swap(ctx context.Context, token string, newValue uint64) (bool, error) { |
| 52 | m.mu.Lock() |
| 53 | defer m.mu.Unlock() |
| 54 | if token != m.tokenLocked() { |
| 55 | return false, nil // stale token: a competitor moved the counter first |
| 56 | } |
| 57 | m.value = newValue |
| 58 | m.exists = true |
| 59 | m.ver++ |
| 60 | m.swapOK++ |
| 61 | return true, nil |
| 62 | } |
| 63 | |
| 64 | // flakyStore wraps a memCounter and, for the first `conflicts` swaps, simulates a |
| 65 | // competitor slipping a block in between the caller's load and its swap: it |
| 66 | // advances the underlying counter and then reports the caller's write as lost. |
| 67 | // This drives the CAS-conflict retry branch deterministically. |
| 68 | type flakyStore struct { |
| 69 | inner *memCounter |
| 70 | competitorBlock uint64 |
| 71 | |
| 72 | mu sync.Mutex |
| 73 | conflicts int |
| 74 | injected int |
| 75 | } |
| 76 | |
| 77 | func (f *flakyStore) load(ctx context.Context) (uint64, string, error) { return f.inner.load(ctx) } |
| 78 | |
| 79 | func (f *flakyStore) swap(ctx context.Context, token string, newValue uint64) (bool, error) { |
| 80 | f.mu.Lock() |
| 81 | inject := f.conflicts > 0 |
| 82 | if inject { |
| 83 | f.conflicts-- |
| 84 | f.injected++ |
| 85 | } |
| 86 | f.mu.Unlock() |
| 87 | if inject { |
| 88 | cur, tok, _ := f.inner.load(ctx) |
| 89 | if _, err := f.inner.swap(ctx, tok, cur+f.competitorBlock); err != nil { |
| 90 | return false, err |
| 91 | } |
| 92 | return false, nil // caller's token is now stale |
| 93 | } |
| 94 | return f.inner.swap(ctx, token, newValue) |
| 95 | } |
| 96 | |
| 97 | func TestAllocateBlockRefill(t *testing.T) { |
| 98 | m := &memCounter{} |
| 99 | a := newWithStore(m, 4) // small block so 10 ids span multiple reservations |
| 100 | ctx := context.Background() |
| 101 | |
| 102 | var got []uint64 |
| 103 | for i := 0; i < 10; i++ { |
| 104 | id, err := a.Allocate(ctx) |
| 105 | if err != nil { |
| 106 | t.Fatalf("allocate %d: %v", i, err) |
| 107 | } |
| 108 | got = append(got, id) |
| 109 | } |
| 110 | for i, id := range got { |
| 111 | if want := uint64(i + 1); id != want { |
| 112 | t.Fatalf("id[%d] = %d, want %d (ids must be 1-based and contiguous)", i, id, want) |
| 113 | } |
| 114 | } |
| 115 | // ceil(10/4) = 3 blocks; each block is one S3 CAS. This is the whole point: |
| 116 | // 10 ids cost 3 S3 writes, not 10. |
| 117 | if m.swapOK != 3 { |
| 118 | t.Fatalf("reservations = %d, want 3 (blocks of 4 covering 10 ids)", m.swapOK) |
| 119 | } |
| 120 | if m.value != 12 { |
| 121 | t.Fatalf("high-water = %d, want 12 (3 blocks of 4)", m.value) |
| 122 | } |
| 123 | } |
| 124 | |
| 125 | func TestAllocatePersistsAcrossRestart(t *testing.T) { |
| 126 | m := &memCounter{} |
| 127 | ctx := context.Background() |
| 128 | |
| 129 | // A reserves a block of 100 but hands out only 3 ids, then "crashes". |
| 130 | a := newWithStore(m, 100) |
| 131 | for i := 0; i < 3; i++ { |
| 132 | if _, err := a.Allocate(ctx); err != nil { |
| 133 | t.Fatalf("A allocate: %v", err) |
| 134 | } |
| 135 | } |
| 136 | if m.value != 100 { |
| 137 | t.Fatalf("high-water after A = %d, want 100", m.value) |
| 138 | } |
| 139 | |
| 140 | // A fresh allocator over the same backing store must continue PAST the stored |
| 141 | // high-water — skipping the unused tail of A's block (ids 4..100 are burned). |
| 142 | b := newWithStore(m, 100) |
| 143 | id, err := b.Allocate(ctx) |
| 144 | if err != nil { |
| 145 | t.Fatalf("B allocate: %v", err) |
| 146 | } |
| 147 | if id != 101 { |
| 148 | t.Fatalf("restarted allocator handed out %d, want 101 (must not reuse A's block)", id) |
| 149 | } |
| 150 | } |
| 151 | |
| 152 | func TestAllocateRetriesOnCASConflict(t *testing.T) { |
| 153 | inner := &memCounter{} |
| 154 | f := &flakyStore{inner: inner, competitorBlock: 7, conflicts: 1} |
| 155 | a := newWithStore(f, 100) |
| 156 | |
| 157 | id, err := a.Allocate(context.Background()) |
| 158 | if err != nil { |
| 159 | t.Fatalf("allocate: %v", err) |
| 160 | } |
| 161 | if f.injected != 1 { |
| 162 | t.Fatalf("injected conflicts = %d, want 1 (the retry path must have fired)", f.injected) |
| 163 | } |
| 164 | // The competitor took ids [1,7]; our retry must start strictly after it. |
| 165 | if id != 8 { |
| 166 | t.Fatalf("id after conflict = %d, want 8 (must skip the competitor's block)", id) |
| 167 | } |
| 168 | if inner.value != 107 { |
| 169 | t.Fatalf("high-water = %d, want 107 (competitor's 7 + our block of 100)", inner.value) |
| 170 | } |
| 171 | } |
| 172 | |
| 173 | func TestAllocateConcurrentUniqueAcrossAllocators(t *testing.T) { |
| 174 | // Two independent allocators over ONE shared counter — the production shape: |
| 175 | // two region clouds minting at once must never collide. |
| 176 | shared := &memCounter{} |
| 177 | a1 := newWithStore(shared, 10) |
| 178 | a2 := newWithStore(shared, 10) |
| 179 | ctx := context.Background() |
| 180 | |
| 181 | const goroutines = 8 |
| 182 | const perGoroutine = 200 // > blockSize, so every goroutine forces refills |
| 183 | |
| 184 | var mu sync.Mutex |
| 185 | seen := map[uint64]bool{} |
| 186 | var wg sync.WaitGroup |
| 187 | |
| 188 | run := func(a *Allocator) { |
| 189 | defer wg.Done() |
| 190 | for i := 0; i < perGoroutine; i++ { |
| 191 | id, err := a.Allocate(ctx) |
| 192 | if err != nil { |
| 193 | t.Errorf("allocate: %v", err) |
| 194 | return |
| 195 | } |
| 196 | mu.Lock() |
| 197 | if seen[id] { |
| 198 | t.Errorf("duplicate id handed out: %d", id) |
| 199 | } |
| 200 | seen[id] = true |
| 201 | mu.Unlock() |
| 202 | } |
| 203 | } |
| 204 | for i := 0; i < goroutines; i++ { |
| 205 | wg.Add(2) |
| 206 | go run(a1) |
| 207 | go run(a2) |
| 208 | } |
| 209 | wg.Wait() |
| 210 | |
| 211 | want := goroutines * 2 * perGoroutine |
| 212 | if len(seen) != want { |
| 213 | t.Fatalf("unique ids = %d, want %d (concurrent allocators overlapped)", len(seen), want) |
| 214 | } |
| 215 | for id := range seen { |
| 216 | if id == 0 { |
| 217 | t.Fatalf("handed out id 0 (ids must be 1-based)") |
| 218 | } |
| 219 | } |
| 220 | } |
| 221 | |
| 222 | // --- httptest S3 fake (real SDK path) --------------------------------------- |
| 223 | |
| 224 | type fakeObj struct { |
| 225 | body []byte |
| 226 | etag string // includes the surrounding quotes, as S3 returns them |
| 227 | } |
| 228 | |
| 229 | // fakeCASS3 is just enough S3 for the counter: path-style GET / conditional PUT |
| 230 | // over an in-memory map, honouring If-Match / If-None-Match with a real 412. |
| 231 | type fakeCASS3 struct { |
| 232 | mu sync.Mutex |
| 233 | objects map[string]fakeObj |
| 234 | etagSeq int |
| 235 | gets int |
| 236 | putOK int |
| 237 | put412 int |
| 238 | // forceConflicts makes the next N PUTs answer 412 regardless of the |
| 239 | // precondition — S3's ConditionalRequestConflict, letting a single-threaded |
| 240 | // test drive the retry loop over the real wire deterministically. |
| 241 | forceConflicts int |
| 242 | } |
| 243 | |
| 244 | func (f *fakeCASS3) precondition412(w http.ResponseWriter) { |
| 245 | f.put412++ |
| 246 | w.Header().Set("Content-Type", "application/xml") |
| 247 | w.WriteHeader(http.StatusPreconditionFailed) |
| 248 | io.WriteString(w, `<Error><Code>PreconditionFailed</Code><Message>At least one of the preconditions you specified did not hold.</Message></Error>`) |
| 249 | } |
| 250 | |
| 251 | func (f *fakeCASS3) handler(w http.ResponseWriter, r *http.Request) { |
| 252 | f.mu.Lock() |
| 253 | defer f.mu.Unlock() |
| 254 | key := r.URL.Path |
| 255 | switch r.Method { |
| 256 | case http.MethodGet: |
| 257 | f.gets++ |
| 258 | obj, ok := f.objects[key] |
| 259 | if !ok { |
| 260 | w.Header().Set("Content-Type", "application/xml") |
| 261 | w.WriteHeader(http.StatusNotFound) |
| 262 | io.WriteString(w, `<Error><Code>NoSuchKey</Code><Message>The specified key does not exist.</Message></Error>`) |
| 263 | return |
| 264 | } |
| 265 | w.Header().Set("ETag", obj.etag) |
| 266 | w.WriteHeader(http.StatusOK) |
| 267 | w.Write(obj.body) |
| 268 | case http.MethodPut: |
| 269 | if f.forceConflicts > 0 { |
| 270 | f.forceConflicts-- |
| 271 | f.precondition412(w) |
| 272 | return |
| 273 | } |
| 274 | body, _ := io.ReadAll(r.Body) |
| 275 | obj, exists := f.objects[key] |
| 276 | if r.Header.Get("If-None-Match") == "*" && exists { |
| 277 | f.precondition412(w) // create-only, but it already exists |
| 278 | return |
| 279 | } |
| 280 | if m := r.Header.Get("If-Match"); m != "" && (!exists || m != obj.etag) { |
| 281 | f.precondition412(w) // replace-only, but the object moved on |
| 282 | return |
| 283 | } |
| 284 | f.etagSeq++ |
| 285 | etag := fmt.Sprintf("\"e%d\"", f.etagSeq) |
| 286 | f.objects[key] = fakeObj{body: body, etag: etag} |
| 287 | f.putOK++ |
| 288 | w.Header().Set("ETag", etag) |
| 289 | w.WriteHeader(http.StatusOK) |
| 290 | default: |
| 291 | w.WriteHeader(http.StatusNotImplemented) |
| 292 | } |
| 293 | } |
| 294 | |
| 295 | func newFakeS3Allocator(t *testing.T, blockSize uint64) (*Allocator, *fakeCASS3) { |
| 296 | t.Helper() |
| 297 | fake := &fakeCASS3{objects: map[string]fakeObj{}} |
| 298 | srv := httptest.NewServer(http.HandlerFunc(fake.handler)) |
| 299 | t.Cleanup(srv.Close) |
| 300 | |
| 301 | // Static creds + region so the SDK's signer is satisfied offline (same as |
| 302 | // s3blobstore_test.go). |
| 303 | t.Setenv("AWS_ACCESS_KEY_ID", "test") |
| 304 | t.Setenv("AWS_SECRET_ACCESS_KEY", "test") |
| 305 | t.Setenv("AWS_REGION", "auto") |
| 306 | |
| 307 | a, err := New(context.Background(), Config{ |
| 308 | Bucket: "idbucket", |
| 309 | Prefix: "pfx", |
| 310 | Endpoint: srv.URL, |
| 311 | BlockSize: blockSize, |
| 312 | }) |
| 313 | if err != nil { |
| 314 | t.Fatalf("New: %v", err) |
| 315 | } |
| 316 | return a, fake |
| 317 | } |
| 318 | |
| 319 | func TestS3AllocatorRoundTrip(t *testing.T) { |
| 320 | a, fake := newFakeS3Allocator(t, 100) |
| 321 | ctx := context.Background() |
| 322 | |
| 323 | for i := 0; i < 5; i++ { |
| 324 | id, err := a.Allocate(ctx) |
| 325 | if err != nil { |
| 326 | t.Fatalf("allocate %d: %v", i, err) |
| 327 | } |
| 328 | if want := uint64(i + 1); id != want { |
| 329 | t.Fatalf("id[%d] = %d, want %d", i, id, want) |
| 330 | } |
| 331 | } |
| 332 | // 5 ids, one block: exactly one successful PUT. |
| 333 | if fake.putOK != 1 { |
| 334 | t.Fatalf("successful PUTs = %d, want 1 (one block for 5 ids)", fake.putOK) |
| 335 | } |
| 336 | obj := fake.objects["/idbucket/pfx/mesh/id-sequence"] |
| 337 | if string(obj.body) != "100" { |
| 338 | t.Fatalf("counter object = %q, want \"100\"", obj.body) |
| 339 | } |
| 340 | } |
| 341 | |
| 342 | func TestS3AllocatorRetriesReal412(t *testing.T) { |
| 343 | a, fake := newFakeS3Allocator(t, 100) |
| 344 | fake.forceConflicts = 2 // the first two PUTs come back 412 over the real SDK |
| 345 | |
| 346 | id, err := a.Allocate(context.Background()) |
| 347 | if err != nil { |
| 348 | t.Fatalf("allocate: %v", err) |
| 349 | } |
| 350 | if id != 1 { |
| 351 | t.Fatalf("id = %d, want 1", id) |
| 352 | } |
| 353 | if fake.put412 != 2 { |
| 354 | t.Fatalf("412 responses = %d, want 2 (the SDK must have retried each)", fake.put412) |
| 355 | } |
| 356 | if fake.putOK != 1 { |
| 357 | t.Fatalf("successful PUTs = %d, want 1", fake.putOK) |
| 358 | } |
| 359 | } |
| 360 | |
| 361 | func TestS3AllocatorConcurrentUnique(t *testing.T) { |
| 362 | // Two allocators, one fake bucket, blockSize 1 → maximum CAS contention over |
| 363 | // the real conditional-PUT path. Uniqueness can only hold if 412s are being |
| 364 | // retried correctly. |
| 365 | fake := &fakeCASS3{objects: map[string]fakeObj{}} |
| 366 | srv := httptest.NewServer(http.HandlerFunc(fake.handler)) |
| 367 | t.Cleanup(srv.Close) |
| 368 | t.Setenv("AWS_ACCESS_KEY_ID", "test") |
| 369 | t.Setenv("AWS_SECRET_ACCESS_KEY", "test") |
| 370 | t.Setenv("AWS_REGION", "auto") |
| 371 | |
| 372 | newA := func() *Allocator { |
| 373 | a, err := New(context.Background(), Config{Bucket: "idbucket", Endpoint: srv.URL, BlockSize: 1}) |
| 374 | if err != nil { |
| 375 | t.Fatalf("New: %v", err) |
| 376 | } |
| 377 | return a |
| 378 | } |
| 379 | a1, a2 := newA(), newA() |
| 380 | ctx := context.Background() |
| 381 | |
| 382 | const goroutines = 6 |
| 383 | const perGoroutine = 40 |
| 384 | |
| 385 | var mu sync.Mutex |
| 386 | seen := map[uint64]bool{} |
| 387 | var wg sync.WaitGroup |
| 388 | run := func(a *Allocator) { |
| 389 | defer wg.Done() |
| 390 | for i := 0; i < perGoroutine; i++ { |
| 391 | id, err := a.Allocate(ctx) |
| 392 | if err != nil { |
| 393 | t.Errorf("allocate: %v", err) |
| 394 | return |
| 395 | } |
| 396 | mu.Lock() |
| 397 | if seen[id] { |
| 398 | t.Errorf("duplicate id: %d", id) |
| 399 | } |
| 400 | seen[id] = true |
| 401 | mu.Unlock() |
| 402 | } |
| 403 | } |
| 404 | for i := 0; i < goroutines; i++ { |
| 405 | wg.Add(2) |
| 406 | go run(a1) |
| 407 | go run(a2) |
| 408 | } |
| 409 | wg.Wait() |
| 410 | |
| 411 | if want := goroutines * 2 * perGoroutine; len(seen) != want { |
| 412 | t.Fatalf("unique ids = %d, want %d", len(seen), want) |
| 413 | } |
| 414 | } |
| 415 | |
amadan