node_tree_test.go 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448
  1. /*
  2. Copyright 2018 The Kubernetes Authors.
  3. Licensed under the Apache License, Version 2.0 (the "License");
  4. you may not use this file except in compliance with the License.
  5. You may obtain a copy of the License at
  6. http://www.apache.org/licenses/LICENSE-2.0
  7. Unless required by applicable law or agreed to in writing, software
  8. distributed under the License is distributed on an "AS IS" BASIS,
  9. WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  10. See the License for the specific language governing permissions and
  11. limitations under the License.
  12. */
  13. package cache
  14. import (
  15. "reflect"
  16. "testing"
  17. "k8s.io/api/core/v1"
  18. metav1 "k8s.io/apimachinery/pkg/apis/meta/v1"
  19. )
  20. var allNodes = []*v1.Node{
  21. // Node 0: a node without any region-zone label
  22. {
  23. ObjectMeta: metav1.ObjectMeta{
  24. Name: "node-0",
  25. },
  26. },
  27. // Node 1: a node with region label only
  28. {
  29. ObjectMeta: metav1.ObjectMeta{
  30. Name: "node-1",
  31. Labels: map[string]string{
  32. v1.LabelZoneRegion: "region-1",
  33. },
  34. },
  35. },
  36. // Node 2: a node with zone label only
  37. {
  38. ObjectMeta: metav1.ObjectMeta{
  39. Name: "node-2",
  40. Labels: map[string]string{
  41. v1.LabelZoneFailureDomain: "zone-2",
  42. },
  43. },
  44. },
  45. // Node 3: a node with proper region and zone labels
  46. {
  47. ObjectMeta: metav1.ObjectMeta{
  48. Name: "node-3",
  49. Labels: map[string]string{
  50. v1.LabelZoneRegion: "region-1",
  51. v1.LabelZoneFailureDomain: "zone-2",
  52. },
  53. },
  54. },
  55. // Node 4: a node with proper region and zone labels
  56. {
  57. ObjectMeta: metav1.ObjectMeta{
  58. Name: "node-4",
  59. Labels: map[string]string{
  60. v1.LabelZoneRegion: "region-1",
  61. v1.LabelZoneFailureDomain: "zone-2",
  62. },
  63. },
  64. },
  65. // Node 5: a node with proper region and zone labels in a different zone, same region as above
  66. {
  67. ObjectMeta: metav1.ObjectMeta{
  68. Name: "node-5",
  69. Labels: map[string]string{
  70. v1.LabelZoneRegion: "region-1",
  71. v1.LabelZoneFailureDomain: "zone-3",
  72. },
  73. },
  74. },
  75. // Node 6: a node with proper region and zone labels in a new region and zone
  76. {
  77. ObjectMeta: metav1.ObjectMeta{
  78. Name: "node-6",
  79. Labels: map[string]string{
  80. v1.LabelZoneRegion: "region-2",
  81. v1.LabelZoneFailureDomain: "zone-2",
  82. },
  83. },
  84. },
  85. // Node 7: a node with proper region and zone labels in a region and zone as node-6
  86. {
  87. ObjectMeta: metav1.ObjectMeta{
  88. Name: "node-7",
  89. Labels: map[string]string{
  90. v1.LabelZoneRegion: "region-2",
  91. v1.LabelZoneFailureDomain: "zone-2",
  92. },
  93. },
  94. },
  95. // Node 8: a node with proper region and zone labels in a region and zone as node-6
  96. {
  97. ObjectMeta: metav1.ObjectMeta{
  98. Name: "node-8",
  99. Labels: map[string]string{
  100. v1.LabelZoneRegion: "region-2",
  101. v1.LabelZoneFailureDomain: "zone-2",
  102. },
  103. },
  104. }}
  105. func verifyNodeTree(t *testing.T, nt *NodeTree, expectedTree map[string]*nodeArray) {
  106. expectedNumNodes := int(0)
  107. for _, na := range expectedTree {
  108. expectedNumNodes += len(na.nodes)
  109. }
  110. if numNodes := nt.NumNodes(); numNodes != expectedNumNodes {
  111. t.Errorf("unexpected NodeTree.numNodes. Expected: %v, Got: %v", expectedNumNodes, numNodes)
  112. }
  113. if !reflect.DeepEqual(nt.tree, expectedTree) {
  114. t.Errorf("The node tree is not the same as expected. Expected: %v, Got: %v", expectedTree, nt.tree)
  115. }
  116. if len(nt.zones) != len(expectedTree) {
  117. t.Errorf("Number of zones in NodeTree.zones is not expected. Expected: %v, Got: %v", len(expectedTree), len(nt.zones))
  118. }
  119. for _, z := range nt.zones {
  120. if _, ok := expectedTree[z]; !ok {
  121. t.Errorf("zone %v is not expected to exist in NodeTree.zones", z)
  122. }
  123. }
  124. }
  125. func TestNodeTree_AddNode(t *testing.T) {
  126. tests := []struct {
  127. name string
  128. nodesToAdd []*v1.Node
  129. expectedTree map[string]*nodeArray
  130. }{
  131. {
  132. name: "single node no labels",
  133. nodesToAdd: allNodes[:1],
  134. expectedTree: map[string]*nodeArray{"": {[]string{"node-0"}, 0}},
  135. },
  136. {
  137. name: "mix of nodes with and without proper labels",
  138. nodesToAdd: allNodes[:4],
  139. expectedTree: map[string]*nodeArray{
  140. "": {[]string{"node-0"}, 0},
  141. "region-1:\x00:": {[]string{"node-1"}, 0},
  142. ":\x00:zone-2": {[]string{"node-2"}, 0},
  143. "region-1:\x00:zone-2": {[]string{"node-3"}, 0},
  144. },
  145. },
  146. {
  147. name: "mix of nodes with and without proper labels and some zones with multiple nodes",
  148. nodesToAdd: allNodes[:7],
  149. expectedTree: map[string]*nodeArray{
  150. "": {[]string{"node-0"}, 0},
  151. "region-1:\x00:": {[]string{"node-1"}, 0},
  152. ":\x00:zone-2": {[]string{"node-2"}, 0},
  153. "region-1:\x00:zone-2": {[]string{"node-3", "node-4"}, 0},
  154. "region-1:\x00:zone-3": {[]string{"node-5"}, 0},
  155. "region-2:\x00:zone-2": {[]string{"node-6"}, 0},
  156. },
  157. },
  158. }
  159. for _, test := range tests {
  160. t.Run(test.name, func(t *testing.T) {
  161. nt := newNodeTree(nil)
  162. for _, n := range test.nodesToAdd {
  163. nt.AddNode(n)
  164. }
  165. verifyNodeTree(t, nt, test.expectedTree)
  166. })
  167. }
  168. }
  169. func TestNodeTree_RemoveNode(t *testing.T) {
  170. tests := []struct {
  171. name string
  172. existingNodes []*v1.Node
  173. nodesToRemove []*v1.Node
  174. expectedTree map[string]*nodeArray
  175. expectError bool
  176. }{
  177. {
  178. name: "remove a single node with no labels",
  179. existingNodes: allNodes[:7],
  180. nodesToRemove: allNodes[:1],
  181. expectedTree: map[string]*nodeArray{
  182. "region-1:\x00:": {[]string{"node-1"}, 0},
  183. ":\x00:zone-2": {[]string{"node-2"}, 0},
  184. "region-1:\x00:zone-2": {[]string{"node-3", "node-4"}, 0},
  185. "region-1:\x00:zone-3": {[]string{"node-5"}, 0},
  186. "region-2:\x00:zone-2": {[]string{"node-6"}, 0},
  187. },
  188. },
  189. {
  190. name: "remove a few nodes including one from a zone with multiple nodes",
  191. existingNodes: allNodes[:7],
  192. nodesToRemove: allNodes[1:4],
  193. expectedTree: map[string]*nodeArray{
  194. "": {[]string{"node-0"}, 0},
  195. "region-1:\x00:zone-2": {[]string{"node-4"}, 0},
  196. "region-1:\x00:zone-3": {[]string{"node-5"}, 0},
  197. "region-2:\x00:zone-2": {[]string{"node-6"}, 0},
  198. },
  199. },
  200. {
  201. name: "remove all nodes",
  202. existingNodes: allNodes[:7],
  203. nodesToRemove: allNodes[:7],
  204. expectedTree: map[string]*nodeArray{},
  205. },
  206. {
  207. name: "remove non-existing node",
  208. existingNodes: nil,
  209. nodesToRemove: allNodes[:5],
  210. expectedTree: map[string]*nodeArray{},
  211. expectError: true,
  212. },
  213. }
  214. for _, test := range tests {
  215. t.Run(test.name, func(t *testing.T) {
  216. nt := newNodeTree(test.existingNodes)
  217. for _, n := range test.nodesToRemove {
  218. err := nt.RemoveNode(n)
  219. if test.expectError == (err == nil) {
  220. t.Errorf("unexpected returned error value: %v", err)
  221. }
  222. }
  223. verifyNodeTree(t, nt, test.expectedTree)
  224. })
  225. }
  226. }
  227. func TestNodeTree_UpdateNode(t *testing.T) {
  228. tests := []struct {
  229. name string
  230. existingNodes []*v1.Node
  231. nodeToUpdate *v1.Node
  232. expectedTree map[string]*nodeArray
  233. }{
  234. {
  235. name: "update a node without label",
  236. existingNodes: allNodes[:7],
  237. nodeToUpdate: &v1.Node{
  238. ObjectMeta: metav1.ObjectMeta{
  239. Name: "node-0",
  240. Labels: map[string]string{
  241. v1.LabelZoneRegion: "region-1",
  242. v1.LabelZoneFailureDomain: "zone-2",
  243. },
  244. },
  245. },
  246. expectedTree: map[string]*nodeArray{
  247. "region-1:\x00:": {[]string{"node-1"}, 0},
  248. ":\x00:zone-2": {[]string{"node-2"}, 0},
  249. "region-1:\x00:zone-2": {[]string{"node-3", "node-4", "node-0"}, 0},
  250. "region-1:\x00:zone-3": {[]string{"node-5"}, 0},
  251. "region-2:\x00:zone-2": {[]string{"node-6"}, 0},
  252. },
  253. },
  254. {
  255. name: "update the only existing node",
  256. existingNodes: allNodes[:1],
  257. nodeToUpdate: &v1.Node{
  258. ObjectMeta: metav1.ObjectMeta{
  259. Name: "node-0",
  260. Labels: map[string]string{
  261. v1.LabelZoneRegion: "region-1",
  262. v1.LabelZoneFailureDomain: "zone-2",
  263. },
  264. },
  265. },
  266. expectedTree: map[string]*nodeArray{
  267. "region-1:\x00:zone-2": {[]string{"node-0"}, 0},
  268. },
  269. },
  270. {
  271. name: "update non-existing node",
  272. existingNodes: allNodes[:1],
  273. nodeToUpdate: &v1.Node{
  274. ObjectMeta: metav1.ObjectMeta{
  275. Name: "node-new",
  276. Labels: map[string]string{
  277. v1.LabelZoneRegion: "region-1",
  278. v1.LabelZoneFailureDomain: "zone-2",
  279. },
  280. },
  281. },
  282. expectedTree: map[string]*nodeArray{
  283. "": {[]string{"node-0"}, 0},
  284. "region-1:\x00:zone-2": {[]string{"node-new"}, 0},
  285. },
  286. },
  287. }
  288. for _, test := range tests {
  289. t.Run(test.name, func(t *testing.T) {
  290. nt := newNodeTree(test.existingNodes)
  291. var oldNode *v1.Node
  292. for _, n := range allNodes {
  293. if n.Name == test.nodeToUpdate.Name {
  294. oldNode = n
  295. break
  296. }
  297. }
  298. if oldNode == nil {
  299. oldNode = &v1.Node{ObjectMeta: metav1.ObjectMeta{Name: "nonexisting-node"}}
  300. }
  301. nt.UpdateNode(oldNode, test.nodeToUpdate)
  302. verifyNodeTree(t, nt, test.expectedTree)
  303. })
  304. }
  305. }
  306. func TestNodeTree_Next(t *testing.T) {
  307. tests := []struct {
  308. name string
  309. nodesToAdd []*v1.Node
  310. numRuns int // number of times to run Next()
  311. expectedOutput []string
  312. }{
  313. {
  314. name: "empty tree",
  315. nodesToAdd: nil,
  316. numRuns: 2,
  317. expectedOutput: []string{"", ""},
  318. },
  319. {
  320. name: "should go back to the first node after finishing a round",
  321. nodesToAdd: allNodes[:1],
  322. numRuns: 2,
  323. expectedOutput: []string{"node-0", "node-0"},
  324. },
  325. {
  326. name: "should go back to the first node after going over all nodes",
  327. nodesToAdd: allNodes[:4],
  328. numRuns: 5,
  329. expectedOutput: []string{"node-0", "node-1", "node-2", "node-3", "node-0"},
  330. },
  331. {
  332. name: "should go to all zones before going to the second nodes in the same zone",
  333. nodesToAdd: allNodes[:9],
  334. numRuns: 11,
  335. expectedOutput: []string{"node-0", "node-1", "node-2", "node-3", "node-5", "node-6", "node-4", "node-7", "node-8", "node-0", "node-1"},
  336. },
  337. }
  338. for _, test := range tests {
  339. t.Run(test.name, func(t *testing.T) {
  340. nt := newNodeTree(test.nodesToAdd)
  341. var output []string
  342. for i := 0; i < test.numRuns; i++ {
  343. output = append(output, nt.Next())
  344. }
  345. if !reflect.DeepEqual(output, test.expectedOutput) {
  346. t.Errorf("unexpected output. Expected: %v, Got: %v", test.expectedOutput, output)
  347. }
  348. })
  349. }
  350. }
  351. func TestNodeTreeMultiOperations(t *testing.T) {
  352. tests := []struct {
  353. name string
  354. nodesToAdd []*v1.Node
  355. nodesToRemove []*v1.Node
  356. operations []string
  357. expectedOutput []string
  358. }{
  359. {
  360. name: "add and remove all nodes between two Next operations",
  361. nodesToAdd: allNodes[2:9],
  362. nodesToRemove: allNodes[2:9],
  363. operations: []string{"add", "add", "next", "add", "remove", "remove", "remove", "next"},
  364. expectedOutput: []string{"node-2", ""},
  365. },
  366. {
  367. name: "add and remove some nodes between two Next operations",
  368. nodesToAdd: allNodes[2:9],
  369. nodesToRemove: allNodes[2:9],
  370. operations: []string{"add", "add", "next", "add", "remove", "remove", "next"},
  371. expectedOutput: []string{"node-2", "node-4"},
  372. },
  373. {
  374. name: "remove nodes already iterated on and add new nodes",
  375. nodesToAdd: allNodes[2:9],
  376. nodesToRemove: allNodes[2:9],
  377. operations: []string{"add", "add", "next", "next", "add", "remove", "remove", "next"},
  378. expectedOutput: []string{"node-2", "node-3", "node-4"},
  379. },
  380. {
  381. name: "add more nodes to an exhausted zone",
  382. nodesToAdd: append(allNodes[4:9], allNodes[3]),
  383. nodesToRemove: nil,
  384. operations: []string{"add", "add", "add", "add", "add", "next", "next", "next", "next", "add", "next", "next", "next"},
  385. expectedOutput: []string{"node-4", "node-5", "node-6", "node-7", "node-3", "node-8", "node-4"},
  386. },
  387. {
  388. name: "remove zone and add new to ensure exhausted is reset correctly",
  389. nodesToAdd: append(allNodes[3:5], allNodes[6:8]...),
  390. nodesToRemove: allNodes[3:5],
  391. operations: []string{"add", "add", "next", "next", "remove", "add", "add", "next", "next", "remove", "next", "next"},
  392. expectedOutput: []string{"node-3", "node-4", "node-6", "node-7", "node-6", "node-7"},
  393. },
  394. }
  395. for _, test := range tests {
  396. t.Run(test.name, func(t *testing.T) {
  397. nt := newNodeTree(nil)
  398. addIndex := 0
  399. removeIndex := 0
  400. var output []string
  401. for _, op := range test.operations {
  402. switch op {
  403. case "add":
  404. if addIndex >= len(test.nodesToAdd) {
  405. t.Error("more add operations than nodesToAdd")
  406. } else {
  407. nt.AddNode(test.nodesToAdd[addIndex])
  408. addIndex++
  409. }
  410. case "remove":
  411. if removeIndex >= len(test.nodesToRemove) {
  412. t.Error("more remove operations than nodesToRemove")
  413. } else {
  414. nt.RemoveNode(test.nodesToRemove[removeIndex])
  415. removeIndex++
  416. }
  417. case "next":
  418. output = append(output, nt.Next())
  419. default:
  420. t.Errorf("unknow operation: %v", op)
  421. }
  422. }
  423. if !reflect.DeepEqual(output, test.expectedOutput) {
  424. t.Errorf("unexpected output. Expected: %v, Got: %v", test.expectedOutput, output)
  425. }
  426. })
  427. }
  428. }