From 7f4ae9312314c329b63c850e09b403a95ad18bed Mon Sep 17 00:00:00 2001
From: David Zafman <dzafman@redhat.com>
Date: Thu, 14 Nov 2019 21:10:28 -0800
Subject: [PATCH] osd: ceph_pg_upmaps() use max_deviation to determine perfect
 distribution

Signed-off-by: David Zafman <dzafman@redhat.com>
---
 src/common/options.cc             |  6 ---
 src/mgr/PyOSDMap.cc               |  4 +-
 src/osd/OSDMap.cc                 | 86 ++++++++++++++-----------------
 src/osd/OSDMap.h                  |  2 +-
 src/pybind/mgr/balancer/module.py |  9 ++--
 src/test/osd/TestOSDMap.cc        |  6 +--
 src/tools/osdmaptool.cc           |  8 ++-
 7 files changed, 54 insertions(+), 67 deletions(-)

diff --git a/src/common/options.cc b/src/common/options.cc
index 67bea89ef3e..81ef3cd3452 100644
--- a/src/common/options.cc
+++ b/src/common/options.cc
@@ -2351,12 +2351,6 @@ std::vector<Option> get_global_options() {
                      "by doing a fairly exhaustive search of existing PGs "
                      "that can be unmapped or upmapped"),
 
-    Option("osd_calc_pg_upmaps_max_stddev", Option::TYPE_FLOAT, Option::LEVEL_ADVANCED)
-    .set_default(1.0)
-    .set_flag(Option::FLAG_RUNTIME)
-    .set_description("standard deviation below which there is no attempt made "
-                     "while trying to calculate PG upmaps"),
-
     Option("osd_calc_pg_upmaps_local_fallback_retries", Option::TYPE_UINT, Option::LEVEL_ADVANCED)
     .set_default(100)
     .set_flag(Option::FLAG_RUNTIME)
diff --git a/src/mgr/PyOSDMap.cc b/src/mgr/PyOSDMap.cc
index dd67ae223e4..681546a8f7f 100644
--- a/src/mgr/PyOSDMap.cc
+++ b/src/mgr/PyOSDMap.cc
@@ -114,9 +114,9 @@ static PyObject *osdmap_calc_pg_upmaps(BasePyOSDMap* self, PyObject *args)
 {
   PyObject *pool_list;
   BasePyOSDMapIncremental *incobj;
-  double max_deviation = 0;
+  int max_deviation = 0;
   int max_iterations = 0;
-  if (!PyArg_ParseTuple(args, "OdiO:calc_pg_upmaps",
+  if (!PyArg_ParseTuple(args, "OiiO:calc_pg_upmaps",
 			&incobj, &max_deviation,
 			&max_iterations, &pool_list)) {
     return nullptr;
diff --git a/src/osd/OSDMap.cc b/src/osd/OSDMap.cc
index 521e021a6bb..7d7037d5e38 100644
--- a/src/osd/OSDMap.cc
+++ b/src/osd/OSDMap.cc
@@ -4504,13 +4504,16 @@ bool OSDMap::try_pg_upmap(
 
 int OSDMap::calc_pg_upmaps(
   CephContext *cct,
-  float max_deviation_ratio,
+  uint32_t max_deviation,
   int max,
   const set<int64_t>& only_pools,
   OSDMap::Incremental *pending_inc)
 {
   ldout(cct, 10) << __func__ << " pools " << only_pools << dendl;
   OSDMap tmp;
+  // Can't be less than 1 pg
+  if (max_deviation < 1)
+    max_deviation = 1;
   tmp.deepish_copy_from(*this);
   int num_changed = 0;
   map<int,set<pg_t>> pgs_by_osd;
@@ -4572,10 +4575,10 @@ int OSDMap::calc_pg_upmaps(
     lderr(cct) << __func__ << " abort due to max <= 0" << dendl;
     return 0;
   }
-  float decay_factor = 1.0 / float(max);
   float stddev = 0;
   map<int,float> osd_deviation;       // osd, deviation(pgs)
   multimap<float,int> deviation_osd;  // deviation(pgs), osd
+  float cur_max_deviation = 0;
   for (auto& i : pgs_by_osd) {
     // make sure osd is still there (belongs to this crush-tree)
     ceph_assert(osd_weight.count(i.first));
@@ -4589,8 +4592,11 @@ int OSDMap::calc_pg_upmaps(
     osd_deviation[i.first] = deviation;
     deviation_osd.insert(make_pair(deviation, i.first));
     stddev += deviation * deviation;
+    if (fabsf(deviation) > cur_max_deviation)
+      cur_max_deviation = fabsf(deviation);
   }
-  if (stddev <= cct->_conf.get_val<double>("osd_calc_pg_upmaps_max_stddev")) {
+  ldout(cct, 20) << " stdev " << stddev << " max_deviation " << cur_max_deviation << dendl;
+  if (cur_max_deviation <= max_deviation) {
     ldout(cct, 10) << __func__ << " distribution is almost perfect"
                    << dendl;
     return 0;
@@ -4601,50 +4607,28 @@ int OSDMap::calc_pg_upmaps(
   auto local_fallback_retries =
     cct->_conf.get_val<uint64_t>("osd_calc_pg_upmaps_local_fallback_retries");
   while (max--) {
+    ldout(cct, 30) << "Top of loop #" << max+1 << dendl;
     // build overfull and underfull
     set<int> overfull;
     vector<int> underfull;
-    float decay = 0;
-    int decay_count = 0;
-    while (overfull.empty()) {
-      for (auto i = deviation_osd.rbegin(); i != deviation_osd.rend(); i++) {
-        if (i->first >= (1.0 - decay))
-          overfull.insert(i->second);
+    for (auto i = deviation_osd.rbegin(); i != deviation_osd.rend(); i++) {
+        ldout(cct, 30) << " check " << i->first << " <= " << max_deviation << dendl;
+        if (i->first <= max_deviation)
+	  break;
+	ldout(cct, 30) << " add overfull osd." << i->second << dendl;
+        overfull.insert(i->second);
       }
-      if (!overfull.empty())
-        break;
-      decay_count++;
-      decay = decay_factor * decay_count;
-      if (decay >= 1.0)
-        break;
-      ldout(cct, 30) << " decay_factor = " << decay_factor
-                     << " decay_count = " << decay_count
-                     << " decay (overfull) = " << decay
-                     << dendl;
-    }
     if (overfull.empty()) {
       ldout(cct, 20) << __func__ << " failed to build overfull" << dendl;
       break;
     }
 
-    decay = 0;
-    decay_count = 0;
-    while (underfull.empty()) {
-      for (auto i = deviation_osd.begin(); i != deviation_osd.end(); i++) {
-        if (i->first >= (-.999 + decay))
+    for (auto i = deviation_osd.begin(); i != deviation_osd.end(); i++) {
+        ldout(cct, 30) << " check " << i->first << " >= " << -(int)max_deviation << dendl;
+        if (i->first >= -(int)max_deviation)
           break;
+	ldout(cct, 30) << " add underfull osd." << i->second << dendl;
         underfull.push_back(i->second);
-      }
-      if (!underfull.empty())
-        break;
-      decay_count++;
-      decay = decay_factor * decay_count;
-      if (decay >= .999)
-        break;
-      ldout(cct, 30) << " decay_factor = " << decay_factor
-                     << " decay_count = " << decay_count
-                     << " decay (underfull) = " << decay
-                     << dendl;
     }
     if (underfull.empty()) {
       ldout(cct, 20) << __func__ << " failed to build underfull" << dendl;
@@ -4671,14 +4655,16 @@ int OSDMap::calc_pg_upmaps(
       int osd = p->second;
       float deviation = p->first;
       float target = osd_weight[osd] * pgs_per_weight;
+      ldout(cct, 10) << " Overfull search osd." << osd
+                       << " target " << target
+                       << " deviation " << deviation
+		       << dendl;
       ceph_assert(target > 0);
-      float deviation_ratio = deviation / target;
-      if (deviation_ratio < max_deviation_ratio) {
+      if (deviation <= max_deviation) {
 	ldout(cct, 10) << " osd." << osd
                        << " target " << target
                        << " deviation " << deviation
-                       << " -> ratio " << deviation_ratio
-                       << " < max ratio " << max_deviation_ratio
+                       << " < max deviation " << max_deviation
                        << dendl;
 	break;
       }
@@ -4817,14 +4803,13 @@ int OSDMap::calc_pg_upmaps(
       float deviation = p.first;
       float target = osd_weight[osd] * pgs_per_weight;
       ceph_assert(target > 0);
-      float deviation_ratio = abs(deviation / target);
-      if (deviation_ratio < max_deviation_ratio) {
-        // respect max_deviation_ratio too
+      if (fabsf(deviation) < max_deviation) {
+        // respect max_deviation too
         ldout(cct, 10) << " osd." << osd
                        << " target " << target
                        << " deviation " << deviation
-                       << " -> absolute ratio " << deviation_ratio
-                       << " < max ratio " << max_deviation_ratio
+                       << " -> absolute " << fabsf(deviation)
+                       << " < max " << max_deviation
                        << dendl;
         break;
       }
@@ -4910,6 +4895,7 @@ int OSDMap::calc_pg_upmaps(
     float new_stddev = 0;
     map<int,float> temp_osd_deviation;
     multimap<float,int> temp_deviation_osd;
+    float cur_max_deviation = 0;
     for (auto& i : temp_pgs_by_osd) {
       // make sure osd is still there (belongs to this crush-tree)
       ceph_assert(osd_weight.count(i.first));
@@ -4922,7 +4908,9 @@ int OSDMap::calc_pg_upmaps(
                      << dendl;
       temp_osd_deviation[i.first] = deviation;
       temp_deviation_osd.insert(make_pair(deviation, i.first));
-      new_stddev += deviation * deviation;
+       new_stddev += deviation * deviation;
+      if (fabsf(deviation) > cur_max_deviation)
+        cur_max_deviation = fabsf(deviation);
     }
     ldout(cct, 10) << " stddev " << stddev << " -> " << new_stddev << dendl;
     if (new_stddev >= stddev) {
@@ -4974,6 +4962,12 @@ int OSDMap::calc_pg_upmaps(
       pending_inc->new_pg_upmap_items[i.first] = i.second;
       ++num_changed;
     }
+    ldout(cct, 20) << " stdev " << stddev << " max_deviation " << cur_max_deviation << dendl;
+    if (cur_max_deviation <= max_deviation) {
+      ldout(cct, 10) << __func__ << " Optimization plan is almost perfect"
+                     << dendl;
+      break;
+    }
   }
   ldout(cct, 10) << " num_changed = " << num_changed << dendl;
   return num_changed;
diff --git a/src/osd/OSDMap.h b/src/osd/OSDMap.h
index f0055611b27..9eb75b865ad 100644
--- a/src/osd/OSDMap.h
+++ b/src/osd/OSDMap.h
@@ -1438,7 +1438,7 @@ public:
 
   int calc_pg_upmaps(
     CephContext *cct,
-    float max_deviation, ///< max deviation from target (value < 1.0)
+    uint32_t max_deviation, ///< max deviation from target (value >= 1)
     int max_iterations,  ///< max iterations to run
     const std::set<int64_t>& pools,        ///< [optional] restrict to pool
     Incremental *pending_inc
diff --git a/src/pybind/mgr/balancer/module.py b/src/pybind/mgr/balancer/module.py
index 2c92180dbcb..e2ce6cf3a3e 100644
--- a/src/pybind/mgr/balancer/module.py
+++ b/src/pybind/mgr/balancer/module.py
@@ -303,12 +303,11 @@ class Module(MgrModule):
         },
         {
             'name': 'upmap_max_deviation',
-            'type': 'float',
-            'default': .01,
-            'min': 0,
-            'max': 1,
+            'type': 'int',
+            'default': 1,
+            'min': 1,
             'desc': 'deviation below which no optimization is attempted',
-            'long_desc': 'If the ratio between the fullest and least-full OSD is below this value then we stop trying to optimize placement.',
+            'long_desc': 'If the number of PGs are within this count then no optimization is attempted',
             'runtime': True,
         },
         {
diff --git a/src/test/osd/TestOSDMap.cc b/src/test/osd/TestOSDMap.cc
index f5bb2b33c46..e35e360521e 100644
--- a/src/test/osd/TestOSDMap.cc
+++ b/src/test/osd/TestOSDMap.cc
@@ -1323,15 +1323,11 @@ TEST_F(OSDMapTest, BUG_38897) {
 
   // ready to go
   {
-    // require perfect distribution!
-    auto ret = g_ceph_context->_conf.set_val(
-      "osd_calc_pg_upmaps_max_stddev", "0");
-    ASSERT_EQ(0, ret);
-    g_ceph_context->_conf.apply_changes(nullptr);
     set<int64_t> only_pools;
     ASSERT_TRUE(pool_1_id >= 0);
     only_pools.insert(pool_1_id);
     OSDMap::Incremental pending_inc(osdmap.get_epoch() + 1);
+    // require perfect distribution! (max deviation 0)
     osdmap.calc_pg_upmaps(g_ceph_context,
                           0, // so we can force optimizing
                           100,
diff --git a/src/tools/osdmaptool.cc b/src/tools/osdmaptool.cc
index cb9787dd691..5221c4f79fc 100644
--- a/src/tools/osdmaptool.cc
+++ b/src/tools/osdmaptool.cc
@@ -53,7 +53,7 @@ void usage()
   cout << "                           writing commands to <file> [default: - for stdout]" << std::endl;
   cout << "   --upmap-max <max-count> set max upmap entries to calculate [default: 10]" << std::endl;
   cout << "   --upmap-deviation <max-deviation>" << std::endl;
-  cout << "                           max deviation from target [default: .01]" << std::endl;
+  cout << "                           max deviation from target [default: 1]" << std::endl;
   cout << "   --upmap-pool <poolname> restrict upmap balancing to 1 or more pools" << std::endl;
   cout << "   --upmap-save            write modified OSDMap with upmap changes" << std::endl;
   cout << "   --dump <format>         displays the map in plain text when <format> is 'plain', 'json' if specified format is not supported" << std::endl;
@@ -143,7 +143,7 @@ int main(int argc, const char **argv)
   bool health = false;
   std::string upmap_file = "-";
   int upmap_max = 10;
-  float upmap_deviation = .01;
+  int upmap_deviation = 1;
   std::set<std::string> upmap_pools;
   int64_t pg_num = -1;
   bool test_map_pgs_dump_all = false;
@@ -255,6 +255,10 @@ int main(int argc, const char **argv)
     cerr << me << ": too many arguments" << std::endl;
     usage();
   }
+  if (upmap_deviation < 1) {
+    cerr << me << ": upmap-deviation must be >= 1" << std::endl;
+    usage();
+  }
   fn = args[0];
 
   if (range_first >= 0 && range_last >= 0) {
-- 
2.39.5