Jon Haddad created CASSANDRA-20230:
--------------------------------------
Summary: vnode algorithm occasionally generates imbalanced rings
Key: CASSANDRA-20230
URL: https://issues.apache.org/jira/browse/CASSANDRA-20230
Project: Apache Cassandra
Issue Type: Bug
Reporter: Jon Haddad
Attachments: ring.txt
Generally, the deterministic vnode algorithm seems to make OK decisions, but
I've been working on a cluster where the tokens it's generated look like
they're not much better than random. I've verified
`allocate_tokens_for_local_replication_factor=3` was used when the nodes were
bootstrapped via the logs.
I've parsed the nodetool ring output and added some additional info so it's
obvious where the ranges are imbalanced. I've calculated the range for each
token along with the avg range for each token range in the cluster, and listed
each range size relative to the average as the %. For example:
The node that owns the token -5646866338711190221, that range is only 9.23% of
the average token range in the cluster.
{noformat}
37 10.20.80.11 rack-b -5646866338711190221 9455879439619330
9.23% 347209701613153318 112.93%{noformat}
Looking at the below data, it's obvious that some nodes have way more data
(272622351113636532 266.02%) than they should.
It doesn't look like we're trying to balance the ring by picking tokens that
split the largest ranges, which explains why the most recent node I we added
had less than half of the data as the largest node.
{noformat}
first token:9170886775430075796
Ring tokens:
# Address Rack Token Range
Rack Range
---------------------------------------------------------------------------------------------------------
1 10.20.16.94 rack-a -9223372036854775808 52485261424700012
51.21% 134226759678331788 43.66%
2 10.20.146.47 rack-c -9189547180369111384 33824856485664424
33.01% 244426531911895070 79.5%
3 10.20.84.97 rack-b -9098397575186281096 91149605182830288
88.94% 177459723093194724 57.72%
4 10.20.17.254 rack-a -9044662703355201173 53734871831079923
52.43% 178709333499574635 58.13%
5 10.20.93.76 rack-b -8949214606862506405 95448096492694768
93.14% 149182968323774691 48.52%
6 10.20.149.213 rack-c -8739828963515584556 209385643346921849
204.31% 449718216853526828 146.28%
7 10.20.93.195 rack-b -8682698381181565144 57130582334019412
55.75% 266516225680941261 86.69%
8 10.20.88.117 rack-b -8541994507578267972 140703873603297172
137.3% 140703873603297172 45.77%
9 10.20.21.149 rack-a -8513158149005026369 28836358573241603
28.14% 531504554350174804 172.88%
10 10.20.145.96 rack-c -8353521350819354568 159636798185671801
155.77% 386307612696229988 125.65%
11 10.20.92.129 rack-b -8261404278536710957 92117072282643611
89.89% 280590229041557015 91.26%
12 10.20.26.105 rack-a -8200535838360498152 60868440176212805
59.39% 312622310644528217 101.68%
13 10.20.95.182 rack-b -8021391251878672242 179144586481825910
174.81% 240013026658038715 78.07%
14 10.20.158.149 rack-c -8006311649206201825 15079602672470417
14.71% 347209701613152743 112.93%
15 10.20.21.212 rack-a -7766062938935428803 240248710270773022
234.43% 434472899425069349 141.32%
16 10.20.144.132 rack-c -7739844482128539727 26218456806889076
25.58% 266467167077662098 86.67%
17 10.20.88.17 rack-b -7670800529894427760 69043952234111967
67.37% 350590721984244482 114.03%
18 10.20.30.86 rack-a -7466462004095374782 204338525799052978
199.39% 299600934840054021 97.45%
19 10.20.151.62 rack-c -7426908388950633006 39553615144741776
38.6% 312936093177906721 101.79%
20 10.20.19.95 rack-a -7366859901397320121 60048487553312885
58.59% 99602102698054661 32.4%
21 10.20.92.38 rack-b -7365507018146776908 1352883250543213
1.32% 305293511747650852 99.3%
22 10.20.29.147 rack-a -7227645749564266633 137861268582510275
134.52% 139214151833053488 45.28%
23 10.20.145.3 rack-c -7171605796608455430 56039952955811203
54.68% 255302592342177576 83.04%
24 10.20.80.231 rack-b -7040317985592000803 131287811016454627
128.11% 325189032554776105 105.77%
25 10.20.26.105 rack-a -6981127409214619804 59190576377380999
57.76% 246518340349646829 80.18%
26 10.20.83.58 rack-b -6882252606836285198 98874802378334606
96.48% 158065378755715605 51.41%
27 10.20.158.56 rack-c -6776630009572643883 105622597263641315
103.06% 394975787035811547 128.47%
28 10.20.30.74 rack-a -6648811345754421660 127818663818222223
124.72% 332316063460198144 108.09%
29 10.20.21.121 rack-a -6535221896394566414 113589449359855246
110.84% 113589449359855246 36.95%
30 10.20.151.96 rack-c -6420071778790659373 115150117603907041
112.36% 356558230781984510 115.97%
31 10.20.82.247 rack-b -6357720556701447159 62351222089212214
60.84% 524532050134838039 170.61%
32 10.20.28.103 rack-a -6305056011315416293 52664545386030866
51.39% 230165885079150121 74.86%
33 10.20.158.149 rack-c -6032433660201779761 272622351113636532
266.02% 387638118588879612 126.08%
34 10.20.88.117 rack-b -5994076040324343539 38357619877436222
37.43% 363644516377103620 118.28%
35 10.20.145.96 rack-c -5778229414025526901 215846626298816638
210.62% 254204246176252860 82.68%
36 10.20.26.105 rack-a -5656322218150809551 121907195874717350
118.95% 648733793164606742 211.01%
37 10.20.80.11 rack-b -5646866338711190221 9455879439619330
9.23% 347209701613153318 112.93%
38 10.20.21.149 rack-a -5394494374428312525 252371964282877696
246.26% 261827843722497026 85.16%
39 10.20.93.76 rack-b -5380399171633528006 14095202794784519
13.75% 266467167077662215 86.67%
40 10.20.144.132 rack-c -5227306901031281262 153092270602246744
149.38% 550922512994245639 179.19%
41 10.20.24.172 rack-a -5181175383115792585 46131517915488677
45.01% 213318991312519940 69.38%
42 10.20.93.195 rack-b -5118571327911031275 62604055204761310
61.09% 261827843722496731 85.16%
43 10.20.92.206 rack-b -4962413169712651344 156158158198379931
152.38% 156158158198379931 50.79%
44 10.20.144.255 rack-c -4894990837571083608 67422332141567736
65.79% 332316063460197654 108.09%
45 10.20.19.95 rack-a -4724399575827667401 170591261743416207
166.46% 456775807288125184 148.57%
46 10.20.93.195 rack-b -4683676894619741545 40722681207925856
39.74% 278736275092909799 90.66%
47 10.20.146.47 rack-c -4649179066907635035 34497827712106510
33.66% 245811770663448573 79.95%
48 10.20.16.94 rack-a -4611686018427387905 37493048480247130
36.59% 112713557400279496 36.66%
49 10.20.21.212 rack-a -4409623112414382071 202062906013005834
197.17% 202062906013005834 65.72%
50 10.20.92.38 rack-b -4371054583975213180 38568528439168891
37.63% 312622310644528365 101.68%
51 10.20.144.255 rack-c -4298588344923390323 72466239051822857
70.71% 350590721984244712 114.03%
52 10.20.150.20 rack-c -3993294833175739272 305293511747651051
297.9% 305293511747651051 99.3%
53 10.20.91.254 rack-b -3937594054506566378 55700778669172894
54.35% 433460529468646802 140.99%
54 10.20.29.147 rack-a -3937256674792971232 337379713595146
0.33% 472366437621410839 153.64%
55 10.20.151.62 rack-c -3668105800620963222 269150874172008010
262.63% 325189032554776050 105.77%
56 10.20.84.97 rack-b -3487875837653040055 180229962967923167
175.87% 449718216853526323 146.28%
57 10.20.145.96 rack-c -3435566666045219787 52309171607820268
51.04% 232539134575743435 75.64%
58 10.20.24.172 rack-a -3272020364001133020 163546302044086767
159.59% 665236310791838212 216.38%
59 10.20.30.74 rack-a -3135096996508842591 136923367492290429
133.61% 136923367492290429 44.54%
60 10.20.83.58 rack-b -3063848761308671438 71248235200171153
69.52% 424027076344368617 137.92%
61 10.20.147.229 rack-c -2911034615910381452 152814145398289986
149.11% 524532050134838335 170.61%
62 10.20.26.105 rack-a -2829803484761191279 81231131149190173
79.26% 305293511747651312 99.3%
63 10.20.80.11 rack-b -2696424851207654625 133378633553536654
130.15% 367423910101016813 119.51%
64 10.20.151.96 rack-c -2547390099533278228 149034751674376397
145.43% 363644516377103224 118.28%
65 10.20.17.254 rack-a -2504614452206415750 42775647326862478
41.74% 325189032554775529 105.77%
66 10.20.91.254 rack-b -2322859386475439970 181755065730975780
177.35% 373565464732214655 121.51%
67 10.20.22.103 rack-a -2315699623075219595 7159763400220375
6.99% 188914829131196155 61.45%
68 10.20.144.255 rack-c -2192377191226873342 123322431848346253
120.34% 355012908306404886 115.47%
69 10.20.149.213 rack-c -2056222665366193435 136154525860679907
132.86% 136154525860679907 44.29%
70 10.20.29.147 rack-a -1791167572940380850 265055092425812585
258.64% 524532050134838745 170.61%
71 10.20.93.76 rack-b -1771936873481194892 19230699459185958
18.76% 550922512994245078 179.19%
72 10.20.145.3 rack-c -1719845305934835095 52091567546359797
50.83% 336377359431358340 109.41%
73 10.20.24.172 rack-a -1569784851601295151 150060454333539944
146.43% 221382721339085699 72.01%
74 10.20.21.121 rack-a -1481596503541663932 88188348059631219
86.05% 88188348059631219 28.68%
75 10.20.88.17 rack-b -1439620810020997023 41975693520666909
40.96% 332316063460197869 108.09%
76 10.20.151.62 rack-c -1411320999486545250 28299810534451773
27.61% 308524306448289845 100.35%
77 10.20.147.229 rack-c -1194751819402005368 216569180084539882
211.32% 216569180084539882 70.44%
78 10.20.95.182 rack-b -1138690567005124535 56061252396880833
54.7% 300930243015872488 97.88%
79 10.20.30.74 rack-a -1072510148256874743 66180418748249792
64.58% 409086355284789189 133.06%
80 10.20.29.51 rack-a -936355622396193590 136154525860681153
132.86% 136154525860681153 44.29%
81 10.20.150.58 rack-c -888273494874972566 48082127521221024
46.92% 306478324527032802 99.69%
82 10.20.89.254 rack-b -763548809496363728 124724685378608838
121.7% 375141757508760807 122.02%
83 10.20.148.78 rack-c -695026190728748975 68522618767614753
66.86% 193247304146223591 62.86%
84 10.20.92.206 rack-b -454091375866946019 240934814861802956
235.1% 309457433629417709 100.65%
85 10.20.150.58 rack-c -404151275954123662 49940099912822357
48.73% 290874914774625313 94.61%
86 10.20.17.254 rack-a -333582278939827335 70568997014296327
68.86% 602773343456366255 196.06%
87 10.20.144.132 rack-c -120191231713029034 213391047226798301
208.22% 283960044241094628 92.36%
88 10.20.29.147 rack-a -117013098855287122 3178132857741912
3.1% 216569180084540213 70.44%
89 10.20.16.94 rack-a -2 117013098855287120
114.18% 117013098855287120 38.06%
90 10.20.82.247 rack-b 18275061754464473 18275061754464475
17.83% 472366437621410492 153.64%
91 10.20.30.86 rack-a 189465225671745150 171190163917280677
167.04% 189465225671745152 61.63%
92 10.20.145.96 rack-c 302842028835857714 113376803164112564
110.63% 423033260548886748 137.6%
93 10.20.21.212 rack-a 382712529817969305 79870500982111591
77.94% 193247304146224155 62.86%
94 10.20.95.182 rack-b 401657613055777279 18945083237807974
18.49% 383382551301312806 124.7%
95 10.20.158.149 rack-c 670265938936873543 268608325881096264
262.1% 367423910101015829 119.51%
96 10.20.30.86 rack-a 673587444592594063 3321505655720520
3.24% 290874914774624758 94.61%
97 10.20.92.129 rack-b 692532527830402040 18945083237807977
18.49% 290874914774624761 94.61%
98 10.20.23.199 rack-a 957547488833689288 265014961003287248
258.6% 283960044241095225 92.36%
99 10.20.93.76 rack-b 976492572071497267 18945083237807979
18.49% 283960044241095227 92.36%
100 10.20.148.78 rack-c 976675586628109273 183014556612006
0.18% 306409647691235730 99.66%
101 10.20.22.103 rack-a 1307873573641664077 331197987013554804
323.18% 350326084807974789 113.95%
102 10.20.83.58 rack-b 1312157198425561502 4283624783897425
4.18% 335664626354064235 109.18%
103 10.20.147.229 rack-c 1449042024249520056 136884825823958554
133.57% 472366437621410783 153.64%
104 10.20.24.172 rack-a 1526181194689538001 77139170440017945
75.27% 218307621047873924 71.01%
105 10.20.21.149 rack-a 1598829898146541929 72648703457003928
70.89% 72648703457003928 23.63%
106 10.20.89.254 rack-b 1735616304527059052 136786406380517123
133.47% 423459106101497550 137.73%
107 10.20.29.51 rack-a 1776289621239736865 40673316712677813
39.69% 177459723093194936 57.72%
108 10.20.23.199 rack-a 1925472589563511867 149182968323775002
145.57% 149182968323775002 48.52%
109 10.20.146.47 rack-c 1941821895281165489 16349305717653622
15.95% 492779871031645433 160.28%
110 10.20.92.38 rack-b 2032567080151914406 90745184870748917
88.55% 296950775624855354 96.59%
111 10.20.21.149 rack-a 2191988815244453426 159421735092539020
155.56% 266516225680941559 86.69%
112 10.20.158.56 rack-c 2365281001382663071 173292186138209645
169.1% 423459106101497582 137.73%
113 10.20.88.17 rack-b 2387579988458317163 22298987075654092
21.76% 355012908306402757 115.47%
114 10.20.84.97 rack-b 2523734514318999176 136154525860682013
132.86% 136154525860682013 44.29%
115 10.20.30.86 rack-a 2613282917889306604 89548403570307428
87.38% 421294102644853178 137.03%
116 10.20.150.20 rack-c 2662231777007518448 48948859118211844
47.76% 296950775624855377 96.59%
117 10.20.92.206 rack-b 2846661377600858870 184429600593340422
179.96% 322926863281859694 105.04%
118 10.20.21.121 rack-a 2883076181595991262 36414803995132392
35.53% 269793263706684658 87.75%
119 10.20.144.251 rack-c 2924059620730015183 40983439134023921
39.99% 261827843722496735 85.16%
120 10.20.145.3 rack-c 3180697442048841657 256637821318826474
250.42% 256637821318826474 83.47%
121 10.20.89.254 rack-b 3241637164636670946 60939722587829289
59.46% 394975787035812076 128.47%
122 10.20.29.51 rack-a 3362088047846622951 120450883209952005
117.53% 479011866250631689 155.8%
123 10.20.144.251 rack-c 3471653766553720026 109565718707097075
106.91% 290956324504878369 94.64%
124 10.20.88.117 rack-b 3598195395418656077 126541628864936051
123.48% 356558230781985131 115.97%
125 10.20.149.213 rack-c 3649113489646914674 50918094228258597
49.68% 177459723093194648 57.72%
126 10.20.22.103 rack-a 3792019965987400295 142906476340485621
139.45% 429931918140777344 139.84%
127 10.20.144.132 rack-c 3798296457970688935 6276491983288640
6.12% 149182968323774261 48.52%
128 10.20.80.11 rack-b 3985833514007536019 187537056036847084
183.0% 387638118588879942 126.08%
129 10.20.144.251 rack-c 4064812683651630209 78979169644094190
77.07% 266516225680941274 86.69%
130 10.20.19.95 rack-a 4139229667600553871 74416983948923662
72.61% 347209701613153576 112.93%
131 10.20.151.96 rack-c 4205516557254927886 66286889654374015
64.68% 140703873603297677 45.77%
132 10.20.83.58 rack-b 4364160686550500444 158644129295572558
154.8% 378327172542964425 123.05%
133 10.20.23.199 rack-a 4405696834678215201 41536148127714757
40.53% 266467167077661330 86.67%
134 10.20.150.58 rack-c 4486106786296485649 80409951618270448
78.46% 280590229041557763 91.26%
135 10.20.16.94 rack-a 4611686018427387901 125579232130902252
122.54% 205989183749172700 67.0%
136 10.20.92.129 rack-b 4663761621390554463 52075602963166562
50.81% 299600934840054019 97.45%
137 10.20.146.47 rack-c 4729291875508437146 65530254117882683
63.94% 243185089211951497 79.1%
138 10.20.80.11 rack-b 4763363724088609656 34071848580172510
33.25% 99602102698055193 32.4%
139 10.20.82.247 rack-b 4902577875921664056 139214151833054400
135.84% 139214151833054400 45.28%
140 10.20.144.255 rack-c 5064821116816274786 162243240894610730
158.31% 335529241307837640 109.13%
141 10.20.92.38 rack-b 5149096216271310975 84275099455036189
82.23% 246518340349646919 80.18%
142 10.20.151.96 rack-c 5344183344632085640 195087128360774665
190.36% 279362227815810854 90.87%
143 10.20.21.121 rack-a 5344190431341493990 7086709408350
0.01% 732504412914106089 238.25%
144 10.20.80.231 rack-b 5470232255249086842 126041823907592852
122.99% 321136038977775867 104.45%
145 10.20.28.103 rack-a 5599615274198389999 129383018949303157
126.25% 255424842856896009 83.08%
146 10.20.89.254 rack-b 5601038641438494310 1423367240104311
1.39% 130806386189407468 42.55%
147 10.20.149.213 rack-c 5763351906979850606 162313265541356296
158.38% 419168562347764966 136.34%
148 10.20.95.182 rack-b 5902916083282211410 139564176302360804
136.18% 301877441843717100 98.19%
149 10.20.148.78 rack-c 6095717362449884318 192801279167672908
188.13% 332365455470033712 108.11%
150 10.20.19.95 rack-a 6189475282618394230 93757920168509912
91.49% 589860008420004231 191.86%
151 10.20.88.17 rack-b 6238445324590049310 48970041971655080
47.78% 335529241307837900 109.13%
152 10.20.158.56 rack-c 6470859119958645149 232413795368595839
226.79% 375141757508760831 122.02%
153 10.20.22.103 rack-a 6516386704535559376 45527584576914227
44.42% 326911421917165146 106.33%
154 10.20.88.117 rack-b 6517807552405859479 1420847870300103
1.39% 279362227815810169 90.87%
155 10.20.145.3 rack-c 6741694105655993871 223886553250134392
218.46% 270834985697348722 88.09%
156 10.20.84.97 rack-b 6936976114753622943 195282009097629072
190.55% 419168562347763464 136.34%
157 10.20.144.251 rack-c 7020430380748903693 83454265995280750
81.43% 278736275092909822 90.66%
158 10.20.23.199 rack-a 7067309217529804976 46878836780901283
45.74% 550922512994245600 179.19%
159 10.20.91.254 rack-b 7269341570223658427 202032352693853451
197.14% 332365455470035484 108.11%
160 10.20.150.20 rack-c 7333052691393432086 63711121169773659
62.17% 312622310644528393 101.68%
161 10.20.17.254 rack-a 7388445256507581893 55392565114149807
54.05% 321136038977776917 104.45%
162 10.20.80.231 rack-b 7582277663401565387 193832406893983494
189.14% 312936093177906960 101.79%
163 10.20.28.103 rack-a 7631751918907982030 49474255506416643
48.28% 243306662400400137 79.14%
164 10.20.148.78 rack-c 7775892406540551989 144140487632569959
140.65% 442839715147119903 144.04%
165 10.20.92.206 rack-b 7912887967081619192 136995560541067203
133.68% 330610303680053805 107.53%
166 10.20.30.74 rack-a 8058249031542833245 145361064461214053
141.84% 426497112634851215 138.72%
167 10.20.150.58 rack-c 8075493341380604702 17244309837771457
16.83% 299600934840052713 97.45%
168 10.20.158.149 rack-c 8175095444078661163 99602102698056461
97.19% 99602102698056461 32.4%
169 10.20.80.231 rack-b 8221412273529908988 46316829451247825
45.2% 308524306448289796 100.35%
170 10.20.28.103 rack-a 8297681652552085364 76269379022176376
74.42% 239432621009252119 77.88%
171 10.20.147.229 rack-c 8314309595911715114 16627943359629750
16.23% 139214151833053951 45.28%
172 10.20.82.247 rack-b 8437981453614448838 123671857702733724
120.68% 216569180084539850 70.44%
173 10.20.150.20 rack-c 8560827936261361580 122846482646912742
119.87% 246518340349646466 80.18%
174 10.20.92.129 rack-b 8744459778141481139 183631841880119559
179.18% 306478324527032301 99.69%
175 10.20.29.51 rack-a 8756779821706409579 12320043564928440
12.02% 459098169154324215 149.33%
176 10.20.91.254 rack-b 8879930450925197428 123150629218787849
120.17% 135470672783716289 44.06%
177 10.20.151.62 rack-c 8881963975239137216 2033524313939788
1.98% 321136038977775636 104.45%
178 10.20.158.56 rack-c 9012770361428545162 130806386189407946
127.64% 130806386189407946 42.55%
179 10.20.21.212 rack-a 9089145277176444020 76374915747898858
74.53% 332365455470034441 108.11%
180 10.20.93.195 rack-b 9170886775430075796 81741498253631776
79.76% 290956324504878368 94.64%{noformat}
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
