replication_test.go 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384
  1. package replication
  2. import (
  3. "bytes"
  4. "io"
  5. "net/http/httptest"
  6. "os"
  7. "path/filepath"
  8. "testing"
  9. "time"
  10. "imuslab.com/arozos/mod/cluster/membership"
  11. "imuslab.com/arozos/mod/cluster/metadata"
  12. "imuslab.com/arozos/mod/cluster/storage"
  13. )
  14. func init() {
  15. membership.HeartbeatInterval = 500 * time.Millisecond
  16. membership.OnlineWindow = 2 * time.Second
  17. membership.OfflineWindow = 4 * time.Second
  18. }
  19. type testNode struct {
  20. id string
  21. m *membership.Manager
  22. meta *metadata.Manager
  23. st *storage.Service
  24. repl *Manager
  25. srv *httptest.Server
  26. root string
  27. vol *metadata.Volume
  28. down bool
  29. }
  30. func newTestNode(t *testing.T, id string) *testNode {
  31. t.Helper()
  32. dir := t.TempDir()
  33. m, err := membership.NewManager(membership.Option{
  34. NodeID: id, DBFile: filepath.Join(dir, "cluster.db"), KeyFile: filepath.Join(dir, "node.key"),
  35. Version: "test", DefaultName: "Node " + id,
  36. })
  37. if err != nil {
  38. t.Fatalf("NewManager: %v", err)
  39. }
  40. meta, err := metadata.New(metadata.Option{
  41. Membership: m, LeaseDuration: 3 * time.Second, LeaseRenew: time.Second,
  42. LeaseTick: 200 * time.Millisecond, PendingRetry: 300 * time.Millisecond,
  43. })
  44. if err != nil {
  45. t.Fatalf("metadata.New: %v", err)
  46. }
  47. root := filepath.Join(dir, "disk")
  48. os.MkdirAll(root, 0755)
  49. st, err := storage.New(storage.Option{
  50. Membership: m, Metadata: meta, TmpDir: filepath.Join(dir, "tmp"),
  51. LocalRoots: func() map[string]string { return map[string]string{"disk": root} },
  52. RefreshInterval: time.Hour, ReconcileInterval: time.Hour,
  53. })
  54. if err != nil {
  55. t.Fatalf("storage.New: %v", err)
  56. }
  57. repl, err := New(Option{
  58. Membership: m, Metadata: meta, Storage: st,
  59. PlanInterval: 400 * time.Millisecond, TaskLease: 2 * time.Second, LeaseRenew: 500 * time.Millisecond,
  60. OfflineStale: 3 * time.Second, MaxAttempts: 3,
  61. })
  62. if err != nil {
  63. t.Fatalf("replication.New: %v", err)
  64. }
  65. srv := httptest.NewServer(m.ACNHandler())
  66. cfg := m.Config()
  67. cfg.AdvertiseURL = srv.URL
  68. m.UpdateConfig(cfg)
  69. n := &testNode{id: id, m: m, meta: meta, st: st, repl: repl, srv: srv, root: root}
  70. t.Cleanup(func() { n.shutdown() })
  71. return n
  72. }
  73. func (n *testNode) shutdown() {
  74. if n.down {
  75. return
  76. }
  77. n.down = true
  78. n.repl.Close()
  79. n.st.Close()
  80. n.meta.Close()
  81. n.m.Close()
  82. n.srv.Close()
  83. }
  84. func waitFor(t *testing.T, what string, timeout time.Duration, cond func() bool) {
  85. t.Helper()
  86. deadline := time.Now().Add(timeout)
  87. for !cond() {
  88. if time.Now().After(deadline) {
  89. t.Fatalf("timed out waiting for %s", what)
  90. }
  91. time.Sleep(50 * time.Millisecond)
  92. }
  93. }
  94. // cluster3 builds a three node cluster where every node contributes a volume.
  95. func cluster3(t *testing.T) (*testNode, *testNode, *testNode) {
  96. t.Helper()
  97. a := newTestNode(t, "node-a")
  98. b := newTestNode(t, "node-b")
  99. c := newTestNode(t, "node-c")
  100. if _, err := a.m.CreateCluster("Repl"); err != nil {
  101. t.Fatalf("CreateCluster: %v", err)
  102. }
  103. time.Sleep(1100 * time.Millisecond)
  104. for _, n := range []*testNode{b, c} {
  105. token, _, _ := a.m.NewJoinToken(time.Hour)
  106. if _, err := n.m.JoinCluster(token); err != nil {
  107. t.Fatalf("join %s: %v", n.id, err)
  108. }
  109. }
  110. waitFor(t, "leader", 10*time.Second, func() bool {
  111. return a.meta.IsLeader() && b.meta.Leader() == "node-a" && c.meta.Leader() == "node-a"
  112. })
  113. for _, n := range []*testNode{a, b, c} {
  114. vol, err := n.st.AddVolume("disk", "/cluster", n.id+" volume")
  115. if err != nil {
  116. t.Fatalf("AddVolume %s: %v", n.id, err)
  117. }
  118. n.vol = vol
  119. }
  120. waitFor(t, "volumes everywhere", 5*time.Second, func() bool {
  121. return len(a.meta.Volumes()) == 3 && len(b.meta.Volumes()) == 3 && len(c.meta.Volumes()) == 3
  122. })
  123. return a, b, c
  124. }
  125. func healthyCount(n *testNode, p string) int {
  126. rec, err := n.meta.Stat(p)
  127. if err != nil {
  128. return -1
  129. }
  130. return len(rec.HealthyLocations())
  131. }
  132. func nodesHolding(n *testNode, p string) map[string]bool {
  133. out := map[string]bool{}
  134. rec, err := n.meta.Stat(p)
  135. if err != nil {
  136. return out
  137. }
  138. for _, l := range rec.HealthyLocations() {
  139. out[l.NodeID] = true
  140. }
  141. return out
  142. }
  143. func readVia(t *testing.T, n *testNode, p string) []byte {
  144. t.Helper()
  145. r, err := n.st.OpenRead(p)
  146. if err != nil {
  147. t.Fatalf("OpenRead on %s: %v", n.id, err)
  148. }
  149. defer r.Close()
  150. b, err := io.ReadAll(r)
  151. if err != nil {
  152. t.Fatalf("read on %s: %v", n.id, err)
  153. }
  154. return b
  155. }
  156. func TestReplicatesToPolicyAndDropsExtras(t *testing.T) {
  157. a, b, c := cluster3(t)
  158. if err := a.meta.Submit(metadata.KindPolicy, &metadata.Policy{Folder: "/docs", Replicas: 2}); err != nil {
  159. t.Fatalf("policy: %v", err)
  160. }
  161. content := bytes.Repeat([]byte("replica-me "), 100000) //1.1 MB
  162. if err := a.st.Write("/docs/report.bin", bytes.NewReader(content), "toby"); err != nil {
  163. t.Fatalf("write: %v", err)
  164. }
  165. waitFor(t, "second healthy copy", 40*time.Second, func() bool { return healthyCount(a, "/docs/report.bin") == 2 })
  166. holders := nodesHolding(a, "/docs/report.bin")
  167. if len(holders) != 2 || !holders["node-a"] {
  168. t.Fatalf("copies should be on a and one other node, got %v", holders)
  169. }
  170. //The copy is a real verified file on the target's disk
  171. var target *testNode
  172. for _, n := range []*testNode{b, c} {
  173. if holders[n.id] {
  174. target = n
  175. }
  176. }
  177. onDisk, err := os.ReadFile(filepath.Join(target.root, "cluster", "docs", "report.bin"))
  178. if err != nil || !bytes.Equal(onDisk, content) {
  179. t.Fatalf("replica on %s missing or different: %v", target.id, err)
  180. }
  181. rec, _ := a.meta.Stat("/docs/report.bin")
  182. if loc, _ := rec.Location(target.vol.ID); loc.State != metadata.LocVerified {
  183. t.Errorf("replica state = %s, want verified", loc.State)
  184. }
  185. //Task history recorded on the leader
  186. waitFor(t, "task history", 20*time.Second, func() bool {
  187. st := a.repl.Status()
  188. return len(st.History) >= 1 && st.History[0].State == TaskDone && st.Queued == 0 && st.Running == 0
  189. })
  190. //Lower the policy: one copy is dropped, never the last one
  191. a.meta.Submit(metadata.KindPolicy, &metadata.Policy{Folder: "/docs", Replicas: 1})
  192. waitFor(t, "extra copy dropped", 30*time.Second, func() bool { return healthyCount(a, "/docs/report.bin") == 1 })
  193. //a's copy is the primary, so the target's copy is the one removed (the
  194. //physical delete follows the metadata update asynchronously)
  195. waitFor(t, "dropped copy removed from disk", 30*time.Second, func() bool {
  196. _, err := os.Stat(filepath.Join(target.root, "cluster", "docs", "report.bin"))
  197. return err != nil
  198. })
  199. if !nodesHolding(a, "/docs/report.bin")["node-a"] {
  200. t.Errorf("primary copy on a should have been kept")
  201. }
  202. if got := readVia(t, c, "/docs/report.bin"); !bytes.Equal(got, content) {
  203. t.Errorf("file unreadable after drop")
  204. }
  205. if st := a.repl.Status(); st.OverReplicated != 0 || st.UnderReplicated != 0 || st.Files != 1 {
  206. t.Errorf("status after settle: %+v", st)
  207. }
  208. }
  209. func TestRepairsStaleCopyInPlace(t *testing.T) {
  210. a, b, _ := cluster3(t)
  211. a.meta.Submit(metadata.KindPolicy, &metadata.Policy{Folder: "/docs", Replicas: 2})
  212. content := []byte("verify me carefully")
  213. a.st.Write("/docs/v.txt", bytes.NewReader(content), "")
  214. waitFor(t, "replica", 15*time.Second, func() bool { return healthyCount(a, "/docs/v.txt") == 2 })
  215. holders := nodesHolding(a, "/docs/v.txt")
  216. var target *testNode = b
  217. if !holders["node-b"] {
  218. t.Skip("copy landed on c; test targets b for simplicity")
  219. }
  220. //Corrupt the replica behind the cluster's back
  221. p := filepath.Join(target.root, "cluster", "docs", "v.txt")
  222. os.WriteFile(p, []byte("corrupted!!"), 0644)
  223. res := target.st.VerifyLocalCopies(0)
  224. if res.Stale != 1 || res.Checked < 1 {
  225. t.Fatalf("verify result: %+v", res)
  226. }
  227. waitFor(t, "leader to see the stale copy", 5*time.Second, func() bool {
  228. rec, _ := a.meta.Stat("/docs/v.txt")
  229. loc, _ := rec.Location(target.vol.ID)
  230. return loc.State == metadata.LocStale
  231. })
  232. //The planner repairs it in place
  233. waitFor(t, "repair", 15*time.Second, func() bool {
  234. rec, err := a.meta.Stat("/docs/v.txt")
  235. if err != nil {
  236. return false
  237. }
  238. loc, ok := rec.Location(target.vol.ID)
  239. return ok && loc.State == metadata.LocVerified
  240. })
  241. fixed, _ := os.ReadFile(p)
  242. if !bytes.Equal(fixed, content) {
  243. t.Errorf("repaired copy content wrong: %q", fixed)
  244. }
  245. //Verification of a good copy keeps it verified and bumps the timestamp
  246. res = target.st.VerifyLocalCopies(0)
  247. if res.Stale != 0 || res.Verified < 1 {
  248. t.Errorf("second verify: %+v", res)
  249. }
  250. }
  251. func TestOfflineNodeCopiesGoStaleAndGetReplaced(t *testing.T) {
  252. a, b, c := cluster3(t)
  253. a.meta.Submit(metadata.KindPolicy, &metadata.Policy{Folder: "/docs", Replicas: 2})
  254. content := []byte("survive a dead node")
  255. a.st.Write("/docs/s.txt", bytes.NewReader(content), "")
  256. waitFor(t, "replica", 15*time.Second, func() bool { return healthyCount(a, "/docs/s.txt") == 2 })
  257. holders := nodesHolding(a, "/docs/s.txt")
  258. var victim, survivor *testNode
  259. if holders["node-b"] {
  260. victim, survivor = b, c
  261. } else {
  262. victim, survivor = c, b
  263. }
  264. victim.shutdown()
  265. waitFor(t, "victim's copy marked stale and replaced", 30*time.Second, func() bool {
  266. rec, err := a.meta.Stat("/docs/s.txt")
  267. if err != nil {
  268. return false
  269. }
  270. loc, _ := rec.Location(victim.vol.ID)
  271. h := nodesHolding(a, "/docs/s.txt")
  272. return loc.State == metadata.LocStale && h[survivor.id] && h["node-a"]
  273. })
  274. if got := readVia(t, survivor, "/docs/s.txt"); !bytes.Equal(got, content) {
  275. t.Errorf("survivor cannot read the file")
  276. }
  277. st := a.repl.Status()
  278. if st.StaleCopies != 1 {
  279. t.Errorf("status should report 1 stale copy: %+v", st)
  280. }
  281. }
  282. func TestEvacuation(t *testing.T) {
  283. a, b, c := cluster3(t)
  284. content := []byte("move me")
  285. if err := b.st.Write("/docs/e.txt", bytes.NewReader(content), ""); err != nil {
  286. t.Fatalf("write: %v", err)
  287. }
  288. //b wrote it: the copy is on b's volume (local placement)
  289. waitFor(t, "record on leader", 5*time.Second, func() bool { return nodesHolding(a, "/docs/e.txt")["node-b"] })
  290. if err := b.st.RemoveVolume(b.vol.ID); err == nil {
  291. t.Errorf("removing a volume with sole copies must be refused")
  292. }
  293. if err := b.st.StartEvacuation(b.vol.ID); err != nil {
  294. t.Fatalf("StartEvacuation: %v", err)
  295. }
  296. waitFor(t, "volume retired", 20*time.Second, func() bool {
  297. v, ok := a.meta.Volume(b.vol.ID)
  298. return ok && v.Removed
  299. })
  300. h := nodesHolding(a, "/docs/e.txt")
  301. if h["node-b"] || (!h["node-a"] && !h["node-c"]) {
  302. t.Errorf("copy not moved off b: %v", h)
  303. }
  304. if _, err := os.Stat(filepath.Join(b.root, "cluster", "docs", "e.txt")); err == nil {
  305. t.Errorf("evacuated copy still on b's disk")
  306. }
  307. if got := readVia(t, c, "/docs/e.txt"); !bytes.Equal(got, content) {
  308. t.Errorf("file unreadable after evacuation")
  309. }
  310. //Writes no longer land on b
  311. if err := b.st.Write("/docs/after.txt", bytes.NewReader([]byte("x")), ""); err != nil {
  312. t.Fatalf("write after evacuation: %v", err)
  313. }
  314. if nodesHolding(b, "/docs/after.txt")["node-b"] {
  315. t.Errorf("new file placed on the retired volume")
  316. }
  317. }
  318. func TestPlanNowForwardsToLeader(t *testing.T) {
  319. a, b, _ := cluster3(t)
  320. a.st.Write("/x.txt", bytes.NewReader([]byte("x")), "")
  321. waitFor(t, "b to see file", 5*time.Second, func() bool { _, err := b.meta.Stat("/x.txt"); return err == nil })
  322. res, err := b.repl.PlanNow()
  323. if err != nil {
  324. t.Fatalf("PlanNow on follower: %v", err)
  325. }
  326. if res.Files != 1 || res.Time == 0 {
  327. t.Errorf("forwarded plan result: %+v", res)
  328. }
  329. if st := b.repl.Status(); st.IsLeader || st.LeaderName != "Node node-a" || st.Files != 1 {
  330. t.Errorf("follower status: %+v", st)
  331. }
  332. }
  333. func TestSiteDiversity(t *testing.T) {
  334. //Two sites: a and b are next to each other, c is far away
  335. matrix := map[string]map[string]float64{
  336. "a": {"b": 2, "c": 400},
  337. "b": {"a": 2, "c": 200},
  338. "c": {"a": 400, "b": 200},
  339. }
  340. tests := []struct {
  341. name string
  342. candidate string
  343. holders []string
  344. want float64
  345. }{
  346. {"same site as the copy", "b", []string{"a"}, 0.002},
  347. {"other site", "c", []string{"a"}, 0.4},
  348. {"nearest holder wins", "c", []string{"a", "b"}, 0.2},
  349. {"holder is itself", "a", []string{"a"}, 0},
  350. {"nothing measured", "d", []string{"a"}, -1},
  351. }
  352. for _, tc := range tests {
  353. t.Run(tc.name, func(t *testing.T) {
  354. got := siteDiversity(matrix, tc.candidate, tc.holders)
  355. if diff := got - tc.want; diff > 0.0001 || diff < -0.0001 {
  356. t.Errorf("siteDiversity(%s, %v) = %v; want %v", tc.candidate, tc.holders, got, tc.want)
  357. }
  358. })
  359. }
  360. //A round trip over a second is as diverse as it gets
  361. far := map[string]map[string]float64{"x": {"y": 5000}}
  362. if got := siteDiversity(far, "x", []string{"y"}); got != 1 {
  363. t.Errorf("a very distant node should saturate at 1, got %v", got)
  364. }
  365. }