| // Licensed to the Apache Software Foundation (ASF) under one |
| // or more contributor license agreements. See the NOTICE file |
| // distributed with this work for additional information |
| // regarding copyright ownership. The ASF licenses this file |
| // to you under the Apache License, Version 2.0 (the |
| // "License"); you may not use this file except in compliance |
| // with the License. You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, |
| // software distributed under the License is distributed on an |
| // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| // KIND, either express or implied. See the License for the |
| // specific language governing permissions and limitations |
| // under the License. |
| |
| #pragma once |
| |
| #include <cstddef> |
| #include <memory> |
| #include <set> |
| #include <string> |
| #include <unordered_map> |
| #include <unordered_set> |
| |
| #include <boost/optional/optional.hpp> |
| #include <gtest/gtest_prod.h> |
| |
| #include "kudu/master/ts_descriptor.h" |
| #include "kudu/util/status.h" |
| |
| namespace kudu { |
| |
| class ThreadSafeRandom; |
| |
| namespace master { |
| |
| // Utility class to help place tablet replicas on tablet servers according |
| // to the location awareness policy. Currently, this class implements the logic |
| // specific to location awareness as described in [1], but it could enforce |
| // other placement policies in the future. |
| // |
| // In essence (for details see [1]), the location awareness placement policy |
| // is about: |
| // * in case of N locations, N > 2, not placing the majority of replicas |
| // in one location |
| // * spreading replicas evenly among available locations |
| // * within a location, spreading load evenly among tablet servers |
| // |
| // [1] https://s.apache.org/location-awareness-design |
| // |
| // TODO(aserbin): add a link to the doc once it appears in the upstream repo. |
| // |
| // NOTE: in the implementation of this class, it's OK to use an empty string |
| // in place of boost::none for a location because valid location strings begin |
| // with '/' and therefore are nonempty. |
| class PlacementPolicy { |
| public: |
| |
| // The 'descs' vector contains information on all available tablet servers |
| // in the cluster, the 'rng' parameter points to an instance of a random |
| // generator that the object references to. The random generator instance |
| // must not be nullptr and must outlive the PlacementPolicy object. |
| PlacementPolicy(TSDescriptorVector descs, |
| ThreadSafeRandom* rng); |
| |
| virtual ~PlacementPolicy() = default; |
| |
| size_t ts_num() const { return ts_num_; } |
| |
| // Select tablet servers to host the given number of replicas for a tablet. |
| // |
| // Parameters: |
| // 'nreplicas' The 'nreplicas' parameter specifies the desired replication factor. |
| // 'dimension' The 'dimension' parameter specifies the dimension information of the tablet. |
| // If not none, place tablet replicas based on the number of tablets in a |
| // dimension. Otherwise, based on the number of tablets at a tablet server. |
| // 'ts_descs' The result set of tablet server descriptors is output into the 'ts_descs' |
| // placeholder (must not be null). |
| Status PlaceTabletReplicas(int nreplicas, |
| const boost::optional<std::string>& dimension, |
| TSDescriptorVector* ts_descs) const; |
| |
| // Select tablet server to host an additional tablet replica. |
| // |
| // Parameters: |
| // 'existing' The 'existing' parameter lists current members of the tablet's |
| // Raft configuration. |
| // 'dimension' The 'dimension' parameter specifies the dimension information of the tablet. |
| // If not none, place tablet replicas based on the number of tablets in a |
| // dimension. Otherwise, based on the number of tablets at a tablet server. |
| // 'ts_desc' The new member is output into 'ts_desc' placeholer (must not be null). |
| Status PlaceExtraTabletReplica(TSDescriptorVector existing, |
| const boost::optional<std::string>& dimension, |
| std::shared_ptr<TSDescriptor>* ts_desc) const; |
| |
| private: |
| // Tablet server descriptors per location. This is the most comprehensive |
| // information on how tablet servers are placed among locations. Inherently, |
| // the locations have a sense of proximity and a hierarchy, so '/mega/turbo0' |
| // is closer to '/mega/turbo1' than '/giga/awesome0' and both '/mega/turbo0' |
| // and '/mega/turbo1' are affected by conditions currently affecting '/mega'. |
| // Number of locations is not supposed to be high: at the order of magnitude |
| // scale, that's about tens. |
| // |
| // NOTE: this dictionary container is made unordered since currently no code |
| // is taking advantage of the order of the keys. |
| typedef std::unordered_map<std::string, TSDescriptorVector> |
| LocationToDescriptorsMap; |
| |
| // Number of tablet replicas per location. |
| typedef std::unordered_map<std::string, int> ReplicaLocationsInfo; |
| |
| friend class PlacementPolicyTest; |
| FRIEND_TEST(PlacementPolicyTest, SelectLocationRandomnessForExtraReplica); |
| |
| // Get the load of the location: a location with N tablet servers and |
| // R replicas has load R/N. |
| // |
| // Parameters: |
| // 'location' The location in question. |
| // 'locations_info' Information on tablet replicas slated for placement, |
| // but not created yet. That's the placement information |
| // on to-be-replicas in the context of optimizing tablet |
| // replica distribution in the cluster. |
| double GetLocationLoad(const std::string& location, |
| const ReplicaLocationsInfo& locations_info) const; |
| |
| // Select locations to place the given number of replicas ('nreplicas') for |
| // a new tablet. The locations are chosen according to the placement |
| // policies. |
| // |
| // TODO (aserbin): add the reference to the document once it's in the repo. |
| Status SelectReplicaLocations(int nreplicas, |
| ReplicaLocationsInfo* locations_info) const; |
| |
| // Select the given number ('nreplicas') from the set of specified tablet |
| // servers to place tablet replicas. |
| Status SelectReplicas(const TSDescriptorVector& source_ts_descs, |
| int nreplicas, |
| const boost::optional<std::string>& dimension, |
| TSDescriptorVector* result_ts_descs) const; |
| |
| // Given the tablet servers in 'ts_descs', pick a tablet server to host |
| // a tablet replica, excluding tablet servers in 'excluded'. If there are no |
| // servers in 'ts_descs' that are not in 'existing', return nullptr. |
| std::shared_ptr<TSDescriptor> SelectReplica( |
| const TSDescriptorVector& ts_descs, |
| const boost::optional<std::string>& dimension, |
| const std::set<std::shared_ptr<TSDescriptor>>& excluded) const; |
| |
| // Select location for next replica of a tablet with the specified replication |
| // factor. In essence, the algorithm picks the least loaded location, |
| // making sure no location contains the majority of replicas of the tablet, |
| // if possible. |
| // |
| // Parameters: |
| // 'num_replicas' The total number of tablet replicas to place. |
| // 'locations_info' Information on tablet replicas slated for placement, |
| // but not created yet. That's the placement information |
| // on to-be-replicas in the context of optimizing tablet |
| // replica distribution in the cluster. |
| // 'location' The result location pointer, must not be null. |
| Status SelectLocation(int num_replicas, |
| const ReplicaLocationsInfo& locations_info, |
| std::string* location) const; |
| |
| // Number of available tablet servers. |
| const size_t ts_num_; |
| |
| // Random number generator used for selecting replica locations. |
| // The object that rng_ points at is supposed to be available during the whole |
| // lifetime of a PlacementPolicy object. |
| mutable ThreadSafeRandom* rng_; |
| |
| // Location to TSDescriptorVector map: the distribution of all already |
| // existing tablet replicas among available tablet servers in the cluster, |
| // grouped by location. |
| LocationToDescriptorsMap ltd_; |
| |
| // A set of known tablet server identifiers (derived from ltd_). |
| std::unordered_set<std::string> known_ts_ids_; |
| }; |
| |
| } // namespace master |
| } // namespace kudu |
