Adding upstream version 18.2.2.upstream/18.2.2

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

6 files changed, 2071 insertions, 0 deletions

diff --git a/src/pybind/mgr/pg_autoscaler/__init__.py b/src/pybind/mgr/pg_autoscaler/__init__.py
new file mode 100644
index 000000000..2394d37e5
--- /dev/null
+++ b/src/pybind/mgr/pg_autoscaler/__init__.py
@@ -0,0 +1,6 @@
+import os
+
+if 'UNITTEST' in os.environ:
+    import tests
+
+from .module import PgAutoscaler, effective_target_ratio
diff --git a/src/pybind/mgr/pg_autoscaler/module.py b/src/pybind/mgr/pg_autoscaler/module.py
new file mode 100644
index 000000000..ea7c4b00b
--- /dev/null
+++ b/src/pybind/mgr/pg_autoscaler/module.py
@@ -0,0 +1,838 @@
+"""
+Automatically scale pg_num based on how much data is stored in each pool.
+"""
+
+import json
+import mgr_util
+import threading
+from typing import Any, Dict, List, Optional, Set, Tuple, TYPE_CHECKING, Union
+import uuid
+from prettytable import PrettyTable
+from mgr_module import HealthChecksT, CLIReadCommand, CLIWriteCommand, CRUSHMap, MgrModule, Option, OSDMap
+
+"""
+Some terminology is made up for the purposes of this module:
+
+ - "raw pgs": pg count after applying replication, i.e. the real resource
+              consumption of a pool.
+ - "grow/shrink" - increase/decrease the pg_num in a pool
+ - "crush subtree" - non-overlapping domains in crush hierarchy: used as
+                     units of resource management.
+"""
+
+INTERVAL = 5
+
+PG_NUM_MIN = 32  # unless specified on a per-pool basis
+
+if TYPE_CHECKING:
+    import sys
+    if sys.version_info >= (3, 8):
+        from typing import Literal
+    else:
+        from typing_extensions import Literal
+
+    PassT = Literal['first', 'second', 'third']
+
+
+def nearest_power_of_two(n: int) -> int:
+    v = int(n)
+
+    v -= 1
+    v |= v >> 1
+    v |= v >> 2
+    v |= v >> 4
+    v |= v >> 8
+    v |= v >> 16
+
+    # High bound power of two
+    v += 1
+
+    # Low bound power of tow
+    x = v >> 1
+
+    return x if (v - n) > (n - x) else v
+
+
+def effective_target_ratio(target_ratio: float,
+                           total_target_ratio: float,
+                           total_target_bytes: int,
+                           capacity: int) -> float:
+    """
+    Returns the target ratio after normalizing for ratios across pools and
+    adjusting for capacity reserved by pools that have target_size_bytes set.
+    """
+    target_ratio = float(target_ratio)
+    if total_target_ratio:
+        target_ratio = target_ratio / total_target_ratio
+
+    if total_target_bytes and capacity:
+        fraction_available = 1.0 - min(1.0, float(total_target_bytes) / capacity)
+        target_ratio *= fraction_available
+
+    return target_ratio
+
+
+class PgAdjustmentProgress(object):
+    """
+    Keeps the initial and target pg_num values
+    """
+
+    def __init__(self, pool_id: int, pg_num: int, pg_num_target: int) -> None:
+        self.ev_id = str(uuid.uuid4())
+        self.pool_id = pool_id
+        self.reset(pg_num, pg_num_target)
+
+    def reset(self, pg_num: int, pg_num_target: int) -> None:
+        self.pg_num = pg_num
+        self.pg_num_target = pg_num_target
+
+    def update(self, module: MgrModule, progress: float) -> None:
+        desc = 'increasing' if self.pg_num < self.pg_num_target else 'decreasing'
+        module.remote('progress', 'update', self.ev_id,
+                      ev_msg="PG autoscaler %s pool %d PGs from %d to %d" %
+                      (desc, self.pool_id, self.pg_num, self.pg_num_target),
+                      ev_progress=progress,
+                      refs=[("pool", self.pool_id)])
+
+
+class CrushSubtreeResourceStatus:
+    def __init__(self) -> None:
+        self.root_ids: List[int] = []
+        self.osds: Set[int] = set()
+        self.osd_count: Optional[int] = None  # Number of OSDs
+        self.pg_target: Optional[int] = None  # Ideal full-capacity PG count?
+        self.pg_current = 0  # How many PGs already?
+        self.pg_left = 0
+        self.capacity: Optional[int] = None  # Total capacity of OSDs in subtree
+        self.pool_ids: List[int] = []
+        self.pool_names: List[str] = []
+        self.pool_count: Optional[int] = None
+        self.pool_used = 0
+        self.total_target_ratio = 0.0
+        self.total_target_bytes = 0  # including replication / EC overhead
+
+
+class PgAutoscaler(MgrModule):
+    """
+    PG autoscaler.
+    """
+    NATIVE_OPTIONS = [
+        'mon_target_pg_per_osd',
+        'mon_max_pg_per_osd',
+    ]
+
+    MODULE_OPTIONS = [
+        Option(
+            name='sleep_interval',
+            type='secs',
+            default=60),
+
+        Option(
+            name='threshold',
+            type='float',
+            desc='scaling threshold',
+            long_desc=('The factor by which the `NEW PG_NUM` must vary from the current'
+                       '`PG_NUM` before being accepted. Cannot be less than 1.0'),
+            default=3.0,
+            min=1.0),
+    ]
+
+    def __init__(self, *args: Any, **kwargs: Any) -> None:
+        super(PgAutoscaler, self).__init__(*args, **kwargs)
+        self._shutdown = threading.Event()
+        self._event: Dict[int, PgAdjustmentProgress] = {}
+
+        # So much of what we do peeks at the osdmap that it's easiest
+        # to just keep a copy of the pythonized version.
+        self._osd_map = None
+        if TYPE_CHECKING:
+            self.sleep_interval = 60
+            self.mon_target_pg_per_osd = 0
+            self.threshold = 3.0
+
+    def config_notify(self) -> None:
+        for opt in self.NATIVE_OPTIONS:
+            setattr(self,
+                    opt,
+                    self.get_ceph_option(opt))
+            self.log.debug(' native option %s = %s', opt, getattr(self, opt))
+        for opt in self.MODULE_OPTIONS:
+            setattr(self,
+                    opt['name'],
+                    self.get_module_option(opt['name']))
+            self.log.debug(' mgr option %s = %s',
+                           opt['name'], getattr(self, opt['name']))
+
+    @CLIReadCommand('osd pool autoscale-status')
+    def _command_autoscale_status(self, format: str = 'plain') -> Tuple[int, str, str]:
+        """
+        report on pool pg_num sizing recommendation and intent
+        """
+        osdmap = self.get_osdmap()
+        pools = osdmap.get_pools_by_name()
+        ps, root_map = self._get_pool_status(osdmap, pools)
+
+        if format in ('json', 'json-pretty'):
+            return 0, json.dumps(ps, indent=4, sort_keys=True), ''
+        else:
+            table = PrettyTable(['POOL', 'SIZE', 'TARGET SIZE',
+                                 'RATE', 'RAW CAPACITY',
+                                 'RATIO', 'TARGET RATIO',
+                                 'EFFECTIVE RATIO',
+                                 'BIAS',
+                                 'PG_NUM',
+#                                 'IDEAL',
+                                 'NEW PG_NUM', 'AUTOSCALE',
+                                 'BULK'],
+                                border=False)
+            table.left_padding_width = 0
+            table.right_padding_width = 2
+            table.align['POOL'] = 'l'
+            table.align['SIZE'] = 'r'
+            table.align['TARGET SIZE'] = 'r'
+            table.align['RATE'] = 'r'
+            table.align['RAW CAPACITY'] = 'r'
+            table.align['RATIO'] = 'r'
+            table.align['TARGET RATIO'] = 'r'
+            table.align['EFFECTIVE RATIO'] = 'r'
+            table.align['BIAS'] = 'r'
+            table.align['PG_NUM'] = 'r'
+#            table.align['IDEAL'] = 'r'
+            table.align['NEW PG_NUM'] = 'r'
+            table.align['AUTOSCALE'] = 'l'
+            table.align['BULK'] = 'l'
+            for p in ps:
+                if p['would_adjust']:
+                    final = str(p['pg_num_final'])
+                else:
+                    final = ''
+                if p['target_bytes'] > 0:
+                    ts = mgr_util.format_bytes(p['target_bytes'], 6)
+                else:
+                    ts = ''
+                if p['target_ratio'] > 0.0:
+                    tr = '%.4f' % p['target_ratio']
+                else:
+                    tr = ''
+                if p['effective_target_ratio'] > 0.0:
+                    etr = '%.4f' % p['effective_target_ratio']
+                else:
+                    etr = ''
+                table.add_row([
+                    p['pool_name'],
+                    mgr_util.format_bytes(p['logical_used'], 6),
+                    ts,
+                    p['raw_used_rate'],
+                    mgr_util.format_bytes(p['subtree_capacity'], 6),
+                    '%.4f' % p['capacity_ratio'],
+                    tr,
+                    etr,
+                    p['bias'],
+                    p['pg_num_target'],
+#                    p['pg_num_ideal'],
+                    final,
+                    'off' if self.has_noautoscale_flag() else p['pg_autoscale_mode'],
+                    str(p['bulk'])
+                ])
+            return 0, table.get_string(), ''
+
+    @CLIWriteCommand("osd pool set threshold")
+    def set_scaling_threshold(self, num: float) -> Tuple[int, str, str]:
+        """
+        set the autoscaler threshold 
+        A.K.A. the factor by which the new PG_NUM must vary from the existing PG_NUM
+        """
+        if num < 1.0:
+            return 22, "", "threshold cannot be set less than 1.0"
+        self.set_module_option("threshold", num)
+        return 0, "threshold updated", ""
+
+    def complete_all_progress_events(self) -> None:
+        for pool_id in list(self._event):
+            ev = self._event[pool_id]
+            self.remote('progress', 'complete', ev.ev_id)
+            del self._event[pool_id]
+
+    def has_noautoscale_flag(self) -> bool:
+        flags = self.get_osdmap().dump().get('flags', '')
+        if 'noautoscale' in flags:
+            return True
+        else:
+            return False
+
+    @CLIWriteCommand("osd pool get noautoscale")
+    def get_noautoscale(self) -> Tuple[int, str, str]:
+        """
+        Get the noautoscale flag to see if all pools
+        are setting the autoscaler on or off as well
+        as newly created pools in the future.
+        """
+        if self.has_noautoscale_flag():
+            return 0, "", "noautoscale is on"
+        else:
+            return 0, "", "noautoscale is off"
+
+    @CLIWriteCommand("osd pool unset noautoscale")
+    def unset_noautoscale(self) -> Tuple[int, str, str]:
+        """
+        Unset the noautoscale flag so all pools will
+        go back to its previous mode. Newly created
+        pools in the future will autoscaler on by default.
+        """
+        if not self.has_noautoscale_flag():
+            return 0, "", "noautoscale is already unset!"
+        else:
+            self.mon_command({
+                'prefix': 'config set',
+                'who': 'global',
+                'name': 'osd_pool_default_pg_autoscale_mode',
+                'value': 'on'
+            })
+            self.mon_command({
+                'prefix': 'osd unset',
+                'key': 'noautoscale'
+            })
+            return 0, "", "noautoscale is unset, all pools now back to its previous mode"
+
+    @CLIWriteCommand("osd pool set noautoscale")
+    def set_noautoscale(self) -> Tuple[int, str, str]:
+        """
+        set the noautoscale for all pools (including
+        newly created pools in the future)
+        and complete all on-going progress events
+        regarding PG-autoscaling.
+        """
+        if self.has_noautoscale_flag():
+            return 0, "", "noautoscale is already set!"
+        else:
+            self.mon_command({
+                'prefix': 'config set',
+                'who': 'global',
+                'name': 'osd_pool_default_pg_autoscale_mode',
+                'value': 'off'
+            })
+            self.mon_command({
+                'prefix': 'osd set',
+                'key': 'noautoscale'
+            })
+            self.complete_all_progress_events()
+            return 0, "", "noautoscale is set, all pools now have autoscale off"
+
+    def serve(self) -> None:
+        self.config_notify()
+        while not self._shutdown.is_set():
+            if not self.has_noautoscale_flag():
+                osdmap = self.get_osdmap()
+                pools = osdmap.get_pools_by_name()
+                self._maybe_adjust(osdmap, pools)
+                self._update_progress_events(osdmap, pools)
+            self._shutdown.wait(timeout=self.sleep_interval)
+
+    def shutdown(self) -> None:
+        self.log.info('Stopping pg_autoscaler')
+        self._shutdown.set()
+
+    def identify_subtrees_and_overlaps(self,
+                                       osdmap: OSDMap,
+                                       pools: Dict[str, Dict[str, Any]],
+                                       crush: CRUSHMap,
+                                       result: Dict[int, CrushSubtreeResourceStatus],
+                                       overlapped_roots: Set[int],
+                                       roots: List[CrushSubtreeResourceStatus]) -> \
+        Tuple[List[CrushSubtreeResourceStatus],
+              Set[int]]:
+
+        # We identify subtrees and overlapping roots from osdmap
+        for pool_name, pool in pools.items():
+            crush_rule = crush.get_rule_by_id(pool['crush_rule'])
+            assert crush_rule is not None
+            cr_name = crush_rule['rule_name']
+            root_id = crush.get_rule_root(cr_name)
+            assert root_id is not None
+            osds = set(crush.get_osds_under(root_id))
+
+            # Are there overlapping roots?
+            s = None
+            for prev_root_id, prev in result.items():
+                if osds & prev.osds:
+                    s = prev
+                    if prev_root_id != root_id:
+                        overlapped_roots.add(prev_root_id)
+                        overlapped_roots.add(root_id)
+                        self.log.warning("pool %s won't scale due to overlapping roots: %s",
+                                      pool_name, overlapped_roots)
+                        self.log.warning("Please See: https://docs.ceph.com/en/"
+                                         "latest/rados/operations/placement-groups"
+                                         "/#automated-scaling")
+                    break
+            if not s:
+                s = CrushSubtreeResourceStatus()
+                roots.append(s)
+            result[root_id] = s
+            s.root_ids.append(root_id)
+            s.osds |= osds
+            s.pool_ids.append(pool['pool'])
+            s.pool_names.append(pool_name)
+            s.pg_current += pool['pg_num_target'] * pool['size']
+            target_ratio = pool['options'].get('target_size_ratio', 0.0)
+            if target_ratio:
+                s.total_target_ratio += target_ratio
+            else:
+                target_bytes = pool['options'].get('target_size_bytes', 0)
+                if target_bytes:
+                    s.total_target_bytes += target_bytes * osdmap.pool_raw_used_rate(pool['pool'])
+        return roots, overlapped_roots
+
+    def get_subtree_resource_status(self,
+                                    osdmap: OSDMap,
+                                    pools: Dict[str, Dict[str, Any]],
+                                    crush: CRUSHMap) -> Tuple[Dict[int, CrushSubtreeResourceStatus],
+                                                              Set[int]]:
+        """
+        For each CRUSH subtree of interest (i.e. the roots under which
+        we have pools), calculate the current resource usages and targets,
+        such as how many PGs there are, vs. how many PGs we would
+        like there to be.
+        """
+        result: Dict[int, CrushSubtreeResourceStatus] = {}
+        roots: List[CrushSubtreeResourceStatus] = []
+        overlapped_roots: Set[int] = set()
+        # identify subtrees and overlapping roots
+        roots, overlapped_roots = self.identify_subtrees_and_overlaps(
+            osdmap, pools, crush, result, overlapped_roots, roots
+        )
+        # finish subtrees
+        all_stats = self.get('osd_stats')
+        for s in roots:
+            assert s.osds is not None
+            s.osd_count = len(s.osds)
+            s.pg_target = s.osd_count * self.mon_target_pg_per_osd
+            s.pg_left = s.pg_target
+            s.pool_count = len(s.pool_ids)
+            capacity = 0
+            for osd_stats in all_stats['osd_stats']:
+                if osd_stats['osd'] in s.osds:
+                    # Intentionally do not apply the OSD's reweight to
+                    # this, because we want to calculate PG counts based
+                    # on the physical storage available, not how it is
+                    # reweighted right now.
+                    capacity += osd_stats['kb'] * 1024
+
+            s.capacity = capacity
+            self.log.debug('root_ids %s pools %s with %d osds, pg_target %d',
+                           s.root_ids,
+                           s.pool_ids,
+                           s.osd_count,
+                           s.pg_target)
+
+        return result, overlapped_roots
+
+    def _calc_final_pg_target(
+            self,
+            p: Dict[str, Any],
+            pool_name: str,
+            root_map: Dict[int, CrushSubtreeResourceStatus],
+            root_id: int,
+            capacity_ratio: float,
+            bias: float,
+            even_pools: Dict[str, Dict[str, Any]],
+            bulk_pools: Dict[str, Dict[str, Any]],
+            func_pass: 'PassT',
+            bulk: bool,
+    ) -> Union[Tuple[float, int, int], Tuple[None, None, None]]:
+        """
+        `profile` determines behaviour of the autoscaler.
+        `first_pass` flag used to determine if this is the first
+        pass where the caller tries to calculate/adjust pools that has
+        used_ratio > even_ratio else this is the second pass,
+        we calculate final_ratio by giving it 1 / pool_count
+        of the root we are currently looking at.
+        """
+        if func_pass == 'first':
+            # first pass to deal with small pools (no bulk flag)
+            # calculating final_pg_target based on capacity ratio
+            # we also keep track of bulk_pools to be used in second pass
+            if not bulk:
+                final_ratio = capacity_ratio
+                pg_left = root_map[root_id].pg_left
+                assert pg_left is not None
+                used_pg = final_ratio * pg_left
+                root_map[root_id].pg_left -= int(used_pg)
+                root_map[root_id].pool_used += 1
+                pool_pg_target = used_pg / p['size'] * bias
+            else:
+                bulk_pools[pool_name] = p
+                return None, None, None
+
+        elif func_pass == 'second':
+            # second pass we calculate the final_pg_target
+            # for pools that have used_ratio > even_ratio
+            # and we keep track of even pools to be used in third pass
+            pool_count = root_map[root_id].pool_count
+            assert pool_count is not None
+            even_ratio = 1 / (pool_count - root_map[root_id].pool_used)
+            used_ratio = capacity_ratio
+
+            if used_ratio > even_ratio:
+                root_map[root_id].pool_used += 1
+            else:
+                even_pools[pool_name] = p
+                return None, None, None
+
+            final_ratio = max(used_ratio, even_ratio)
+            pg_left = root_map[root_id].pg_left
+            assert pg_left is not None
+            used_pg = final_ratio * pg_left
+            root_map[root_id].pg_left -= int(used_pg)
+            pool_pg_target = used_pg / p['size'] * bias
+
+        else:
+            # third pass we just split the pg_left to all even_pools
+            pool_count = root_map[root_id].pool_count
+            assert pool_count is not None
+            final_ratio = 1 / (pool_count - root_map[root_id].pool_used)
+            pool_pg_target = (final_ratio * root_map[root_id].pg_left) / p['size'] * bias
+
+        min_pg = p.get('options', {}).get('pg_num_min', PG_NUM_MIN)
+        max_pg = p.get('options', {}).get('pg_num_max')
+        final_pg_target = max(min_pg, nearest_power_of_two(pool_pg_target))
+        if max_pg and max_pg < final_pg_target:
+            final_pg_target = max_pg
+        self.log.info("Pool '{0}' root_id {1} using {2} of space, bias {3}, "
+                      "pg target {4} quantized to {5} (current {6})".format(
+                      p['pool_name'],
+                      root_id,
+                      capacity_ratio,
+                      bias,
+                      pool_pg_target,
+                      final_pg_target,
+                      p['pg_num_target']
+        ))
+        return final_ratio, pool_pg_target, final_pg_target
+
+    def _get_pool_pg_targets(
+            self,
+            osdmap: OSDMap,
+            pools: Dict[str, Dict[str, Any]],
+            crush_map: CRUSHMap,
+            root_map: Dict[int, CrushSubtreeResourceStatus],
+            pool_stats: Dict[int, Dict[str, int]],
+            ret: List[Dict[str, Any]],
+            threshold: float,
+            func_pass: 'PassT',
+            overlapped_roots: Set[int],
+    ) -> Tuple[List[Dict[str, Any]], Dict[str, Dict[str, Any]] , Dict[str, Dict[str, Any]]]:
+        """
+        Calculates final_pg_target of each pools and determine if it needs
+        scaling, this depends on the profile of the autoscaler. For scale-down,
+        we start out with a full complement of pgs and only descrease it when other
+        pools needs more pgs due to increased usage. For scale-up, we start out with
+        the minimal amount of pgs and only scale when there is increase in usage.
+        """
+        even_pools: Dict[str, Dict[str, Any]] = {}
+        bulk_pools: Dict[str, Dict[str, Any]] = {}
+        for pool_name, p in pools.items():
+            pool_id = p['pool']
+            if pool_id not in pool_stats:
+                # race with pool deletion; skip
+                continue
+
+            # FIXME: we assume there is only one take per pool, but that
+            # may not be true.
+            crush_rule = crush_map.get_rule_by_id(p['crush_rule'])
+            assert crush_rule is not None
+            cr_name = crush_rule['rule_name']
+            root_id = crush_map.get_rule_root(cr_name)
+            assert root_id is not None
+            if root_id in overlapped_roots:
+                # skip pools
+                # with overlapping roots
+                self.log.warn("pool %d contains an overlapping root %d"
+                              "... skipping scaling", pool_id, root_id)
+                continue
+            capacity = root_map[root_id].capacity
+            assert capacity is not None
+            if capacity == 0:
+                self.log.debug("skipping empty subtree {0}".format(cr_name))
+                continue
+
+            raw_used_rate = osdmap.pool_raw_used_rate(pool_id)
+
+            bias = p['options'].get('pg_autoscale_bias', 1.0)
+            target_bytes = 0
+            # ratio takes precedence if both are set
+            if p['options'].get('target_size_ratio', 0.0) == 0.0:
+                target_bytes = p['options'].get('target_size_bytes', 0)
+
+            # What proportion of space are we using?
+            actual_raw_used = pool_stats[pool_id]['bytes_used']
+            actual_capacity_ratio = float(actual_raw_used) / capacity
+
+            pool_raw_used = max(actual_raw_used, target_bytes * raw_used_rate)
+            capacity_ratio = float(pool_raw_used) / capacity
+
+            self.log.info("effective_target_ratio {0} {1} {2} {3}".format(
+                p['options'].get('target_size_ratio', 0.0),
+                root_map[root_id].total_target_ratio,
+                root_map[root_id].total_target_bytes,
+                capacity))
+
+            target_ratio = effective_target_ratio(p['options'].get('target_size_ratio', 0.0),
+                                                  root_map[root_id].total_target_ratio,
+                                                  root_map[root_id].total_target_bytes,
+                                                  capacity)
+
+            # determine if the pool is a bulk
+            bulk = False
+            flags = p['flags_names'].split(",")
+            if "bulk" in flags:
+                bulk = True
+
+            capacity_ratio = max(capacity_ratio, target_ratio)
+            final_ratio, pool_pg_target, final_pg_target = self._calc_final_pg_target(
+                p, pool_name, root_map, root_id,
+                capacity_ratio, bias, even_pools,
+                bulk_pools, func_pass, bulk)
+
+            if final_ratio is None:
+                continue
+
+            adjust = False
+            if (final_pg_target > p['pg_num_target'] * threshold or
+                    final_pg_target < p['pg_num_target'] / threshold) and \
+                    final_ratio >= 0.0 and \
+                    final_ratio <= 1.0 and \
+                    p['pg_autoscale_mode'] == 'on':
+                adjust = True
+
+            assert pool_pg_target is not None
+            ret.append({
+                'pool_id': pool_id,
+                'pool_name': p['pool_name'],
+                'crush_root_id': root_id,
+                'pg_autoscale_mode': p['pg_autoscale_mode'],
+                'pg_num_target': p['pg_num_target'],
+                'logical_used': float(actual_raw_used)/raw_used_rate,
+                'target_bytes': target_bytes,
+                'raw_used_rate': raw_used_rate,
+                'subtree_capacity': capacity,
+                'actual_raw_used': actual_raw_used,
+                'raw_used': pool_raw_used,
+                'actual_capacity_ratio': actual_capacity_ratio,
+                'capacity_ratio': capacity_ratio,
+                'target_ratio': p['options'].get('target_size_ratio', 0.0),
+                'effective_target_ratio': target_ratio,
+                'pg_num_ideal': int(pool_pg_target),
+                'pg_num_final': final_pg_target,
+                'would_adjust': adjust,
+                'bias': p.get('options', {}).get('pg_autoscale_bias', 1.0),
+                'bulk': bulk,
+            })
+
+        return ret, bulk_pools, even_pools
+
+    def _get_pool_status(
+            self,
+            osdmap: OSDMap,
+            pools: Dict[str, Dict[str, Any]],
+    ) -> Tuple[List[Dict[str, Any]],
+               Dict[int, CrushSubtreeResourceStatus]]:
+        threshold = self.threshold
+        assert threshold >= 1.0
+
+        crush_map = osdmap.get_crush()
+        root_map, overlapped_roots = self.get_subtree_resource_status(osdmap, pools, crush_map)
+        df = self.get('df')
+        pool_stats = dict([(p['id'], p['stats']) for p in df['pools']])
+
+        ret: List[Dict[str, Any]] = []
+
+        # Iterate over all pools to determine how they should be sized.
+        # First call of _get_pool_pg_targets() is to find/adjust pools that uses more capacaity than
+        # the even_ratio of other pools and we adjust those first.
+        # Second call make use of the even_pools we keep track of in the first call.
+        # All we need to do is iterate over those and give them 1/pool_count of the
+        # total pgs.
+
+        ret, bulk_pools, _  = self._get_pool_pg_targets(osdmap, pools, crush_map, root_map,
+                                                  pool_stats, ret, threshold, 'first', overlapped_roots)
+
+        ret, _, even_pools = self._get_pool_pg_targets(osdmap, bulk_pools, crush_map, root_map,
+                                                  pool_stats, ret, threshold, 'second', overlapped_roots)
+
+        ret, _, _ = self._get_pool_pg_targets(osdmap, even_pools, crush_map, root_map,
+                                         pool_stats, ret, threshold, 'third', overlapped_roots)
+
+        return (ret, root_map)
+
+    def _get_pool_by_id(self,
+                     pools: Dict[str, Dict[str, Any]],
+                     pool_id: int) -> Optional[Dict[str, Any]]:
+        # Helper for getting pool data by pool_id
+        for pool_name, p in pools.items():
+            if p['pool'] == pool_id:
+                return p
+        self.log.debug('pool not found')
+        return None
+
+    def _update_progress_events(self,
+                                osdmap: OSDMap,
+                                pools: Dict[str, Dict[str, Any]]) -> None:
+        # Update progress events if necessary
+        if self.has_noautoscale_flag():
+            self.log.debug("noautoscale_flag is set.")
+            return
+        for pool_id in list(self._event):
+            ev = self._event[pool_id]
+            pool_data = self._get_pool_by_id(pools, pool_id)
+            if (
+                pool_data is None
+                or pool_data["pg_num"] == pool_data["pg_num_target"]
+                or ev.pg_num == ev.pg_num_target
+            ):
+                # pool is gone or we've reached our target
+                self.remote('progress', 'complete', ev.ev_id)
+                del self._event[pool_id]
+                continue
+            ev.update(self, (ev.pg_num - pool_data['pg_num']) / (ev.pg_num - ev.pg_num_target))
+
+    def _maybe_adjust(self,
+                      osdmap: OSDMap,
+                      pools: Dict[str, Dict[str, Any]]) -> None:
+        # Figure out which pool needs pg adjustments
+        self.log.info('_maybe_adjust')
+        if self.has_noautoscale_flag():
+            self.log.debug("noautoscale_flag is set.")
+            return
+        if osdmap.get_require_osd_release() < 'nautilus':
+            return
+
+        self.log.debug("pool: {0}".format(json.dumps(pools, indent=4,
+                                sort_keys=True)))
+
+        ps, root_map = self._get_pool_status(osdmap, pools)
+
+        # Anyone in 'warn', set the health message for them and then
+        # drop them from consideration.
+        too_few = []
+        too_many = []
+        bytes_and_ratio = []
+        health_checks: Dict[str, Dict[str, Union[int, str, List[str]]]] = {}
+
+        total_bytes = dict([(r, 0) for r in iter(root_map)])
+        total_target_bytes = dict([(r, 0.0) for r in iter(root_map)])
+        target_bytes_pools: Dict[int, List[int]] = dict([(r, []) for r in iter(root_map)])
+
+        for p in ps:
+            pool_id = p['pool_id']
+            pool_opts = pools[p['pool_name']]['options']
+            if pool_opts.get('target_size_ratio', 0) > 0 and pool_opts.get('target_size_bytes', 0) > 0:
+                bytes_and_ratio.append(
+                    'Pool %s has target_size_bytes and target_size_ratio set' % p['pool_name'])
+            total_bytes[p['crush_root_id']] += max(
+                p['actual_raw_used'],
+                p['target_bytes'] * p['raw_used_rate'])
+            if p['target_bytes'] > 0:
+                total_target_bytes[p['crush_root_id']] += p['target_bytes'] * p['raw_used_rate']
+                target_bytes_pools[p['crush_root_id']].append(p['pool_name'])
+            if p['pg_autoscale_mode'] == 'warn':
+                msg = 'Pool %s has %d placement groups, should have %d' % (
+                    p['pool_name'],
+                    p['pg_num_target'],
+                    p['pg_num_final'])
+                if p['pg_num_final'] > p['pg_num_target']:
+                    too_few.append(msg)
+                elif p['pg_num_final'] < p['pg_num_target']:
+                    too_many.append(msg)
+            if not p['would_adjust']:
+                continue
+            if p['pg_autoscale_mode'] == 'on':
+                # Note that setting pg_num actually sets pg_num_target (see
+                # OSDMonitor.cc)
+                r = self.mon_command({
+                    'prefix': 'osd pool set',
+                    'pool': p['pool_name'],
+                    'var': 'pg_num',
+                    'val': str(p['pg_num_final'])
+                })
+
+                # create new event or update existing one to reflect
+                # progress from current state to the new pg_num_target
+                pool_data = pools[p['pool_name']]
+                pg_num = pool_data['pg_num']
+                new_target = p['pg_num_final']
+                if pool_id in self._event:
+                    self._event[pool_id].reset(pg_num, new_target)
+                else:
+                    self._event[pool_id] = PgAdjustmentProgress(pool_id, pg_num, new_target)
+                self._event[pool_id].update(self, 0.0)
+
+                if r[0] != 0:
+                    # FIXME: this is a serious and unexpected thing,
+                    # we should expose it as a cluster log error once
+                    # the hook for doing that from ceph-mgr modules is
+                    # in.
+                    self.log.error("pg_num adjustment on {0} to {1} failed: {2}"
+                                   .format(p['pool_name'],
+                                           p['pg_num_final'], r))
+
+        if too_few:
+            summary = "{0} pools have too few placement groups".format(
+                len(too_few))
+            health_checks['POOL_TOO_FEW_PGS'] = {
+                'severity': 'warning',
+                'summary': summary,
+                'count': len(too_few),
+                'detail': too_few
+            }
+        if too_many:
+            summary = "{0} pools have too many placement groups".format(
+                len(too_many))
+            health_checks['POOL_TOO_MANY_PGS'] = {
+                'severity': 'warning',
+                'summary': summary,
+                'count': len(too_many),
+                'detail': too_many
+            }
+
+        too_much_target_bytes = []
+        for root_id, total in total_bytes.items():
+            total_target = int(total_target_bytes[root_id])
+            capacity = root_map[root_id].capacity
+            assert capacity is not None
+            if total_target > 0 and total > capacity and capacity:
+                too_much_target_bytes.append(
+                    'Pools %s overcommit available storage by %.03fx due to '
+                    'target_size_bytes %s on pools %s' % (
+                        root_map[root_id].pool_names,
+                        total / capacity,
+                        mgr_util.format_bytes(total_target, 5, colored=False),
+                        target_bytes_pools[root_id]
+                    )
+                )
+            elif total_target > capacity and capacity:
+                too_much_target_bytes.append(
+                    'Pools %s overcommit available storage by %.03fx due to '
+                    'collective target_size_bytes of %s' % (
+                        root_map[root_id].pool_names,
+                        total / capacity,
+                        mgr_util.format_bytes(total_target, 5, colored=False),
+                    )
+                )
+        if too_much_target_bytes:
+            health_checks['POOL_TARGET_SIZE_BYTES_OVERCOMMITTED'] = {
+                'severity': 'warning',
+                'summary': "%d subtrees have overcommitted pool target_size_bytes" % len(too_much_target_bytes),
+                'count': len(too_much_target_bytes),
+                'detail': too_much_target_bytes,
+            }
+
+        if bytes_and_ratio:
+            health_checks['POOL_HAS_TARGET_SIZE_BYTES_AND_RATIO'] = {
+                'severity': 'warning',
+                'summary': "%d pools have both target_size_bytes and target_size_ratio set" % len(bytes_and_ratio),
+                'count': len(bytes_and_ratio),
+                'detail': bytes_and_ratio,
+            }
+
+        self.set_health_checks(health_checks)
diff --git a/src/pybind/mgr/pg_autoscaler/tests/__init__.py b/src/pybind/mgr/pg_autoscaler/tests/__init__.py
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/src/pybind/mgr/pg_autoscaler/tests/__init__.py
diff --git a/src/pybind/mgr/pg_autoscaler/tests/test_cal_final_pg_target.py b/src/pybind/mgr/pg_autoscaler/tests/test_cal_final_pg_target.py
new file mode 100644
index 000000000..655025bbe
--- /dev/null
+++ b/src/pybind/mgr/pg_autoscaler/tests/test_cal_final_pg_target.py
@@ -0,0 +1,676 @@
+# python unit test
+import unittest
+from tests import mock
+import pytest
+import json
+from pg_autoscaler import module
+
+
+class RootMapItem:
+
+    def __init__(self, pool_count, pg_target, pg_left):
+
+        self.pool_count = pool_count
+        self.pg_target = pg_target
+        self.pg_left = pg_left
+        self.pool_used = 0
+
+
+class TestPgAutoscaler(object):
+
+    def setup_method(self):
+        # a bunch of attributes for testing.
+        self.autoscaler = module.PgAutoscaler('module_name', 0, 0)
+
+    def helper_test(self, pools, root_map, bias, overlapped_roots):
+        # Here we simulate how _get_pool_pg_target() works.
+
+        bulk_pools = {}
+        even_pools = {}
+
+        # first pass
+        for pool_name, p in pools.items():
+            root_id = p['root_id']
+            if root_id in overlapped_roots:
+                # skip pools with overlapping roots
+                assert p['no_scale']
+                continue
+
+            final_ratio, pool_pg_target, final_pg_target = self.autoscaler._calc_final_pg_target(
+                p, pool_name, root_map,
+                p['root_id'], p['capacity_ratio'],
+                bias, even_pools, bulk_pools, 'first', p['bulk'])
+
+            if final_ratio == None:
+                # no final_ratio means current pool is an even pool
+                # and we do not have to do any assertion on it.
+                continue
+
+            assert p['expected_final_pg_target'] == final_pg_target
+            assert p['expected_final_ratio'] == final_ratio
+            assert not p['expected_bulk_pool'] and pool_name not in bulk_pools
+
+        # second pass
+        for pool_name, p in bulk_pools.items():
+            final_ratio, pool_pg_target, final_pg_target = self.autoscaler._calc_final_pg_target(
+                p, pool_name, root_map,
+                p['root_id'], p['capacity_ratio'],
+                bias, even_pools, bulk_pools, 'second', p['bulk'])
+
+            if final_ratio == None:
+                # no final_ratio means current pool is an even pool
+                # and we do not have to do any assertion on it.
+                continue
+
+            assert p['expected_final_pg_target'] == final_pg_target
+            assert p['expected_final_ratio'] == final_ratio
+            assert not p['even_pools'] and pool_name not in even_pools
+
+        #third pass
+        for pool_name, p in even_pools.items():
+            final_ratio, pool_pg_target, final_pg_target = self.autoscaler._calc_final_pg_target(
+                p, pool_name, root_map,
+                p['root_id'], p['capacity_ratio'],
+                bias, even_pools, bulk_pools, 'third',  p['bulk'])
+
+            assert p['expected_final_pg_target'] == final_pg_target
+            assert p['expected_final_ratio'] == final_ratio
+            assert p['even_pools'] and pool_name in even_pools
+
+    def test_even_pools_one_meta_three_bulk(self):
+        pools = {
+
+            "meta_0": {
+
+                "pool": 0,
+                "pool_name": "meta_0",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.2,
+                "root_id": 0,
+                "expected_final_pg_target": 64,
+                "expected_final_ratio": 0.2,
+                "expected_bulk_pool": False,
+                "even_pools": False,
+                "size": 1,
+                "no_scale": False,
+                "bulk": False,
+            },
+
+            "bulk_0": {
+
+                "pool": 1,
+                "pool_name": "bulk_0",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.2,
+                "root_id": 0,
+                "expected_final_pg_target": 128,
+                "expected_final_ratio": 1/3,
+                "expected_bulk_pool": True,
+                "even_pools": True,
+                "size": 1,
+                "no_scale": False,
+                "bulk": True,
+            },
+
+            "bulk_1": {
+
+                "pool": 2,
+                "pool_name": "bulk_1",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.2,
+                "root_id": 0,
+                "expected_final_pg_target": 128,
+                "expected_final_ratio": 1/3,
+                "expected_bulk_pool": True,
+                "even_pools": True,
+                "size": 1,
+                "no_scale": False,
+                "bulk": True,
+            },
+
+            "bulk_2": {
+
+                "pool": 3,
+                "pool_name": "bulk_2",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.1,
+                "root_id": 0,
+                "expected_final_pg_target": 128,
+                "expected_final_ratio": 1/3,
+                "expected_bulk_pool": True,
+                "even_pools": True,
+                "size": 1,
+                "no_scale": False,
+                "bulk": True,
+            },
+
+        }
+
+        root_map = {
+
+            0: RootMapItem(4, 400, 400),
+            1: RootMapItem(4, 400, 400),
+
+        }
+
+        bias = 1
+        overlapped_roots = set()
+        self.helper_test(pools, root_map, bias, overlapped_roots)
+
+    def test_even_pools_two_meta_two_bulk(self):
+        pools = {
+
+            "meta0": {
+
+                "pool": 0,
+                "pool_name": "meta0",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.2,
+                "root_id": 0,
+                "expected_final_pg_target": 64,
+                "expected_final_ratio": 0.2,
+                "expected_bulk_pool": False,
+                "even_pools": True,
+                "size": 1,
+                "no_scale": False,
+                "bulk": False,
+            },
+
+            "meta1": {
+
+                "pool": 1,
+                "pool_name": "meta1",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.2,
+                "root_id": 0,
+                "expected_final_pg_target": 64,
+                "expected_final_ratio": 0.2,
+                "expected_bulk_pool": False,
+                "even_pools": True,
+                "size": 1,
+                "no_scale": False,
+                "bulk": False,
+            },
+
+            "bulk0": {
+
+                "pool": 2,
+                "pool_name": "bulk0",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.2,
+                "root_id": 0,
+                "expected_final_pg_target": 128,
+                "expected_final_ratio": 0.5,
+                "expected_bulk_pool": True,
+                "even_pools": True,
+                "size": 1,
+                "no_scale": False,
+                "bulk": True,
+            },
+
+            "bulk1": {
+
+                "pool": 3,
+                "pool_name": "test3",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.1,
+                "root_id": 0,
+                "expected_final_pg_target": 128,
+                "expected_final_ratio": 0.5,
+                "expected_bulk_pool": True,
+                "even_pools": True,
+                "size": 1,
+                "no_scale": False,
+                "bulk": True,
+            },
+
+        }
+
+        root_map = {
+
+            0: RootMapItem(4, 400, 400),
+            1: RootMapItem(4, 400, 400),
+
+        }
+
+        bias = 1
+        overlapped_roots = set()
+        self.helper_test(pools, root_map, bias, overlapped_roots)
+
+    def test_uneven_pools_one_meta_three_bulk(self):
+        pools = {
+
+            "meta0": {
+
+                "pool": 0,
+                "pool_name": "meta0",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.1,
+                "root_id": 0,
+                "expected_final_pg_target": 32,
+                "expected_final_ratio": 0.1,
+                "expected_bulk_pool": False,
+                "even_pools": True,
+                "size": 1,
+                "no_scale": False,
+                "bulk": False,
+            },
+
+            "bulk0": {
+
+                "pool": 1,
+                "pool_name": "bulk0",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.5,
+                "root_id": 0,
+                "expected_final_pg_target": 128,
+                "expected_final_ratio": 0.5,
+                "expected_bulk_pool": True,
+                "even_pools": False,
+                "size": 1,
+                "no_scale": False,
+                "bulk": True,
+            },
+
+            "bulk1": {
+
+                "pool": 2,
+                "pool_name": "bulk1",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.1,
+                "root_id": 0,
+                "expected_final_pg_target": 64,
+                "expected_final_ratio": 0.5,
+                "expected_bulk_pool": True,
+                "even_pools": True,
+                "size": 1,
+                "no_scale": False,
+                "bulk": True,
+            },
+
+            "bulk2": {
+
+                "pool": 3,
+                "pool_name": "bulk2",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.1,
+                "root_id": 0,
+                "expected_final_pg_target": 64,
+                "expected_final_ratio": 0.5,
+                "expected_bulk_pool": True,
+                "even_pools": True,
+                "size": 1,
+                "no_scale": False,
+                "bulk": True,
+            },
+
+        }
+
+        root_map = {
+
+            0: RootMapItem(4, 400, 400),
+            1: RootMapItem(4, 400, 400),
+
+        }
+
+        bias = 1
+        overlapped_roots = set()
+        self.helper_test(pools, root_map, bias, overlapped_roots)
+
+    def test_uneven_pools_two_meta_two_bulk(self):
+        pools = {
+
+            "meta0": {
+
+                "pool": 0,
+                "pool_name": "meta0",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.1,
+                "root_id": 0,
+                "expected_final_pg_target": 32,
+                "expected_final_ratio": 0.1,
+                "expected_bulk_pool": False,
+                "even_pools": True,
+                "size": 1,
+                "no_scale": False,
+                "bulk": False, 
+            },
+
+            "meta1": {
+
+                "pool": 1,
+                "pool_name": "meta1",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.1,
+                "root_id": 0,
+                "expected_final_pg_target": 32,
+                "expected_final_ratio": 0.1,
+                "expected_bulk_pool": False,
+                "even_pools": False,
+                "size": 1,
+                "no_scale": False,
+                "bulk": False,
+            },
+
+            "bulk0": {
+
+                "pool": 2,
+                "pool_name": "bulk0",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.5,
+                "root_id": 0,
+                "expected_final_pg_target": 128,
+                "expected_final_ratio": 0.5,
+                "expected_bulk_pool": True,
+                "even_pools": True,
+                "size": 1,
+                "no_scale": False,
+                "bulk": True,
+            },
+
+            "bulk1": {
+
+                "pool": 3,
+                "pool_name": "bulk1",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.1,
+                "root_id": 0,
+                "expected_final_pg_target": 128,
+                "expected_final_ratio": 0.5,
+                "expected_bulk_pool": True,
+                "even_pools": True,
+                "size": 1,
+                "no_scale": False,
+                "bulk": True,
+            },
+
+        }
+
+        root_map = {
+
+            0: RootMapItem(4, 400, 400),
+            1: RootMapItem(4, 400, 400),
+
+        }
+
+        bias = 1
+        overlapped_roots = set()
+        self.helper_test(pools, root_map, bias, overlapped_roots)
+
+    def test_uneven_pools_with_diff_roots(self):
+        pools = {
+
+            "meta0": {
+
+                "pool": 0,
+                "pool_name": "meta0",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.3,
+                "root_id": 0,
+                "expected_final_pg_target": 1024,
+                "expected_final_ratio": 0.3,
+                "expected_bulk_pool": False,
+                "even_pools": False,
+                "size": 1,
+                "no_scale": False,
+                "bulk": False,
+            },
+
+            "meta1": {
+
+                "pool": 1,
+                "pool_name": "meta1",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.6,
+                "root_id": 1,
+                "expected_final_pg_target": 2048,
+                "expected_final_ratio": 0.6,
+                "expected_bulk_pool": False,
+                "even_pools": False,
+                "size": 1,
+                "no_scale": False,
+                "bulk": False,
+            },
+
+            "bulk2": {
+
+                "pool": 2,
+                "pool_name": "bulk2",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.6,
+                "root_id": 0,
+                "expected_final_pg_target": 2048,
+                "expected_final_ratio": 0.6,
+                "expected_bulk_pool": True,
+                "even_pools": False,
+                "size": 1,
+                "no_scale": False,
+                "bulk": True,
+            },
+
+            "bulk3": {
+
+                "pool": 3,
+                "pool_name": "test3",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.1,
+                "root_id": 0,
+                "expected_final_pg_target": 1024,
+                "expected_final_ratio": 1,
+                "expected_bulk_pool": True,
+                "even_pools": True,
+                "size": 1,
+                "no_scale": False,
+                "bulk": True,
+            },
+
+            "bulk4": {
+
+                "pool": 4,
+                "pool_name": "bulk4",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.4,
+                "root_id": 1,
+                "expected_final_pg_target": 2048,
+                "expected_final_ratio": 1,
+                "expected_bulk_pool": True,
+                "even_pools": True,
+                "size": 1,
+                "no_scale": False,
+                "bulk": True,
+            },
+
+        }
+
+        root_map = {
+
+            0: RootMapItem(3, 5000, 5000),
+            1: RootMapItem(2, 5000, 5000),
+
+        }
+
+        bias = 1
+        overlapped_roots = set()
+        self.helper_test(pools, root_map, bias, overlapped_roots)
+
+    def test_even_pools_with_diff_roots(self):
+        pools = {
+
+            "meta0": {
+
+                "pool": 0,
+                "pool_name": "meta0",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.4,
+                "root_id": 0,
+                "expected_final_pg_target": 2048,
+                "expected_final_ratio": 0.4,
+                "expected_bulk_pool": False,
+                "even_pools": False,
+                "size": 1,
+                "no_scale": False,
+                "bulk": False,
+            },
+
+            "meta1": {
+
+                "pool": 1,
+                "pool_name": "meta1",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.6,
+                "root_id": 1,
+                "expected_final_pg_target": 2048,
+                "expected_final_ratio": 0.6,
+                "expected_bulk_pool": False,
+                "even_pools": False,
+                "size": 1,
+                "no_scale": False,
+                "bulk": False,
+            },
+
+            "bulk1": {
+
+                "pool": 2,
+                "pool_name": "bulk1",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.2,
+                "root_id": 0,
+                "expected_final_pg_target": 1024,
+                "expected_final_ratio": 0.5,
+                "expected_bulk_pool": True,
+                "even_pools": True,
+                "size": 1,
+                "no_scale": False,
+                "bulk": True,
+            },
+
+            "bulk2": {
+
+                "pool": 3,
+                "pool_name": "bulk2",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.1,
+                "root_id": 0,
+                "expected_final_pg_target": 1024,
+                "expected_final_ratio": 0.5,
+                "expected_bulk_pool": True,
+                "even_pools": True,
+                "size": 1,
+                "no_scale": False,
+                "bulk": True,
+            },
+
+            "bulk3": {
+
+                "pool": 4,
+                "pool_name": "bulk4",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.25,
+                "root_id": 1,
+                "expected_final_pg_target": 2048,
+                "expected_final_ratio": 1,
+                "expected_bulk_pool": True,
+                "even_pools": True,
+                "size": 1,
+                "no_scale": False,
+                "bulk": True,
+            },
+
+        }
+
+        root_map = {
+
+            0: RootMapItem(3, 5000, 5000),
+            1: RootMapItem(2, 5000, 5000),
+
+        }
+
+        bias = 1
+        overlapped_roots = set()
+        self.helper_test(pools, root_map, bias, overlapped_roots)
+
+    def test_uneven_pools_with_overlapped_roots(self):
+        pools = {
+
+            "test0": {
+
+                "pool": 0,
+                "pool_name": "test0",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.4,
+                "root_id": 0,
+                "expected_final_pg_target": 2048,
+                "expected_final_ratio": 0.4,
+                "even_pools": False,
+                "size": 1,
+                "no_scale": True,
+            },
+
+            "test1": {
+
+                "pool": 1,
+                "pool_name": "test1",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.6,
+                "root_id": 1,
+                "expected_final_pg_target": 2048,
+                "expected_final_ratio": 0.6,
+                "even_pools": False,
+                "size": 1,
+                "no_scale": True,
+            },
+
+            "test2": {
+
+                "pool": 2,
+                "pool_name": "test2",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.5,
+                "root_id": 0,
+                "expected_final_pg_target": 2048,
+                "expected_final_ratio": 0.5,
+                "even_pools": False,
+                "size": 1,
+                "no_scale": True,
+            },
+
+            "test3": {
+
+                "pool": 3,
+                "pool_name": "test3",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.1,
+                "root_id": 0,
+                "expected_final_pg_target": 512,
+                "expected_final_ratio": 1,
+                "even_pools": True,
+                "size": 1,
+                "no_scale": True,
+            },
+
+            "test4": {
+
+                "pool": 4,
+                "pool_name": "test4",
+                "pg_num_target": 32,
+                "capacity_ratio": 0.4,
+                "root_id": 1,
+                "expected_final_pg_target": 2048,
+                "expected_final_ratio": 1,
+                "even_pools": True,
+                "size": 1,
+                "no_scale": True,
+            },
+
+        }
+
+        root_map = {
+
+            0: RootMapItem(3, 5000, 5000),
+            1: RootMapItem(2, 5000, 5000),
+
+        }
+
+        bias = 1
+        overlapped_roots = {0, 1}
+        self.helper_test(pools, root_map, bias, overlapped_roots)
diff --git a/src/pybind/mgr/pg_autoscaler/tests/test_cal_ratio.py b/src/pybind/mgr/pg_autoscaler/tests/test_cal_ratio.py
new file mode 100644
index 000000000..d96671360
--- /dev/null
+++ b/src/pybind/mgr/pg_autoscaler/tests/test_cal_ratio.py
@@ -0,0 +1,37 @@
+from pg_autoscaler import effective_target_ratio
+from pytest import approx
+
+
+def check_simple_ratio(target_ratio, tot_ratio):
+    etr = effective_target_ratio(target_ratio, tot_ratio, 0, 0)
+    assert (target_ratio / tot_ratio) == approx(etr)
+    return etr
+
+
+def test_simple():
+    etr1 = check_simple_ratio(0.2, 0.9)
+    etr2 = check_simple_ratio(2, 9)
+    etr3 = check_simple_ratio(20, 90)
+    assert etr1 == approx(etr2)
+    assert etr1 == approx(etr3)
+
+    etr = check_simple_ratio(0.9, 0.9)
+    assert etr == approx(1.0)
+    etr1 = check_simple_ratio(1, 2)
+    etr2 = check_simple_ratio(0.5, 1.0)
+    assert etr1 == approx(etr2)
+
+
+def test_total_bytes():
+    etr = effective_target_ratio(1, 10, 5, 10)
+    assert etr == approx(0.05)
+    etr = effective_target_ratio(0.1, 1, 5, 10)
+    assert etr == approx(0.05)
+    etr = effective_target_ratio(1, 1, 5, 10)
+    assert etr == approx(0.5)
+    etr = effective_target_ratio(1, 1, 0, 10)
+    assert etr == approx(1.0)
+    etr = effective_target_ratio(0, 1, 5, 10)
+    assert etr == approx(0.0)
+    etr = effective_target_ratio(1, 1, 10, 10)
+    assert etr == approx(0.0)
diff --git a/src/pybind/mgr/pg_autoscaler/tests/test_overlapping_roots.py b/src/pybind/mgr/pg_autoscaler/tests/test_overlapping_roots.py
new file mode 100644
index 000000000..b82146f7f
--- /dev/null
+++ b/src/pybind/mgr/pg_autoscaler/tests/test_overlapping_roots.py
@@ -0,0 +1,514 @@
+# python unit test
+import unittest
+from tests import mock
+import pytest
+import json
+from pg_autoscaler import module
+
+
+class OSDMAP:
+    def __init__(self, pools):
+        self.pools = pools
+
+    def get_pools(self):
+        return self.pools
+
+    def pool_raw_used_rate(pool_id):
+        return 1
+
+
+class CRUSH:
+    def __init__(self, rules, osd_dic):
+        self.rules = rules
+        self.osd_dic = osd_dic
+
+    def get_rule_by_id(self, rule_id):
+        for rule in self.rules:
+            if rule['rule_id'] == rule_id:
+                return rule
+
+        return None
+
+    def get_rule_root(self, rule_name):
+        for rule in self.rules:
+            if rule['rule_name'] == rule_name:
+                return rule['root_id']
+
+        return None
+
+    def get_osds_under(self, root_id):
+        return self.osd_dic[root_id]
+
+
+class TestPgAutoscaler(object):
+
+    def setup_method(self):
+        # a bunch of attributes for testing.
+        self.autoscaler = module.PgAutoscaler('module_name', 0, 0)
+
+    def helper_test(self, osd_dic, rules, pools, expected_overlapped_roots):
+        result = {}
+        roots = []
+        overlapped_roots = set()
+        osdmap = OSDMAP(pools)
+        crush = CRUSH(rules, osd_dic)
+        roots, overlapped_roots = self.autoscaler.identify_subtrees_and_overlaps(
+            osdmap, pools, crush, result, overlapped_roots, roots
+        )
+        assert overlapped_roots == expected_overlapped_roots
+
+    def test_subtrees_and_overlaps(self):
+        osd_dic = {
+            -1: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
+            -40: [11, 12, 13, 14, 15],
+            -5: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],
+        }
+
+        rules = [
+            {
+                "rule_id": 0,
+                "rule_name": "data",
+                "ruleset": 0,
+                "type": 1,
+                "min_size": 1,
+                "max_size": 10,
+                "root_id": -1,
+            },
+            {
+                "rule_id": 1,
+                "rule_name": "teuthology-data-ec",
+                "ruleset": 1,
+                "type": 3,
+                "min_size": 3,
+                "max_size": 6,
+                "root_id": -5,
+            },
+            {
+                "rule_id": 4,
+                "rule_name": "rep-ssd",
+                "ruleset": 4,
+                "type": 1,
+                "min_size": 1,
+                "max_size": 10,
+                "root_id": -40,
+            },
+        ]
+        pools = {
+            "data": {
+                "pool": 0,
+                "pool_name": "data",
+                "pg_num_target": 1024,
+                "size": 3,
+                "crush_rule": 0,
+                "capacity_ratio": 0.1624,
+                "options": {
+                    "pg_num_min": 1024,
+                },
+                "expected_final_pg_target": 1024,
+            },
+            "metadata": {
+                "pool": 1,
+                "pool_name": "metadata",
+                "pg_num_target": 64,
+                "size": 3,
+                "crush_rule": 4,
+                "capacity_ratio": 0.0144,
+                "options": {
+                    "pg_num_min": 64,
+                },
+                "expected_final_pg_target": 64,
+            },
+            "libvirt-pool": {
+                "pool": 4,
+                "pool_name": "libvirt-pool",
+                "pg_num_target": 32,
+                "size": 3,
+                "crush_rule": 0,
+                "capacity_ratio": 0.0001,
+                "options": {},
+                "expected_final_pg_target": 128,
+            },
+            ".rgw.root": {
+                "pool": 93,
+                "pool_name": ".rgw.root",
+                "pg_num_target": 32,
+                "size": 3,
+                "crush_rule": 4,
+                "capacity_ratio": 0,
+                "options": {},
+                "expected_final_pg_target": 32,
+            },
+            "default.rgw.control": {
+                "pool": 94,
+                "pool_name": "default.rgw.control",
+                "pg_num_target": 32,
+                "size": 3,
+                "crush_rule": 4,
+                "capacity_ratio": 0,
+                "options": {},
+                "expected_final_pg_target": 32,
+            },
+            "default.rgw.meta": {
+                "pool": 95,
+                "pool_name": "default.rgw.meta",
+                "pg_num_target": 32,
+                "size": 3,
+                "crush_rule": 4,
+                "capacity_ratio": 0,
+                "options": {},
+                "expected_final_pg_target": 32,
+            },
+            "default.rgw.log": {
+                "pool": 96,
+                "pool_name": "default.rgw.log",
+                "pg_num_target": 32,
+                "size": 3,
+                "crush_rule": 4,
+                "capacity_ratio": 0,
+                "options": {},
+                "expected_final_pg_target": 32,
+            },
+            "default.rgw.buckets.index": {
+                "pool": 97,
+                "pool_name": "default.rgw.buckets.index",
+                "pg_num_target": 32,
+                "size": 3,
+                "crush_rule": 4,
+                "capacity_ratio": 0.0002,
+                "options": {},
+                "expected_final_pg_target": 32,
+            },
+            "default.rgw.buckets.data": {
+                "pool": 98,
+                "pool_name": "default.rgw.buckets.data",
+                "pg_num_target": 32,
+                "size": 3,
+                "crush_rule": 0,
+                "capacity_ratio": 0.0457,
+                "options": {},
+                "expected_final_pg_target": 128,
+            },
+            "default.rgw.buckets.non-ec": {
+                "pool": 99,
+                "pool_name": "default.rgw.buckets.non-ec",
+                "pg_num_target": 32,
+                "size": 3,
+                "crush_rule": 0,
+                "capacity_ratio": 0,
+                "options": {},
+                "expected_final_pg_target": 32,
+            },
+            "device_health_metrics": {
+                "pool": 100,
+                "pool_name": "device_health_metrics",
+                "pg_num_target": 1,
+                "size": 3,
+                "crush_rule": 0,
+                "capacity_ratio": 0,
+                "options": {
+                    "pg_num_min": 1
+                },
+                "expected_final_pg_target": 1,
+            },
+            "cephfs.teuthology.meta": {
+                "pool": 113,
+                "pool_name": "cephfs.teuthology.meta",
+                "pg_num_target": 64,
+                "size": 3,
+                "crush_rule": 4,
+                "capacity_ratio": 0.1389,
+                "options": {
+                    "pg_autoscale_bias": 4,
+                    "pg_num_min": 64,
+                },
+                "expected_final_pg_target": 512,
+            },
+            "cephfs.teuthology.data": {
+                "pool": 114,
+                "pool_name": "cephfs.teuthology.data",
+                "pg_num_target": 256,
+                "size": 3,
+                "crush_rule": 0,
+                "capacity_ratio": 0.0006,
+                "options": {
+                    "pg_num_min": 128,
+                },
+                "expected_final_pg_target": 1024,
+                "expected_final_pg_target": 256,
+            },
+            "cephfs.scratch.meta": {
+                "pool": 117,
+                "pool_name": "cephfs.scratch.meta",
+                "pg_num_target": 32,
+                "size": 3,
+                "crush_rule": 4,
+                "capacity_ratio": 0.0027,
+                "options": {
+                    "pg_autoscale_bias": 4,
+                    "pg_num_min": 16,
+                },
+                "expected_final_pg_target": 64,
+            },
+            "cephfs.scratch.data": {
+                "pool": 118,
+                "pool_name": "cephfs.scratch.data",
+                "pg_num_target": 32,
+                "size": 3,
+                "crush_rule": 0,
+                "capacity_ratio": 0.0027,
+                "options": {},
+                "expected_final_pg_target": 128,
+            },
+            "cephfs.teuthology.data-ec": {
+                "pool": 119,
+                "pool_name": "cephfs.teuthology.data-ec",
+                "pg_num_target": 1024,
+                "size": 6,
+                "crush_rule": 1,
+                "capacity_ratio": 0.8490,
+                "options": {
+                    "pg_num_min": 1024
+                },
+                "expected_final_pg_target": 1024,
+            },
+            "cephsqlite": {
+                "pool": 121,
+                "pool_name": "cephsqlite",
+                "pg_num_target": 32,
+                "size": 3,
+                "crush_rule": 4,
+                "capacity_ratio": 0,
+                "options": {},
+                "expected_final_pg_target": 128,
+            },
+        }
+        expected_overlapped_roots = {-40, -1, -5}
+        self.helper_test(osd_dic, rules, pools, expected_overlapped_roots)
+
+    def test_no_overlaps(self):
+        osd_dic = {
+            -1: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
+            -40: [11, 12, 13, 14, 15],
+            -5: [16, 17, 18],
+        }
+
+        rules = [
+            {
+                "rule_id": 0,
+                "rule_name": "data",
+                "ruleset": 0,
+                "type": 1,
+                "min_size": 1,
+                "max_size": 10,
+                "root_id": -1,
+            },
+            {
+                "rule_id": 1,
+                "rule_name": "teuthology-data-ec",
+                "ruleset": 1,
+                "type": 3,
+                "min_size": 3,
+                "max_size": 6,
+                "root_id": -5,
+            },
+            {
+                "rule_id": 4,
+                "rule_name": "rep-ssd",
+                "ruleset": 4,
+                "type": 1,
+                "min_size": 1,
+                "max_size": 10,
+                "root_id": -40,
+            },
+        ]
+        pools = {
+            "data": {
+                "pool": 0,
+                "pool_name": "data",
+                "pg_num_target": 1024,
+                "size": 3,
+                "crush_rule": 0,
+                "capacity_ratio": 0.1624,
+                "options": {
+                    "pg_num_min": 1024,
+                },
+                "expected_final_pg_target": 1024,
+            },
+            "metadata": {
+                "pool": 1,
+                "pool_name": "metadata",
+                "pg_num_target": 64,
+                "size": 3,
+                "crush_rule": 4,
+                "capacity_ratio": 0.0144,
+                "options": {
+                    "pg_num_min": 64,
+                },
+                "expected_final_pg_target": 64,
+            },
+            "libvirt-pool": {
+                "pool": 4,
+                "pool_name": "libvirt-pool",
+                "pg_num_target": 32,
+                "size": 3,
+                "crush_rule": 0,
+                "capacity_ratio": 0.0001,
+                "options": {},
+                "expected_final_pg_target": 128,
+            },
+            ".rgw.root": {
+                "pool": 93,
+                "pool_name": ".rgw.root",
+                "pg_num_target": 32,
+                "size": 3,
+                "crush_rule": 4,
+                "capacity_ratio": 0,
+                "options": {},
+                "expected_final_pg_target": 32,
+            },
+            "default.rgw.control": {
+                "pool": 94,
+                "pool_name": "default.rgw.control",
+                "pg_num_target": 32,
+                "size": 3,
+                "crush_rule": 4,
+                "capacity_ratio": 0,
+                "options": {},
+                "expected_final_pg_target": 32,
+            },
+            "default.rgw.meta": {
+                "pool": 95,
+                "pool_name": "default.rgw.meta",
+                "pg_num_target": 32,
+                "size": 3,
+                "crush_rule": 4,
+                "capacity_ratio": 0,
+                "options": {},
+                "expected_final_pg_target": 32,
+            },
+            "default.rgw.log": {
+                "pool": 96,
+                "pool_name": "default.rgw.log",
+                "pg_num_target": 32,
+                "size": 3,
+                "crush_rule": 4,
+                "capacity_ratio": 0,
+                "options": {},
+                "expected_final_pg_target": 32,
+            },
+            "default.rgw.buckets.index": {
+                "pool": 97,
+                "pool_name": "default.rgw.buckets.index",
+                "pg_num_target": 32,
+                "size": 3,
+                "crush_rule": 4,
+                "capacity_ratio": 0.0002,
+                "options": {},
+                "expected_final_pg_target": 32,
+            },
+            "default.rgw.buckets.data": {
+                "pool": 98,
+                "pool_name": "default.rgw.buckets.data",
+                "pg_num_target": 32,
+                "size": 3,
+                "crush_rule": 0,
+                "capacity_ratio": 0.0457,
+                "options": {},
+                "expected_final_pg_target": 128,
+            },
+            "default.rgw.buckets.non-ec": {
+                "pool": 99,
+                "pool_name": "default.rgw.buckets.non-ec",
+                "pg_num_target": 32,
+                "size": 3,
+                "crush_rule": 0,
+                "capacity_ratio": 0,
+                "options": {},
+                "expected_final_pg_target": 32,
+            },
+            "device_health_metrics": {
+                "pool": 100,
+                "pool_name": "device_health_metrics",
+                "pg_num_target": 1,
+                "size": 3,
+                "crush_rule": 0,
+                "capacity_ratio": 0,
+                "options": {
+                    "pg_num_min": 1
+                },
+                "expected_final_pg_target": 1,
+            },
+            "cephfs.teuthology.meta": {
+                "pool": 113,
+                "pool_name": "cephfs.teuthology.meta",
+                "pg_num_target": 64,
+                "size": 3,
+                "crush_rule": 4,
+                "capacity_ratio": 0.1389,
+                "options": {
+                    "pg_autoscale_bias": 4,
+                    "pg_num_min": 64,
+                },
+                "expected_final_pg_target": 512,
+            },
+            "cephfs.teuthology.data": {
+                "pool": 114,
+                "pool_name": "cephfs.teuthology.data",
+                "pg_num_target": 256,
+                "size": 3,
+                "crush_rule": 0,
+                "capacity_ratio": 0.0006,
+                "options": {
+                    "pg_num_min": 128,
+                },
+                "expected_final_pg_target": 1024,
+                "expected_final_pg_target": 256,
+            },
+            "cephfs.scratch.meta": {
+                "pool": 117,
+                "pool_name": "cephfs.scratch.meta",
+                "pg_num_target": 32,
+                "size": 3,
+                "crush_rule": 4,
+                "capacity_ratio": 0.0027,
+                "options": {
+                    "pg_autoscale_bias": 4,
+                    "pg_num_min": 16,
+                },
+                "expected_final_pg_target": 64,
+            },
+            "cephfs.scratch.data": {
+                "pool": 118,
+                "pool_name": "cephfs.scratch.data",
+                "pg_num_target": 32,
+                "size": 3,
+                "crush_rule": 0,
+                "capacity_ratio": 0.0027,
+                "options": {},
+                "expected_final_pg_target": 128,
+            },
+            "cephfs.teuthology.data-ec": {
+                "pool": 119,
+                "pool_name": "cephfs.teuthology.data-ec",
+                "pg_num_target": 1024,
+                "size": 6,
+                "crush_rule": 1,
+                "capacity_ratio": 0.8490,
+                "options": {
+                    "pg_num_min": 1024
+                },
+                "expected_final_pg_target": 1024,
+            },
+            "cephsqlite": {
+                "pool": 121,
+                "pool_name": "cephsqlite",
+                "pg_num_target": 32,
+                "size": 3,
+                "crush_rule": 4,
+                "capacity_ratio": 0,
+                "options": {},
+                "expected_final_pg_target": 128,
+            },
+        }
+        expected_overlapped_roots = set()
+        self.helper_test(osd_dic, rules, pools, expected_overlapped_roots)