1#!/usr/bin/python3
2# Copyright 2017 Facebook.
3# Licensed under the same terms as memcached itself.
4
5import argparse
6import socket
7import sys
8import re
9import traceback
10from time import sleep
11
12parser = argparse.ArgumentParser(description="daemon for rebalancing slabs")
13parser.add_argument("--host", help="host to connect to",
14        default="localhost:11211", metavar="HOST:PORT")
15parser.add_argument("-s", "--sleep", help="seconds between runs",
16                    type=int, default="1")
17parser.add_argument("-v", "--verbose", action="store_true")
18parser.add_argument("-a", "--automove", action="store_true", default=False,
19                    help="enable automatic page rebalancing")
20parser.add_argument("-w", "--window", type=int, default="30",
21                    help="rolling window size for decision history")
22parser.add_argument("-r", "--ratio", type=float, default=0.8,
23                    help="ratio limiting distance between low/high class ages")
24
25# TODO:
26# - age adjuster function
27#   - by ratio of get_hits
28#   - by ratio of chunk size
29
30args = parser.parse_args()
31
32host, port = args.host.split(':')
33
34def window_check_count(history, sid, key):
35    total = 0
36    for window in history['w']:
37        s = window.get(sid)
38        if s and s.get(key):
39            total += s.get(key) > 0 and 1 or 0
40    return total
41
42def window_check_sum(history, sid, key):
43    total = 0
44    for window in history['w']:
45        s = window.get(sid)
46        if s and s.get(key):
47            total += s.get(key)
48    return total
49
50def determine_move(history, diffs, totals):
51    """ Figure out of a page move is in order.
52
53    - if > 2.5 pages of free space without free chunks reducing for N trials,
54      and no evictions for N trials, free to global.
55    - use ratio of how far apart age can be between slab classes
56    - TODO: if get_hits exists, allowable distance in age from the *youngest* slab
57      class is based on the percentage of get_hits the class gets, against the
58      factored max distance, ie:
59      1% max delta. youngest is 900, oldest allowable is 900+90
60      if class has 30% of get_hits, it can be 930
61    - youngest evicting slab class gets page moved to it, if outside ratio max
62    - use age as average over window. smooths over items falling out of WARM.
63      also gives a little weight: if still evicting, a few more pages than
64      necessary may be moved, pulling the classes closer together. Hopefully
65      avoiding ping-ponging.
66    """
67    # rotate windows
68    history['w'].append({})
69    if (len(history['w']) > args.window):
70        history['w'].pop(0)
71    w = history['w'][-1]
72    oldest = (-1, 0)
73    youngest = (-1, sys.maxsize)
74    decision = (-1, -1)
75    for sid, slab in diffs.items():
76
77        w[sid] = {}
78        if 'evicted_d' not in slab or 'total_pages_d' not in slab:
79            continue
80        # mark this window as dirty if total pages increases or evictions
81        # happened
82        if slab['total_pages_d'] > 0:
83            w[sid]['dirty'] = 1
84        if slab['evicted_d'] > 0:
85            w[sid]['dirty'] = 1
86            w[sid]['ev'] = slab['evicted_d'] / totals['evicted_d']
87        w[sid]['age'] = slab['age']
88        age = window_check_sum(history, sid, 'age') / len(history['w'])
89
90        # if > 2.5 pages free, and not dirty, reassign to global page pool and
91        # break.
92        if slab['free_chunks'] > slab['chunks_per_page'] * 2.5:
93            if window_check_sum(history, sid, 'dirty') == 0:
94                decision = (sid, 0)
95                break
96
97        # are we the oldest slab class? (and a valid target)
98        if age > oldest[1] and slab['total_pages'] > 2:
99            oldest = (sid, age)
100
101        # are we the youngest evicting slab class?
102        ev_total = window_check_count(history, sid, 'ev')
103        ev_total_sum = window_check_sum(history, sid, 'ev') / args.window
104        window_min = args.window / 2
105        if args.verbose:
106            print("sid {} age {} ev_total {} window_min {} ev_total_sum {}".format(sid, age, ev_total, window_min, ev_total_sum))
107        # If youngest and evicted in more than 50% of the window interval, or more than 25% of the total evictions in the window
108        if age < youngest[1] and ( ev_total > window_min or ev_total_sum > 0.25 ):
109            youngest = (sid, age)
110            #if args.verbose:
111            #    print("window: {} range: {}".format(ev_total, window_min))
112
113    # is the youngest slab class too young?
114    if youngest[0] != -1 and oldest[0] != -1:
115        if args.verbose:
116            print("old:   [class: {}] [age: {:.2f}]\nyoung: [class: {}] [age: {:.2f}]".format(
117                int(oldest[0]), oldest[1], int(youngest[0]), youngest[1]))
118        if youngest[1] < oldest[1] * args.ratio and w[youngest[0]].get('ev'):
119            decision = (oldest[0], youngest[0])
120
121    if (len(history['w']) >= args.window):
122        return decision
123    return (-1, -1)
124
125
126def run_move(s, decision):
127    s.write("slabs reassign " + str(decision[0]) + " " + str(decision[1]) + "\r\n")
128    line = s.readline().rstrip()
129    if args.verbose:
130        print("move result:", line)
131
132
133def diff_stats(before, after):
134    """ fills out "diffs" as deltas between before/after,
135    and "totals" as the sum of all slab classes.
136    "_d" postfix to keys means the delta between before/after.
137    non-postfix keys are total as of 'after's reading.
138    """
139    diffs = {}
140    totals = {}
141    for slabid in after.keys():
142        sb = before.get(slabid)
143        sa = after.get(slabid)
144        if not (sb and sa):
145            continue
146        slab = sa.copy()
147        for k in sa.keys():
148            if k not in sb:
149                continue
150            if k not in totals:
151                totals[k] = 0
152                totals[k + '_d'] = 0
153            if k + '_d' not in slab:
154                slab[k + '_d'] = 0
155            if re.search(r"^\d+$", sa[k]):
156                totals[k] += int(sa[k])
157                slab[k] = int(sa[k])
158                slab[k + '_d'] = int(sa[k]) - int(sb[k])
159                totals[k + '_d'] += int(sa[k]) - int(sb[k])
160        slab['slab'] = slabid
161        diffs[slabid] = slab
162    return (diffs, totals)
163
164
165def read_stats(s):
166    slabs = {}
167    for statcmd in ['items', 'slabs']:
168        #print("stat cmd: " + statcmd)
169        # FIXME: Formatting
170        s.write("stats " + statcmd + "\r\n")
171        while True:
172            line = s.readline().rstrip()
173            if line.startswith("END"):
174                break
175
176            m = re.match(r"^STAT (?:items:)?(\d+):(\S+) (\S+)", line)
177            if m:
178                (slab, var, val) = m.groups()
179                if slab not in slabs:
180                    slabs[slab] = {}
181                slabs[slab][var] = val
182            #print("line: " + line)
183    return slabs
184
185
186def pct(num, divisor):
187    if not divisor:
188        return 0
189    return (num / divisor)
190
191
192def show_detail(diffs, totals):
193    """ just a pretty printer for some extra data """
194    print("\n  {:2s}: {:8s} (pct  ) {:10s} (pct    ) {:6s} (pct)   {:6s}".format('sb',
195                'evicted', 'items', 'pages', 'age'))
196
197    for sid, slab in diffs.items():
198        if 'evicted_d' not in slab:
199            continue
200        print("  {:2d}: {:8d} ({:.2f}%) {:10d} ({:.4f}%) {:6d} ({:.2f}%) {:6d}".format(
201              int(sid), slab['evicted_d'], pct(slab['evicted_d'], totals['evicted_d']),
202              slab['number'], pct(slab['number'], totals['number']),
203              slab['total_pages'], pct(slab['total_pages'],
204              totals['total_pages']),
205              slab['age']))
206
207
208stats_pre = {}
209history = { 'w': [{}] }
210while True:
211    try:
212        with socket.create_connection((host, port), 5) as c:
213            s = c.makefile(mode="rw", buffering=1)
214            s.write("slabs automove 0\r\n")
215            print(s.readline().rstrip())
216            while True:
217                stats_post = read_stats(s)
218                (diffs, totals) = diff_stats(stats_pre, stats_post)
219                if args.verbose:
220                    show_detail(diffs, totals)
221                decision = determine_move(history, diffs, totals)
222                if decision[0] != -1 and decision[1] != -1:
223                    print("moving page from, to:", decision)
224                    if args.automove:
225                        run_move(s, decision)
226
227                # Minimize sleeping if we just moved a page to global pool.
228                # Improves responsiveness during flushes/quick changes.
229                if decision[1] == 0:
230                    sleep(0.05)
231                else:
232                    sleep(args.sleep)
233                stats_pre = stats_post
234    except:
235        err = sys.exc_info()
236        print("disconnected:", err[0], err[1])
237        traceback.print_exc()
238        stats_pre = {}
239        history = { 'w': [{}] }
240        sleep(args.sleep)
241
242