Instruction file imported from williamntlam/distributed-deque (
.cursor/rules/memory-patterns.mdc). Copyright stays with the author.
Memory deque patterns — distributed-deque
Deep dive: docs/deque-guide.md. File tree: README Repository layout.
| File | Contents |
|---|---|
memory/node.go |
node, link/unlink at head/tail |
memory/deque.go |
MemoryDeque, mutex, size, four ops |
memory/ring.go |
(later) ring buffer — same methods |
cmd/queued/main.go |
HTTP server; owns the only canonical deque |
Author is learning — explain mutex boundaries and distribution tradeoffs; avoid implementing whole packages unless asked.
MemoryDeque ↔ doubly-linked list + mutex
| Go op | Implementation | Notes |
|---|---|---|
PushFront |
Lock; new node before head |
O(1); update head, nil-safe empty list |
PushBack |
Lock; new node after tail |
O(1) |
PopFront |
Lock; unlink head |
Empty → ErrEmpty; fix tail if one node left |
PopBack |
Lock; unlink tail |
Symmetric |
Len |
Lock; return size |
Maintain on push/pop — do not walk list |
Close |
Set closed flag; ErrClosed on ops |
sync.Once or atomic |
- Why linked, not slice:
PushFronton a plain slice is O(n); deque needs O(1) both ends. - Later: ring buffer (circular slice + head/tail) — same O(1) ends, fewer allocs; swap internals after linked list ships.
- Atomicity: hold one mutex for the whole push/pop/unlink.
- Concurrency: many goroutines on one
MemoryDeque— mutex serializes; each pop gets at most one element. - Not distributed: each process has its own
MemoryDequeunless talking tocmd/queued.
Ordering modes (both valid)
| Mode | Producers | Consumers | Tests | Use when |
|---|---|---|---|---|
| A — strict FIFO | One (or broker + accept arrival order) | One | TestPushBack_PopFront_FIFO, etc. |
Reproducible order |
| B — worker pool | Many | Many | TestConcurrentPushPop, -race |
Throughput; order not fixed |
README: Ordering: strict FIFO vs concurrent workers. Guide: §3.1.
cmd/queued ↔ HTTP
| Server op | HTTP | Notes |
|---|---|---|
PushBack |
POST /push body |
Max body size; copy bytes into deque |
PopFront |
GET /pop |
200 + body; 204 if empty (not 500) |
| Clients | curl, scripts, etc. |
No remote package in repo |
- Server process owns the only
MemoryDeque. - HTTP “connection refused” is not the same as an empty deque.
Production habits (when implementing)
- Pass
context.Context; respect cancel on blocking waits. - After
Close(), returnErrClosed. - Bound payload size; document whether returned
[]byteis copied. - Use
go test -raceon memory package tests.
When adding code, state which lock, what error (ErrEmpty vs ErrClosed), and whether the deque is in-process or behind HTTP.