search

graphite-project / carbon

Carbon is one of the components of Graphite, and is responsible for receiving metrics over the network and writing them down to disk using a storage backend.
http://graphite.readthedocs.org/
Apache License 2.0
1.51k stars 490 forks source link

Carbon fnv1a_ch not compatible with carbon-c-relay #714

Closed iain-buclaw-sociomantic closed 6 years ago

iain-buclaw-sociomantic commented 6 years ago

Given the following carbon config:

DESTINATIONS = 192.168.240.186:2003:a, 192.168.240.184:2003:b
HASHING_TYPE = fnv1a_ch

And the equivalent carbon-c-relay config:

cluster graphite
    fnv1a_ch
        192.168.240.186:2003=a proto tcp
        192.168.240.184:2003=b proto tcp
    ;

They both produce different hash rings.

Carbon:

  218@192.168.240.184:2003   536@192.168.240.184:2003   611@192.168.240.186:2003
  991@192.168.240.184:2003  1625@192.168.240.186:2003  2470@192.168.240.186:2003
 2505@192.168.240.184:2003  2801@192.168.240.184:2003  3088@192.168.240.184:2003
 3112@192.168.240.186:2003  3378@192.168.240.186:2003  3423@192.168.240.186:2003
 3696@192.168.240.186:2003  3859@192.168.240.184:2003  4185@192.168.240.184:2003
 4496@192.168.240.186:2003  5319@192.168.240.184:2003  6103@192.168.240.184:2003
 6265@192.168.240.184:2003  6314@192.168.240.184:2003  6566@192.168.240.184:2003
 6755@192.168.240.186:2003  7335@192.168.240.186:2003  7474@192.168.240.184:2003
 7671@192.168.240.184:2003  7877@192.168.240.186:2003  7948@192.168.240.186:2003
 8078@192.168.240.186:2003  9040@192.168.240.184:2003  9314@192.168.240.186:2003
 9796@192.168.240.184:2003 10098@192.168.240.184:2003 10427@192.168.240.186:2003
11346@192.168.240.186:2003 11432@192.168.240.186:2003 12229@192.168.240.184:2003
12313@192.168.240.184:2003 12612@192.168.240.184:2003 12684@192.168.240.186:2003
12862@192.168.240.186:2003 12941@192.168.240.186:2003 12973@192.168.240.186:2003
13406@192.168.240.184:2003 14002@192.168.240.186:2003 14373@192.168.240.184:2003
14550@192.168.240.186:2003 14711@192.168.240.184:2003 14715@192.168.240.184:2003
15042@192.168.240.186:2003 15100@192.168.240.186:2003 15303@192.168.240.184:2003
15441@192.168.240.186:2003 15630@192.168.240.184:2003 16003@192.168.240.184:2003
16023@192.168.240.186:2003 16159@192.168.240.186:2003 16844@192.168.240.184:2003
16959@192.168.240.184:2003 17469@192.168.240.186:2003 17638@192.168.240.186:2003
17797@192.168.240.186:2003 17911@192.168.240.186:2003 17974@192.168.240.184:2003
19350@192.168.240.186:2003 19624@192.168.240.184:2003 19916@192.168.240.186:2003
19959@192.168.240.186:2003 20241@192.168.240.186:2003 20442@192.168.240.186:2003
20498@192.168.240.186:2003 20708@192.168.240.184:2003 21083@192.168.240.184:2003
21219@192.168.240.186:2003 21530@192.168.240.184:2003 22403@192.168.240.184:2003
23090@192.168.240.184:2003 23394@192.168.240.184:2003 23679@192.168.240.186:2003
23801@192.168.240.184:2003 24156@192.168.240.186:2003 24257@192.168.240.184:2003
24278@192.168.240.184:2003 25241@192.168.240.184:2003 25803@192.168.240.184:2003
26266@192.168.240.186:2003 26439@192.168.240.186:2003 27050@192.168.240.184:2003
27079@192.168.240.186:2003 27419@192.168.240.186:2003 27778@192.168.240.184:2003
27855@192.168.240.184:2003 27959@192.168.240.186:2003 27972@192.168.240.184:2003
28002@192.168.240.186:2003 28003@192.168.240.186:2003 28091@192.168.240.186:2003
28329@192.168.240.186:2003 28430@192.168.240.184:2003 29749@192.168.240.186:2003
29794@192.168.240.186:2003 30120@192.168.240.184:2003 30142@192.168.240.184:2003
30325@192.168.240.184:2003 30711@192.168.240.184:2003 30767@192.168.240.184:2003
30933@192.168.240.186:2003 31079@192.168.240.184:2003 31372@192.168.240.184:2003
31383@192.168.240.184:2003 31464@192.168.240.186:2003 31966@192.168.240.186:2003
32069@192.168.240.184:2003 32142@192.168.240.184:2003 32524@192.168.240.184:2003
32609@192.168.240.186:2003 32785@192.168.240.184:2003 32947@192.168.240.186:2003
33146@192.168.240.184:2003 33696@192.168.240.186:2003 33753@192.168.240.184:2003
34338@192.168.240.186:2003 34457@192.168.240.186:2003 34683@192.168.240.186:2003
34728@192.168.240.186:2003 35134@192.168.240.186:2003 35137@192.168.240.184:2003
35256@192.168.240.186:2003 35872@192.168.240.186:2003 36029@192.168.240.184:2003
36077@192.168.240.184:2003 36557@192.168.240.184:2003 39426@192.168.240.184:2003
39671@192.168.240.186:2003 39891@192.168.240.186:2003 40295@192.168.240.184:2003
41026@192.168.240.184:2003 41315@192.168.240.186:2003 41797@192.168.240.186:2003
42190@192.168.240.186:2003 42291@192.168.240.184:2003 43031@192.168.240.186:2003
43121@192.168.240.184:2003 43146@192.168.240.184:2003 43914@192.168.240.184:2003
44012@192.168.240.186:2003 44343@192.168.240.184:2003 44644@192.168.240.184:2003
45015@192.168.240.186:2003 45561@192.168.240.186:2003 45594@192.168.240.184:2003
46446@192.168.240.186:2003 46700@192.168.240.184:2003 46884@192.168.240.186:2003
47071@192.168.240.184:2003 47339@192.168.240.184:2003 47752@192.168.240.186:2003
48116@192.168.240.184:2003 48631@192.168.240.186:2003 49685@192.168.240.184:2003
50284@192.168.240.186:2003 50447@192.168.240.184:2003 51405@192.168.240.186:2003
51415@192.168.240.186:2003 51742@192.168.240.184:2003 51972@192.168.240.184:2003
52127@192.168.240.184:2003 52678@192.168.240.186:2003 53275@192.168.240.184:2003
53390@192.168.240.186:2003 53602@192.168.240.184:2003 53693@192.168.240.186:2003
55468@192.168.240.184:2003 56262@192.168.240.186:2003 56348@192.168.240.186:2003
57079@192.168.240.186:2003 57445@192.168.240.186:2003 57660@192.168.240.184:2003
57996@192.168.240.186:2003 58025@192.168.240.186:2003 58716@192.168.240.184:2003
59352@192.168.240.184:2003 59361@192.168.240.184:2003 59420@192.168.240.186:2003
59941@192.168.240.184:2003 60005@192.168.240.186:2003 60053@192.168.240.186:2003
60297@192.168.240.184:2003 61264@192.168.240.186:2003 61518@192.168.240.184:2003
61521@192.168.240.186:2003 61848@192.168.240.184:2003 61858@192.168.240.184:2003
61859@192.168.240.186:2003 62437@192.168.240.184:2003 62768@192.168.240.186:2003
63088@192.168.240.186:2003 63327@192.168.240.186:2003 63429@192.168.240.184:2003
64019@192.168.240.186:2003 65214@192.168.240.184:2003

Carbon-c-relay:

  218@192.168.240.184:2003   536@192.168.240.184:2003   611@192.168.240.186:2003
  991@192.168.240.184:2003  1625@192.168.240.186:2003  1795@192.168.240.184:2003
 2000@192.168.240.186:2003  2470@192.168.240.186:2003  2505@192.168.240.184:2003
 2801@192.168.240.184:2003  3088@192.168.240.184:2003  3112@192.168.240.186:2003
 3378@192.168.240.186:2003  3423@192.168.240.186:2003  3696@192.168.240.186:2003
 3849@192.168.240.184:2003  3859@192.168.240.184:2003  4185@192.168.240.184:2003
 4496@192.168.240.186:2003  5319@192.168.240.184:2003  6103@192.168.240.184:2003
 6265@192.168.240.184:2003  6314@192.168.240.184:2003  6566@192.168.240.184:2003
 6755@192.168.240.186:2003  7335@192.168.240.186:2003  7474@192.168.240.184:2003
 7671@192.168.240.184:2003  7877@192.168.240.186:2003  7948@192.168.240.186:2003
 8078@192.168.240.186:2003  9040@192.168.240.184:2003  9314@192.168.240.186:2003
 9796@192.168.240.184:2003 10098@192.168.240.184:2003 10427@192.168.240.186:2003
11346@192.168.240.186:2003 11432@192.168.240.186:2003 12229@192.168.240.184:2003
12313@192.168.240.184:2003 12612@192.168.240.184:2003 12684@192.168.240.186:2003
12862@192.168.240.186:2003 12941@192.168.240.186:2003 12973@192.168.240.186:2003
13406@192.168.240.184:2003 14002@192.168.240.186:2003 14373@192.168.240.184:2003
14550@192.168.240.186:2003 14711@192.168.240.184:2003 14715@192.168.240.184:2003
15042@192.168.240.186:2003 15100@192.168.240.186:2003 15303@192.168.240.184:2003
15441@192.168.240.186:2003 15630@192.168.240.184:2003 16003@192.168.240.184:2003
16023@192.168.240.186:2003 16844@192.168.240.184:2003 16959@192.168.240.184:2003
17469@192.168.240.186:2003 17638@192.168.240.186:2003 17797@192.168.240.186:2003
17911@192.168.240.186:2003 17974@192.168.240.184:2003 19350@192.168.240.186:2003
19624@192.168.240.184:2003 19916@192.168.240.186:2003 19959@192.168.240.186:2003
20241@192.168.240.186:2003 20442@192.168.240.186:2003 20498@192.168.240.186:2003
20708@192.168.240.184:2003 21083@192.168.240.184:2003 21219@192.168.240.186:2003
21530@192.168.240.184:2003 22403@192.168.240.184:2003 23090@192.168.240.184:2003
23394@192.168.240.184:2003 23679@192.168.240.186:2003 23801@192.168.240.184:2003
24156@192.168.240.186:2003 24257@192.168.240.184:2003 24278@192.168.240.184:2003
26266@192.168.240.186:2003 26439@192.168.240.186:2003 27050@192.168.240.184:2003
27079@192.168.240.186:2003 27419@192.168.240.186:2003 27778@192.168.240.184:2003
27855@192.168.240.184:2003 27959@192.168.240.186:2003 27972@192.168.240.184:2003
28002@192.168.240.186:2003 28003@192.168.240.186:2003 28091@192.168.240.186:2003
28329@192.168.240.186:2003 28430@192.168.240.184:2003 29749@192.168.240.186:2003
29794@192.168.240.186:2003 30120@192.168.240.184:2003 30142@192.168.240.184:2003
30325@192.168.240.184:2003 30711@192.168.240.184:2003 30767@192.168.240.184:2003
30933@192.168.240.186:2003 31079@192.168.240.184:2003 31190@192.168.240.184:2003
31372@192.168.240.184:2003 31383@192.168.240.184:2003 31464@192.168.240.186:2003
31966@192.168.240.186:2003 32069@192.168.240.184:2003 32142@192.168.240.184:2003
32524@192.168.240.184:2003 32609@192.168.240.186:2003 32785@192.168.240.184:2003
32947@192.168.240.186:2003 33146@192.168.240.184:2003 33696@192.168.240.186:2003
33753@192.168.240.184:2003 34338@192.168.240.186:2003 34457@192.168.240.186:2003
34683@192.168.240.186:2003 34728@192.168.240.186:2003 35134@192.168.240.186:2003
35137@192.168.240.184:2003 35256@192.168.240.186:2003 35872@192.168.240.186:2003
36029@192.168.240.184:2003 36077@192.168.240.184:2003 36557@192.168.240.184:2003
39426@192.168.240.184:2003 39671@192.168.240.186:2003 39891@192.168.240.186:2003
40295@192.168.240.184:2003 41026@192.168.240.184:2003 41315@192.168.240.186:2003
41797@192.168.240.186:2003 42190@192.168.240.186:2003 42291@192.168.240.184:2003
43031@192.168.240.186:2003 43121@192.168.240.184:2003 43146@192.168.240.184:2003
43914@192.168.240.184:2003 44012@192.168.240.186:2003 44343@192.168.240.184:2003
45015@192.168.240.186:2003 45561@192.168.240.186:2003 45594@192.168.240.184:2003
46446@192.168.240.186:2003 46700@192.168.240.184:2003 46884@192.168.240.186:2003
47071@192.168.240.184:2003 47339@192.168.240.184:2003 47752@192.168.240.186:2003
48116@192.168.240.184:2003 48631@192.168.240.186:2003 49685@192.168.240.184:2003
50284@192.168.240.186:2003 50447@192.168.240.184:2003 51405@192.168.240.186:2003
51415@192.168.240.186:2003 51742@192.168.240.184:2003 51972@192.168.240.184:2003
52127@192.168.240.184:2003 52678@192.168.240.186:2003 53275@192.168.240.184:2003
53390@192.168.240.186:2003 53602@192.168.240.184:2003 55468@192.168.240.184:2003
56262@192.168.240.186:2003 56348@192.168.240.186:2003 57079@192.168.240.186:2003
57445@192.168.240.186:2003 57660@192.168.240.184:2003 57996@192.168.240.186:2003
58025@192.168.240.186:2003 58716@192.168.240.184:2003 59352@192.168.240.184:2003
59361@192.168.240.184:2003 59420@192.168.240.186:2003 59941@192.168.240.184:2003
60005@192.168.240.186:2003 60053@192.168.240.186:2003 60297@192.168.240.184:2003
61264@192.168.240.186:2003 61518@192.168.240.184:2003 61521@192.168.240.186:2003
61848@192.168.240.184:2003 61858@192.168.240.184:2003 61859@192.168.240.186:2003
62437@192.168.240.184:2003 62768@192.168.240.186:2003 63088@192.168.240.186:2003
63327@192.168.240.186:2003 63429@192.168.240.184:2003 64019@192.168.240.186:2003
65214@192.168.240.184:2003 65465@192.168.240.186:2003

This means that any tooling that uses carbon's consistent hash ring (such as carbonate) can not be used with carbon-c-relay. However I'm not sure whether who has the bug here in this discrepancy.

iain-buclaw-sociomantic commented 6 years ago

The diff between the two lists of replica_key = hash is:

--- carbon.txt  2017-12-21 17:46:57.480823985 +0100
+++ crelay.txt  2017-12-21 17:46:43.069027781 +0100
@@ -39,7 +39,7 @@
 38-a = 15441
 39-a = 31464
 40-a = 12862
-41-a = 16159
+41-a = 65465
 42-a = 32947
 43-a = 64019
 44-a = 11346
@@ -62,7 +62,7 @@
 61-a = 43031
 62-a = 34683
 63-a = 51405
-64-a = 53693
+64-a = 2000
 65-a = 14002
 66-a = 39671
 67-a = 47752
@@ -139,7 +139,7 @@
 38-b = 536
 39-b = 32069
 40-b = 16003
-41-b = 25241
+41-b = 1795
 42-b = 33146
 43-b = 65214
 44-b = 5319
@@ -160,9 +160,9 @@
 59-b = 52127
 60-b = 30767
 61-b = 43146
-62-b = 25803
+62-b = 31190
 63-b = 51972
-64-b = 44644
+64-b = 3849
 65-b = 15303
 66-b = 39426
 67-b = 35137

That is a worry, seems like some keys produce different hashes.

deniszh commented 6 years ago

It's after applying https://github.com/graphite-project/carbon/pull/679, right?

iain-buclaw-sociomantic commented 6 years ago

It's after applying #679, right?

I didn't have it applied. But applying that patch makes no difference.

iain-buclaw-sociomantic commented 6 years ago

If I calculate the small_hash the "C" way (by using bitwise shifts) then the computed hash rings match.

--- a/lib/carbon/hashing.py
+++ b/lib/carbon/hashing.py
@@ -38,13 +38,10 @@ class ConsistentHashRing:
   def compute_ring_position(self, key):
     if self.hash_type == 'fnv1a_ch':
       if sys.version_info >= (3, 0):
-        big_hash = '{:x}'.format(int(fnv32a(key)))
+        big_hash = int(fnv32a(key))
       else:
-        big_hash = '{:x}'.format(int(fnv32a(str(key))))
-      if len(big_hash) > 4:
-          small_hash = int(big_hash[:4], 16) ^ int(big_hash[4:], 16)
-      else:
-          small_hash = int(big_hash, 16)
+        big_hash = int(fnv32a(str(key)))
+      small_hash = (big_hash >> 16) ^ (big_hash & 0xFFFF)
     else:
       if sys.version_info >= (3, 0):
         big_hash = md5(key.encode('utf-8')).hexdigest()
deniszh commented 6 years ago

Cool! Could you please make a PRs? Thanks!

iain-buclaw-sociomantic commented 6 years ago

Right, just as soon as I understand why the original computation sometimes fails.

iain-buclaw-sociomantic commented 6 years ago

OK, it looks like the high and low parts are split incorrectly.

i.e:

key = '41-b'
fnv32a = 104464697
hex = 63a0139

The big hash is 7 hex digits in length, and is split into [63a0 : 139], which yields the computation:

small_hash = 0x63a0 ^ 0x139  # 25504 ^ 313 == 25241

Where it should instead be split into [63a : 0139], which gives us the correct answer:

small_hash = 0x63a ^ 0x0139  # 1594 ^ 313 == 1795
DanCech commented 6 years ago

Makes sense, nice catch @iain-buclaw-sociomantic ! In any case it'll be more efficient with your patch. A test case to cover this would also be great.

iain-buclaw-sociomantic commented 6 years ago

Alternatively, the big hash could be assigned as:

big_hash = '{:08x}.format(int(fnv32a(str(key)))

And the original logic could be kept (removing the condition that works around smaller hashes).

Yes, I agree that not bothering with formatting and just doing the bitwise approach should be more efficient.

reyjrar commented 6 years ago

Just wanted to say thanks to @iain-buclaw-sociomantic. I was experiencing this issue and thought I was losing my mind.

Thank you for your work!