Redis 해시 함수 및 데이터 파티션

Question

알려진 바와 같이 Redis는 CRC16 알고리즘을 사용하여 키를 해시 슬롯에 매핑합니다. crc가 노드에 키를 할당하기 위해 일종의 "배포"를 사용한다고 가정하는 것이 안전한가요? 그리고 그렇다면 어떤 종류의 분포입니까?

또한 모든 키의 해시 함수를 사용하여 키 양과 관련하여 노드에 균등하게로드 할 수 있습니까? 클라이언트가 3 노드 클러스터에서 임의로 3000 삽입을한다고 가정합니다. 그 후에 키는 노드에 균등하게 분배됩니다 (M1 ≈ 1000, M2 ≈ 1000, M3 ≈ 1000). 입력 2,000,000와

list1= [] 
list2= [] 
list3= [] 

def RedisClusterCRC16(keysslot): 

    XMODEMCRC16Lookup = [ 
     0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50a5, 0x60c6, 0x70e7, 
     0x8108, 0x9129, 0xa14a, 0xb16b, 0xc18c, 0xd1ad, 0xe1ce, 0xf1ef, 
     0x1231, 0x0210, 0x3273, 0x2252, 0x52b5, 0x4294, 0x72f7, 0x62d6, 
     0x9339, 0x8318, 0xb37b, 0xa35a, 0xd3bd, 0xc39c, 0xf3ff, 0xe3de, 
     0x2462, 0x3443, 0x0420, 0x1401, 0x64e6, 0x74c7, 0x44a4, 0x5485, 
     0xa56a, 0xb54b, 0x8528, 0x9509, 0xe5ee, 0xf5cf, 0xc5ac, 0xd58d, 
     0x3653, 0x2672, 0x1611, 0x0630, 0x76d7, 0x66f6, 0x5695, 0x46b4, 
     0xb75b, 0xa77a, 0x9719, 0x8738, 0xf7df, 0xe7fe, 0xd79d, 0xc7bc, 
     0x48c4, 0x58e5, 0x6886, 0x78a7, 0x0840, 0x1861, 0x2802, 0x3823, 
     0xc9cc, 0xd9ed, 0xe98e, 0xf9af, 0x8948, 0x9969, 0xa90a, 0xb92b, 
     0x5af5, 0x4ad4, 0x7ab7, 0x6a96, 0x1a71, 0x0a50, 0x3a33, 0x2a12, 
     0xdbfd, 0xcbdc, 0xfbbf, 0xeb9e, 0x9b79, 0x8b58, 0xbb3b, 0xab1a, 
     0x6ca6, 0x7c87, 0x4ce4, 0x5cc5, 0x2c22, 0x3c03, 0x0c60, 0x1c41, 
     0xedae, 0xfd8f, 0xcdec, 0xddcd, 0xad2a, 0xbd0b, 0x8d68, 0x9d49, 
     0x7e97, 0x6eb6, 0x5ed5, 0x4ef4, 0x3e13, 0x2e32, 0x1e51, 0x0e70, 
     0xff9f, 0xefbe, 0xdfdd, 0xcffc, 0xbf1b, 0xaf3a, 0x9f59, 0x8f78, 
     0x9188, 0x81a9, 0xb1ca, 0xa1eb, 0xd10c, 0xc12d, 0xf14e, 0xe16f, 
     0x1080, 0x00a1, 0x30c2, 0x20e3, 0x5004, 0x4025, 0x7046, 0x6067, 
     0x83b9, 0x9398, 0xa3fb, 0xb3da, 0xc33d, 0xd31c, 0xe37f, 0xf35e, 
     0x02b1, 0x1290, 0x22f3, 0x32d2, 0x4235, 0x5214, 0x6277, 0x7256, 
     0xb5ea, 0xa5cb, 0x95a8, 0x8589, 0xf56e, 0xe54f, 0xd52c, 0xc50d, 
     0x34e2, 0x24c3, 0x14a0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405, 
     0xa7db, 0xb7fa, 0x8799, 0x97b8, 0xe75f, 0xf77e, 0xc71d, 0xd73c, 
     0x26d3, 0x36f2, 0x0691, 0x16b0, 0x6657, 0x7676, 0x4615, 0x5634, 
     0xd94c, 0xc96d, 0xf90e, 0xe92f, 0x99c8, 0x89e9, 0xb98a, 0xa9ab, 
     0x5844, 0x4865, 0x7806, 0x6827, 0x18c0, 0x08e1, 0x3882, 0x28a3, 
     0xcb7d, 0xdb5c, 0xeb3f, 0xfb1e, 0x8bf9, 0x9bd8, 0xabbb, 0xbb9a, 
     0x4a75, 0x5a54, 0x6a37, 0x7a16, 0x0af1, 0x1ad0, 0x2ab3, 0x3a92, 
     0xfd2e, 0xed0f, 0xdd6c, 0xcd4d, 0xbdaa, 0xad8b, 0x9de8, 0x8dc9, 
     0x7c26, 0x6c07, 0x5c64, 0x4c45, 0x3ca2, 0x2c83, 0x1ce0, 0x0cc1, 
     0xef1f, 0xff3e, 0xcf5d, 0xdf7c, 0xaf9b, 0xbfba, 0x8fd9, 0x9ff8, 
     0x6e17, 0x7e36, 0x4e55, 0x5e74, 0x2e93, 0x3eb2, 0x0ed1, 0x1ef0 
    ] 

    crc = 0 
    for byte in keysslot.encode("utf-8"): 
     crc = ((crc << 8) & 0xff00)^XMODEMCRC16Lookup[((crc >> 8) & 0xff)^ord(byte)] 





    metr1=0 
    metr2=0 
    metr3=0 

    if ((crc & 0xffff)% 16384) <= 5460: 
     metr1 = metr1+1 
     list1.append(metr1) 
    elif (((crc & 0xffff)% 16384) > 5460) and (((crc & 0xffff)% 16384) <= 10922): 
     metr2 = metr2+1 
     list2.append(metr2) 
    else: 
     metr3 = metr3+1 
     list3.append(metr3) 





for i in range(2000000): 
    RedisClusterCRC16(str(i)) 


print "M1 holds: ", sum(list1) 
print "M2 holds: ", sum(list2) 
print "M3 holds: ", sum(list3) 

이 결과는 :

M1 holds: 666625 
M2 holds: 666744 
M3 holds: 666631 

난 슬롯의 분배가 각 노드에서 거의 동등한 것으로 관찰

이러한 테스트하려면 파이썬에서 함수를 만들어 (이 예에서는 의사 노드).

해시 함수는 작은 정수 (버킷)에 키를 매핑 :

Answer 1

검색 후 내가 증거를 발견했다. 이상적인 해시 함수는 키를 정수와 같은 방식으로 매핑하여 입력 데이터에 규칙 성이 있어도 버킷 값이 고르게 분산되도록합니다.

• 정수의 열쇠를지도 :

  이 과정

  은 두 단계로 나눌 수 있습니다.
• 정수를 양동이에 매핑하십시오. 또한 여기

: https://en.wikipedia.org/wiki/Hash_function 균일 설명 해시 범위 크기 N의 범위에 비해 작다이 방법 (CRC)는 한 해시 값을 충분히 균일 한 분포를 생성 할 수있다 "고 말한다 체크섬 또는 지문 인식 기능 "을 지원합니다.

위의 실행 코드를 염두에두고 crc가 해시 값의 균일 한 분포를 생성 할 수 있음은 분명합니다.