1 /** 2 * Copyright 2021 Huawei Technologies Co., Ltd 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef MINDSPORE_CCSRC_FL_SERVER_CONSISTENT_HASH_RING_H_ 18 #define MINDSPORE_CCSRC_FL_SERVER_CONSISTENT_HASH_RING_H_ 19 20 #include <map> 21 #include <string> 22 #include "utils/log_adapter.h" 23 24 namespace mindspore { 25 namespace fl { 26 namespace server { 27 constexpr uint32_t kDefaultVirtualNodeNum = 32; 28 // To support distributed storage and make servers easy to scale-out and scale-in for a large load of metadata in 29 // server, we use class ConsistentHashRing to help servers find out which metadata is stored in which server node. 30 31 // Class ConsistentHashRing implements the algorithm described in the paper 32 // <https://dl.acm.org/doi/pdf/10.1145/258533.258660>. 33 34 // This class will create a ring for hash values of metadata and server nodes. Each server could use this ring to 35 // retrieve data stored in other servers according to the hash keys. The time complexity for adding/deleting/searching 36 // of this algorithm is basically O(log n). 37 class ConsistentHashRing { 38 public: 39 // The parameter virtual_node_num for constructor means the virtual node number to be created for each physical server 40 // node. According to the paper, these virtual nodes could help spread data to all the servers and ensuring balancing 41 // at the same time. And when we say "adding/deleting/searching", we are talking about operations on thease virtual 42 // nodes instead of the physical nodes. virtual_node_num_(virtual_node_num)43 explicit ConsistentHashRing(uint32_t virtual_node_num = 128) : virtual_node_num_(virtual_node_num) {} 44 ~ConsistentHashRing() = default; 45 46 // Insert several virtual nodes for a server into this ring according to its rank id. 47 bool Insert(uint32_t rank); 48 49 // Remove virtual nodes for a server according to its rank id. 50 bool Erase(uint32_t rank); 51 52 // Find the physical server node's rank according to the metadata's key. 53 uint32_t Find(const std::string &key); 54 55 private: 56 uint32_t virtual_node_num_; 57 // The hash ring for the server nodes. 58 // Key is the hash value of the virtual node. 59 // Value is the physical node' rank id. 60 std::map<size_t, uint32_t> ring_; 61 }; 62 } // namespace server 63 } // namespace fl 64 } // namespace mindspore 65 #endif // MINDSPORE_CCSRC_FL_SERVER_CONSISTENT_HASH_RING_H_ 66