{"id":1025,"date":"2025-05-08T17:37:33","date_gmt":"2025-05-08T09:37:33","guid":{"rendered":"https:\/\/beijian99.top\/?p=1025"},"modified":"2025-05-08T18:32:23","modified_gmt":"2025-05-08T10:32:23","slug":"%e4%b8%80%e8%87%b4%e6%80%a7%e5%93%88%e5%b8%8c","status":"publish","type":"post","link":"https:\/\/beijian99.top\/?p=1025","title":{"rendered":"\u4e00\u81f4\u6027\u54c8\u5e0c"},"content":{"rendered":"\n
\"\"<\/figure>\n\n\n\n

\u4ec0\u4e48\u662f\u4e00\u81f4\u6027\u54c8\u5e0c\uff1f<\/h3>\n\n\n\n

\u4e00\u81f4\u6027\u54c8\u5e0c\uff08Consistent Hashing\uff09\u662f\u4e00\u79cd\u7279\u6b8a\u7684\u54c8\u5e0c\u6280\u672f\uff0c\u4e3b\u8981\u7528\u4e8e\u5206\u5e03\u5f0f\u7cfb\u7edf\u4e2d\u89e3\u51b3\u6570\u636e\u5206\u5e03\u548c\u8d1f\u8f7d\u5747\u8861\u95ee\u9898\u3002\u5b83\u5728\u8282\u70b9\u589e\u51cf\u65f6\u80fd\u591f\u6700\u5c0f\u5316\u6570\u636e\u8fc1\u79fb\u91cf\uff0c\u4fdd\u6301\u7cfb\u7edf\u7684\u9ad8\u53ef\u7528\u6027\u3002<\/p>\n\n\n\n

\u4f20\u7edf\u54c8\u5e0c\u7684\u95ee\u9898<\/h3>\n\n\n\n

\u5728\u4f20\u7edf\u54c8\u5e0c\u65b9\u6cd5\u4e2d\uff0c\u5f53\u8282\u70b9\u6570\u91cf\u53d8\u5316\u65f6\uff08\u589e\u52a0\u6216\u51cf\u5c11\uff09\uff0c\u51e0\u4e4e\u6240\u6709\u6570\u636e\u90fd\u9700\u8981\u91cd\u65b0\u6620\u5c04\uff0c\u5bfc\u81f4\u5927\u89c4\u6a21\u6570\u636e\u8fc1\u79fb\uff0c\u8fd9\u5728\u5206\u5e03\u5f0f\u7cfb\u7edf\u4e2d\u662f\u975e\u5e38\u4f4e\u6548\u7684\u3002<\/p>\n\n\n\n

\u4e00\u81f4\u6027\u54c8\u5e0c\u7684\u4f18\u52bf<\/h3>\n\n\n\n
    \n
  1. \u8282\u70b9\u589e\u51cf\u65f6\u6570\u636e\u8fc1\u79fb\u91cf\u5c0f\uff1a\u53ea\u5f71\u54cd\u76f8\u90bb\u8282\u70b9\u7684\u6570\u636e<\/li>\n\n\n\n
  2. \u826f\u597d\u7684\u8d1f\u8f7d\u5747\u8861\uff1a\u6570\u636e\u5747\u5300\u5206\u5e03\u5728\u73af\u4e0a<\/li>\n\n\n\n
  3. \u53ef\u6269\u5c55\u6027\uff1a\u652f\u6301\u865a\u62df\u8282\u70b9\u8fdb\u4e00\u6b65\u63d0\u9ad8\u5747\u8861\u6027<\/li>\n<\/ol>\n\n\n\n

    \u4e00\u81f4\u6027\u54c8\u5e0c\u539f\u7406<\/h3>\n\n\n\n
      \n
    1. \u54c8\u5e0c\u73af\u6784\u9020\uff1a\u5c06\u54c8\u5e0c\u503c\u7a7a\u95f4\u7ec4\u7ec7\u6210\u4e00\u4e2a\u865a\u62df\u7684\u73af\uff08\u901a\u5e38\u4f7f\u75280~2^32-1\uff09<\/li>\n\n\n\n
    2. \u8282\u70b9\u6620\u5c04\uff1a\u5c06\u8282\u70b9\u901a\u8fc7\u54c8\u5e0c\u51fd\u6570\u6620\u5c04\u5230\u73af\u4e0a<\/li>\n\n\n\n
    3. \u6570\u636e\u5b9a\u4f4d\uff1a\u6570\u636ekey\u901a\u8fc7\u54c8\u5e0c\u51fd\u6570\u6620\u5c04\u5230\u73af\u4e0a\uff0c\u987a\u65f6\u9488\u627e\u5230\u7684\u7b2c\u4e00\u4e2a\u8282\u70b9\u5373\u4e3a\u5b58\u50a8\u4f4d\u7f6e<\/li>\n<\/ol>\n\n\n\n

      \u865a\u62df\u8282\u70b9<\/h4>\n\n\n\n

      \u4e3a\u4e86\u89e3\u51b3\u8282\u70b9\u5206\u5e03\u4e0d\u5747\u95ee\u9898\uff0c\u4e00\u81f4\u6027\u54c8\u5e0c\u5f15\u5165\u4e86\u865a\u62df\u8282\u70b9\u6982\u5ff5\uff1a
      \u2022 \u6bcf\u4e2a\u7269\u7406\u8282\u70b9\u5bf9\u5e94\u591a\u4e2a\u865a\u62df\u8282\u70b9<\/p>\n\n\n\n

      \u2022 \u865a\u62df\u8282\u70b9\u5747\u5300\u5206\u5e03\u5728\u73af\u4e0a<\/p>\n\n\n\n

      \u2022 \u63d0\u9ad8\u4e86\u8d1f\u8f7d\u5747\u8861\u6027<\/p>\n\n\n\n

      <\/p>\n\n\n\n

      \n\n\n\n

      Golang\u5b9e\u73b0<\/h4>\n\n\n
      \npackage consistenthash\n\nimport (\n\t"hash\/crc32"\n\t"sort"\n\t"strconv"\n)\n\n\/\/ Hash \u5b9a\u4e49\u54c8\u5e0c\u51fd\u6570\u7c7b\u578b\ntype Hash func(data []byte) uint32\n\n\/\/ Map \u4e00\u81f4\u6027\u54c8\u5e0c\u7ed3\u6784\ntype Map struct {\n\thash     Hash           \/\/ \u54c8\u5e0c\u51fd\u6570\n\treplicas int            \/\/ \u865a\u62df\u8282\u70b9\u500d\u6570\n\tkeys     []int          \/\/ \u54c8\u5e0c\u73af\n\thashMap  map[int]string \/\/ \u865a\u62df\u8282\u70b9\u4e0e\u771f\u5b9e\u8282\u70b9\u7684\u6620\u5c04\n}\n\n\/\/ New \u521b\u5efa\u4e00\u81f4\u6027\u54c8\u5e0c\u5b9e\u4f8b\nfunc New(replicas int, fn Hash) *Map {\n\tm := &Map{\n\t\treplicas: replicas,\n\t\thash:     fn,\n\t\thashMap:  make(map[int]string),\n\t}\n\tif m.hash == nil {\n\t\tm.hash = crc32.ChecksumIEEE \/\/ \u9ed8\u8ba4\u54c8\u5e0c\u51fd\u6570\n\t}\n\treturn m\n}\n\n\/\/ Add \u6dfb\u52a0\u8282\u70b9\u5230\u54c8\u5e0c\u73af\nfunc (m *Map) Add(keys ...string) {\n\tfor _, key := range keys {\n\t\tfor i := 0; i < m.replicas; i++ {\n\t\t\t\/\/ \u8ba1\u7b97\u865a\u62df\u8282\u70b9\u7684\u54c8\u5e0c\u503c\n\t\t\thash := int(m.hash([]byte(strconv.Itoa(i) + key)))\n\t\t\tm.keys = append(m.keys, hash)\n\t\t\tm.hashMap[hash] = key \/\/ \u865a\u62df\u8282\u70b9\u6620\u5c04\u5230\u771f\u5b9e\u8282\u70b9\n\t\t}\n\t}\n\tsort.Ints(m.keys) \/\/ \u6392\u5e8f\u54c8\u5e0c\u73af\n}\n\n\/\/ Get \u6839\u636ekey\u83b7\u53d6\u5bf9\u5e94\u7684\u8282\u70b9\nfunc (m *Map) Get(key string) string {\n\tif len(m.keys) == 0 {\n\t\treturn ""\n\t}\n\n\t\/\/ \u8ba1\u7b97key\u7684\u54c8\u5e0c\u503c\n\thash := int(m.hash([]byte(key)))\n\n\t\/\/ \u4e8c\u5206\u67e5\u627e\u7b2c\u4e00\u4e2a\u5927\u4e8e\u7b49\u4e8ehash\u7684\u8282\u70b9\n\tidx := sort.Search(len(m.keys), func(i int) bool {\n\t\treturn m.keys[i] >= hash\n\t})\n\n\t\/\/ \u5982\u679c\u6ca1\u627e\u5230\uff0c\u5219\u4f7f\u7528\u7b2c\u4e00\u4e2a\u8282\u70b9(\u73af\u72b6\u7ed3\u6784)\n\tif idx == len(m.keys) {\n\t\tidx = 0\n\t}\n\n\treturn m.hashMap[m.keys[idx]]\n}\n\n\/\/ Remove \u4ece\u54c8\u5e0c\u73af\u4e2d\u79fb\u9664\u8282\u70b9\nfunc (m *Map) Remove(key string) {\n\tfor i := 0; i < m.replicas; i++ {\n\t\thash := int(m.hash([]byte(strconv.Itoa(i) + key)))\n\t\t\/\/ \u4ece\u6392\u5e8f\u5217\u8868\u4e2d\u5220\u9664\n\t\tidx := sort.SearchInts(m.keys, hash)\n\t\tif idx < len(m.keys) && m.keys[idx] == hash {\n\t\t\tm.keys = append(m.keys[:idx], m.keys[idx+1:]...)\n\t\t}\n\t\t\/\/ \u4ece\u6620\u5c04\u4e2d\u5220\u9664\n\t\tdelete(m.hashMap, hash)\n\t}\n}\n<\/pre><\/div>\n\n\n
      \u4f7f\u7528\u793a\u4f8b<\/p>\n\n\n
      \npackage main\n\nimport (\n\t"fmt"\n\t"yourmodule\/consistenthash"\n)\n\nfunc main() {\n\t\/\/ \u521b\u5efa\u4e00\u81f4\u6027\u54c8\u5e0c\u5b9e\u4f8b\uff0c\u8bbe\u7f6e\u865a\u62df\u8282\u70b9\u6570\u4e3a3\n\tch := consistenthash.New(3, nil)\n\t\n\t\/\/ \u6dfb\u52a0\u8282\u70b9\n\tch.Add("Node1", "Node2", "Node3")\n\t\n\t\/\/ \u6d4b\u8bd5\u6570\u636e\u5206\u5e03\n\ttestKeys := []string{"key1", "key2", "key3", "key4", "key5"}\n\tfor _, key := range testKeys {\n\t\tfmt.Printf("Key %s is assigned to %s\\n", key, ch.Get(key))\n\t}\n\t\n\t\/\/ \u6dfb\u52a0\u65b0\u8282\u70b9\n\tfmt.Println("\\nAdding Node4...")\n\tch.Add("Node4")\n\tfor _, key := range testKeys {\n\t\tfmt.Printf("Key %s is now assigned to %s\\n", key, ch.Get(key))\n\t}\n\t\n\t\/\/ \u79fb\u9664\u8282\u70b9\n\tfmt.Println("\\nRemoving Node2...")\n\tch.Remove("Node2")\n\tfor _, key := range testKeys {\n\t\tfmt.Printf("Key %s is now assigned to %s\\n", key, ch.Get(key))\n\t}\n}\n<\/pre><\/div>\n\n\n
      \u5b9e\u73b0\u7ec6\u8282\u5206\u6790<\/p>\n\n\n\n
        \n
      1. \u54c8\u5e0c\u51fd\u6570\uff1a\u9ed8\u8ba4\u4f7f\u7528crc32.ChecksumIEEE<\/code>\uff0c\u4e5f\u53ef\u4ee5\u81ea\u5b9a\u4e49<\/li>\n\n\n\n
      2. \u865a\u62df\u8282\u70b9\uff1a\u901a\u8fc7replicas<\/code>\u53c2\u6570\u63a7\u5236\u6bcf\u4e2a\u7269\u7406\u8282\u70b9\u7684\u865a\u62df\u8282\u70b9\u6570\u91cf<\/li>\n\n\n\n
      3. \u54c8\u5e0c\u73af\uff1a\u4f7f\u7528\u6392\u5e8f\u7684\u5207\u7247\u5b9e\u73b0\uff0c\u4fbf\u4e8e\u4e8c\u5206\u67e5\u627e<\/li>\n\n\n\n
      4. \u8282\u70b9\u67e5\u627e\uff1a\u4f7f\u7528sort.Search<\/code>\u8fdb\u884c\u9ad8\u6548\u4e8c\u5206\u67e5\u627e<\/li>\n<\/ol>\n\n\n\n
        \u6027\u80fd\u8003\u8651<\/p>\n\n\n\n
          \n
        1. \u65f6\u95f4\u590d\u6742\u5ea6\uff1a
          \u2022 \u6dfb\u52a0\u8282\u70b9\uff1aO(n log n) \u4e3b\u8981\u6765\u81ea\u6392\u5e8f \u2022 \u67e5\u627e\u8282\u70b9\uff1aO(log n) \u4e8c\u5206\u67e5\u627e<\/li>\n\n\n\n
        2. \u7a7a\u95f4\u590d\u6742\u5ea6\uff1aO(n) \u5176\u4e2dn\u662f\u865a\u62df\u8282\u70b9\u603b\u6570<\/li>\n<\/ol>\n\n\n\n
          \n\n\n\n
          \u4e00\u81f4\u6027\u54c8\u5e0c\u7684\u5e94\u7528\u573a\u666f<\/strong><\/h2>\n\n\n\n
          <\/p>\n\n\n\n
          \u4e00\u3001\u5206\u5e03\u5f0f\u7f13\u5b58\u7cfb\u7edf<\/strong><\/p>\n\n\n\n
          \u7f13\u5b58\u670d\u52a1\u5668\u8d1f\u8f7d\u5747\u8861
          \u5178\u578b\u5e94\u7528\uff1aMemcached\u96c6\u7fa4\u3001Redis\u5ba2\u6237\u7aef\u5206\u7247<\/p>\n\n\n\n
            \n
          • \u5b9e\u73b0\u65b9\u5f0f\uff1a\n
              \n
            • \u7f13\u5b58\u952e\u901a\u8fc7 \u4e00\u81f4\u6027\u54c8\u5e0c\u6620\u5c04\u5230\u7279\u5b9a\u8282\u70b9<\/li>\n\n\n\n
            • \u8282\u70b9\u589e\u51cf\u65f6\u4ec5\u9700\u8fc1\u79fb\u76f8\u90bb\u8282\u70b9\u6570\u636e<\/li>\n<\/ul>\n<\/li>\n\n\n\n
            • \u4f18\u52bf\uff1a\n
                \n
              •  \u907f\u514d\u4f20\u7edf\u54c8\u5e0c\u5bfc\u81f4\u7684\u5168\u5c40\u7f13\u5b58\u5931\u6548<\/li>\n\n\n\n
              • \u63d0\u9ad8\u7f13\u5b58\u547d\u4e2d\u7387\uff08\u5982PHP\u7684Memcached\u6269\u5c55\u9ed8\u8ba4\u4f7f\u7528\u4e00\u81f4\u6027\u54c8\u5e0c\uff09<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n
                <\/p>\n\n\n\n
                \u4e8c\u3001\u5185\u5bb9\u5206\u53d1\u7f51\u7edc(CDN)<\/strong><\/p>\n\n\n\n
                \u8fb9\u7f18\u8282\u70b9\u8def\u7531
                \u5178\u578b\u5e94\u7528\uff1aAkamai\u3001Cloudflare\u7b49CDN\u670d\u52a1<\/p>\n\n\n\n
                <\/p>\n\n\n\n
                \u4e09\u3001\u8d1f\u8f7d\u5747\u8861\u5668<\/strong><\/p>\n\n\n\n
                \u4f1a\u8bdd\u4fdd\u6301(Sticky Session)
                \u5178\u578b\u5e94\u7528\uff1aNginx\u3001HAProxy\u7b49\u8d1f\u8f7d\u5747\u8861\u5668<\/p>\n\n\n\n
                  \n
                • \u5b9e\u73b0\u65b9\u5f0f\uff1a\n
                    \n
                  •  \u5c06\u7528\u6237IP\u6216SessionID\u54c8\u5e0c\u5230\u540e\u7aef\u670d\u52a1\u5668<\/li>\n\n\n\n
                  • \u76f8\u540c\u7528\u6237\u7684\u8bf7\u6c42\u59cb\u7ec8\u8def\u7531\u5230\u540c\u4e00\u670d\u52a1\u5668<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                  • \u4f18\u52bf\uff1a\n
                      \n
                    •  \u907f\u514d\u4f20\u7edf\u8f6e\u8be2\u5bfc\u81f4\u7684\u4f1a\u8bdd\u72b6\u6001\u4e22\u5931<\/li>\n\n\n\n
                    • \u540e\u7aef\u670d\u52a1\u5668\u589e\u51cf\u65f6\u5f71\u54cd\u6700\u5c0f<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n
                      \u56db\u3001\u5206\u5e03\u5f0f\u8ba1\u7b97<\/strong><\/p>\n\n\n\n
                      MapReduce\u4efb\u52a1\u5206\u914d
                      \u5178\u578b\u5e94\u7528\uff1aHadoop\u4efb\u52a1\u8c03\u5ea6<\/p>\n\n\n\n
                        \n
                      • \u5b9e\u73b0\u65b9\u5f0f\uff1a\n
                          \n
                        • \u5c06\u8f93\u5165\u6570\u636e\u5206\u7247\u901a\u8fc7\u54c8\u5e0c\u6620\u5c04\u5230\u5de5\u4f5c\u8282\u70b9<\/li>\n\n\n\n
                        • \u4fdd\u6301\u76f8\u540ckey\u7684\u6570\u636e\u53d1\u9001\u5230\u540c\u4e00Reducer<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                        • \u4f18\u52bf\uff1a\n
                            \n
                          • \u4fdd\u8bc1\u6570\u636e\u672c\u5730\u6027(Data Locality)<\/li>\n\n\n\n
                          • \u52a8\u6001\u8c03\u6574\u8ba1\u7b97\u8282\u70b9\u65f6\u4efb\u52a1\u8fc1\u79fb\u6700\u5c11<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n
                            \n\n\n\n
                            <\/p>\n","protected":false},"excerpt":{"rendered":"
                            \u4ec0\u4e48\u662f\u4e00\u81f4\u6027\u54c8\u5e0c\uff1f \u4e00\u81f4\u6027\u54c8\u5e0c\uff08Consistent Hashing\uff09\u662f\u4e00\u79cd\u7279\u6b8a\u7684\u54c8\u5e0c\u6280\u672f\uff0c\u4e3b\u8981\u7528\u4e8e\u5206\u5e03\u5f0f\u7cfb\u7edf […]<\/p>\n","protected":false},"author":1,"featured_media":1028,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[4],"tags":[155],"class_list":["post-1025","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithm","tag-155"],"_links":{"self":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/1025","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1025"}],"version-history":[{"count":4,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/1025\/revisions"}],"predecessor-version":[{"id":1031,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/1025\/revisions\/1031"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/media\/1028"}],"wp:attachment":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1025"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1025"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1025"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}