Simulator
This section introduces ssd.py
, a simple SSD simulator you can use to understand better how SSDs work. See the previous lesson for details on how to run the simulator.
#! /usr/bin/env python from __future__ import print_function from collections import * from optparse import OptionParser import random import string class ssd: def __init__(self, ssd_type, num_logical_pages, num_blocks, pages_per_block, block_erase_time, page_program_time, page_read_time, high_water_mark, low_water_mark, trace_gc, show_state): # type self.TYPE_DIRECT = 1 self.TYPE_LOGGING = 2 self.TYPE_IDEAL = 3 if ssd_type == 'direct': self.ssd_type = self.TYPE_DIRECT elif ssd_type == 'log': self.ssd_type = self.TYPE_LOGGING elif ssd_type == 'ideal': self.ssd_type = self.TYPE_IDEAL else: print('bad SSD type (%s)' % ssd_type) exit(1) # size self.num_logical_pages = num_logical_pages self.num_blocks = num_blocks self.pages_per_block = pages_per_block # parameters self.block_erase_time = block_erase_time self.page_program_time = page_program_time self.page_read_time = page_read_time # init each page of each block to INVALID self.STATE_INVALID = 1 self.STATE_ERASED = 2 self.STATE_VALID = 3 self.num_pages = self.num_blocks * self.pages_per_block self.state = {} for i in range(self.num_pages): self.state[i] = self.STATE_INVALID # data itself self.data = {} for i in range(self.num_pages): self.data[i] = ' ' # LOGGING stuff # reverse map: for each physical page, what LOGICAL page refers to it? # which page to write to right now? self.current_page = -1 self.current_block = 0 # gc counts self.gc_count = 0 self.gc_current_block = 0 self.gc_high_water_mark = high_water_mark self.gc_low_water_mark = low_water_mark self.gc_trace = trace_gc self.show_state = show_state # can use this as a log block self.gc_used_blocks = {} for i in range(self.num_blocks): self.gc_used_blocks[i] = 0 # counts so as to help the GC self.live_count = {} for i in range(self.num_blocks): self.live_count[i] = 0 # FTL self.forward_map = {} for i in range(self.num_logical_pages): self.forward_map[i] = -1 self.reverse_map = {} for i in range(self.num_pages): self.reverse_map[i] = -1 # stats self.physical_erase_count = {} self.physical_read_count = {} self.physical_write_count = {} for i in range(self.num_blocks): self.physical_erase_count[i] = 0 self.physical_read_count[i] = 0 self.physical_write_count[i] = 0 self.physical_erase_sum = 0 self.physical_write_sum = 0 self.physical_read_sum = 0 self.logical_trim_sum = 0 self.logical_write_sum = 0 self.logical_read_sum = 0 self.logical_trim_fail_sum = 0 self.logical_write_fail_sum = 0 self.logical_read_fail_sum = 0 return def blocks_in_use(self): used = 0 for i in range(self.num_blocks): used += self.gc_used_blocks[i] return used def physical_erase(self, block_address): page_begin = block_address * self.pages_per_block page_end = page_begin + self.pages_per_block - 1 for page in range(page_begin, page_end + 1): self.data[page] = ' ' self.state[page] = self.STATE_ERASED # now, definitely NOT in use self.gc_used_blocks[block_address] = 0 # STATS self.physical_erase_count[block_address] += 1 self.physical_erase_sum += 1 return def physical_program(self, page_address, data): self.data[page_address] = data self.state[page_address] = self.STATE_VALID # STATS self.physical_write_count[page_address / self.pages_per_block] += 1 self.physical_write_sum += 1 return def physical_read(self, page_address): # STATS self.physical_read_count[page_address / self.pages_per_block] += 1 self.physical_read_sum += 1 return self.data[page_address] def read_direct(self, address): return self.physical_read(address) def write_direct(self, page_address, data): block_address = page_address / self.pages_per_block page_begin = block_address * self.pages_per_block page_end = page_begin + self.pages_per_block - 1 old_list = [] for old_page in range(page_begin, page_end + 1): if self.state[old_page] == self.STATE_VALID: old_data = self.physical_read(old_page) old_list.append((old_page, old_data)) self.physical_erase(block_address) for (old_page, old_data) in old_list: if old_page == page_address: continue self.physical_program(old_page, old_data) self.physical_program(page_address, data) self.forward_map[page_address] = page_address self.reverse_map[page_address] = page_address return 'success' def write_ideal(self, page_address, data): self.physical_program(page_address, data) self.forward_map[page_address] = page_address self.reverse_map[page_address] = page_address return 'success' def is_block_free(self, block): first_page = block * self.pages_per_block if self.state[first_page] == self.STATE_INVALID or self.state[first_page] == self.STATE_ERASED: if self.state[first_page] == self.STATE_INVALID: self.physical_erase(block) self.current_block = block self.current_page = first_page self.gc_used_blocks[block] = 1 return True return False def get_cursor(self): if self.current_page == -1: for block in range(self.current_block, self.num_blocks) + range(0, self.current_block): if self.is_block_free(block): return 0 return -1 return 0 def update_cursor(self): self.current_page += 1 if self.current_page % self.pages_per_block == 0: self.current_page = -1 return def write_logging(self, page_address, data, is_gc_write=False): if self.get_cursor() == -1: self.logical_write_fail_sum += 1 return 'failure: device full' # NORMAL MODE writing assert(self.state[self.current_page] == self.STATE_ERASED) self.physical_program(self.current_page, data) self.forward_map[page_address] = self.current_page self.reverse_map[self.current_page] = page_address self.update_cursor() return 'success' def garbage_collect(self): blocks_cleaned = 0 for block in range(self.gc_current_block, self.num_blocks) + range(0, self.gc_current_block): # don't GC the block currently being written to if block == self.current_block: continue # page to start looking for live blocks page_start = block * self.pages_per_block # is this page (and hence block) already erased? then don't bother if self.state[page_start] == self.STATE_ERASED: continue # collect list of live physical pages in this block live_pages = [] for page in range(page_start, page_start + self.pages_per_block): logical_page = self.reverse_map[page] if logical_page != -1 and self.forward_map[logical_page] == page: live_pages.append(page) # if ONLY live blocks, don't clean it! (why bother with move?) if len(live_pages) == self.pages_per_block: continue # live pages should be copied to current writing location for page in live_pages: # live: so copy it someplace new if self.gc_trace: print('gc %d:: read(physical_page=%d)' % (self.gc_count, page)) print('gc %d:: write()' % self.gc_count) data = self.physical_read(page) self.write(self.reverse_map[page], data) # finally, erase the block and see if we're done blocks_cleaned += 1 self.physical_erase(block) if self.gc_trace: print('gc %d:: erase(block=%d)' % (self.gc_count, block)) if self.show_state: print('') self.dump() print('') if self.blocks_in_use() <= self.gc_low_water_mark: # done! record where we stopped and return self.gc_current_block = block self.gc_count += 1 return # END: block iteration return def upkeep(self): # GARBAGE COLLECTION if self.blocks_in_use() >= self.gc_high_water_mark: self.garbage_collect() # WEAR LEVELING: for future return def trim(self, address): self.logical_trim_sum += 1 if address < 0 or address >= self.num_logical_pages: self.logical_trim_fail_sum += 1 return 'fail: illegal trim address' if self.forward_map[address] == -1: self.logical_trim_fail_sum += 1 return 'fail: uninitialized trim' self.forward_map[address] = -1 return 'success' def read(self, address): self.logical_read_sum += 1 if address < 0 or address >= self.num_logical_pages: self.logical_read_fail_sum += 1 return 'fail: illegal read address' if self.forward_map[address] == -1: self.logical_read_fail_sum += 1 return 'fail: uninitialized read' # USED for DIRECT and LOGGING and IDEAL return self.read_direct(self.forward_map[address]) def write(self, address, data): self.logical_write_sum += 1 if address < 0 or address >= self.num_logical_pages: self.logical_write_fail_sum += 1 return 'fail: illegal write address' if self.ssd_type == self.TYPE_DIRECT: return self.write_direct(address, data) elif self.ssd_type == self.TYPE_IDEAL: return self.write_ideal(address, data) else: return self.write_logging(address, data) def printable_state(self, s): if s == self.STATE_INVALID: return 'i' elif s == self.STATE_ERASED: return 'E' elif s == self.STATE_VALID: return 'v' else: print('bad state %d' % s) exit(1) def stats(self): print('Physical Operations Per Block') print('Erases ', end='') for i in range(self.num_blocks): print('%3d ' % self.physical_erase_count[i], end='') print(' Sum: %d' % self.physical_erase_sum) print('Writes ', end='') for i in range(self.num_blocks): print('%3d ' % self.physical_write_count[i], end='') print(' Sum: %d' % self.physical_write_sum) print('Reads ', end='') for i in range(self.num_blocks): print('%3d ' % self.physical_read_count[i], end='') print(' Sum: %d' % self.physical_read_sum) print('') print('Logical Operation Sums') print(' Write count %d (%d failed)' % (self.logical_write_sum, self.logical_write_fail_sum)) print(' Read count %d (%d failed)' % (self.logical_read_sum, self.logical_read_fail_sum)) print(' Trim count %d (%d failed)' % (self.logical_trim_sum, self.logical_trim_fail_sum)) print('') print('Times') print(' Erase time %.2f' % (self.physical_erase_sum * self.block_erase_time)) print(' Write time %.2f' % (self.physical_write_sum * self.page_program_time)) print(' Read time %.2f' % (self.physical_read_sum * self.page_read_time)) total_time = self.physical_erase_sum * self.block_erase_time + self.physical_write_sum * self.page_program_time + self.physical_read_sum * self.page_read_time print(' Total time %.2f' % total_time) return def dump(self): # FTL print('FTL ', end='') count = 0 ftl_columns = (self.pages_per_block * self.num_blocks) / 7 for i in range(self.num_logical_pages): if self.forward_map[i] == -1: continue count += 1 print('%3d:%3d ' % (i, self.forward_map[i]), end='') if count > 0 and count % ftl_columns == 0: print('\n ', end='') if count == 0: print('(empty)', end='') print('') # FLASH? print('Block ', end='') for i in range(self.num_blocks): out_str = '%d' % i print(out_str + ' ' * (self.pages_per_block - len(out_str) + 1), end='') print('') max_len = len(str(self.num_pages)) for n in range(max_len, 0, -1): if n == max_len: print('Page ', end='') else: print(' ', end='') for i in range(self.num_pages): out_str = str(i).zfill(max_len)[max_len - n] print(out_str, end='') if i > 0 and (i+1) % 10 == 0: print(end=' ') print('') print('State ', end='') for i in range(self.num_pages): print('%s' % self.printable_state(self.state[i]), end='') if i > 0 and (i+1) % 10 == 0: print(end=' ') print('') # DATA print('Data ', end='') for i in range(self.num_pages): if self.state[i] == self.STATE_VALID: print('%s' % self.data[i], end='') else: print(' ', end='') if i > 0 and (i+1) % 10 == 0: print(end=' ') print('') # LIVE print('Live ', end='') for i in range(self.num_pages): if self.state[i] == self.STATE_VALID and self.forward_map[self.reverse_map[i]] == i: print('+', end='') else: print(' ', end='') if i > 0 and (i+1) % 10 == 0: print(end=' ') print('') return # # MAIN PROGRAM # parser = OptionParser() parser.add_option('-s', '--seed', default=0, help='the random seed', action='store', type='int', dest='seed') parser.add_option('-n', '--num_cmds', default=10, help='number of commands to randomly generate', action='store', type='int', dest='num_cmds') parser.add_option('-P', '--op_percentages', default='40/50/10', help='if rand, percent of reads/writes/trims', action='store', type='string', dest='op_percentages') parser.add_option('-K', '--skew', default='', help='if non-empty, skew, e.g., 80/20: 80% of ops to 20% of blocks', action='store', type='string', dest='skew') parser.add_option('-k', '--skew_start', default=0, help='if --skew, skew after this many writes', action='store', type='int', dest='skew_start') parser.add_option('-r', '--read_fails', default=0, help='if rand, percent of reads that can fail', action='store', type='int', dest='read_fail') parser.add_option('-L', '--cmd_list', default='', help='comma-separated list of commands (e.g., r10,w20:a)', action='store', type='string', dest='cmd_list') parser.add_option('-T', '--ssd_type', default='direct', help='SSD type: ideal, direct, log', action='store', type='string', dest='ssd_type') parser.add_option('-l', '--logical_pages', default=80, help='number of logical pages in interface', action='store', type='int', dest='num_logical_pages') parser.add_option('-B', '--num_blocks', default=12, help='number of physical blocks in SSD', action='store', type='int', dest='num_blocks') parser.add_option('-p', '--pages_per_block', default=10, help='pages per physical block', action='store', type='int', dest='pages_per_block') parser.add_option('-G', '--high_water_mark', default=10, help='blocks used before gc trigger', action='store', type='int', dest='high_water_mark') parser.add_option('-g', '--low_water_mark', default=8, help='gc target before stopping gc', action='store', type='int', dest='low_water_mark') parser.add_option('-R', '--read_time', default=10, help='page read time (usecs)', action='store', type='int', dest='read_time') parser.add_option('-W', '--program_time', default=40, help='page program time (usecs)', action='store', type='int', dest='program_time') parser.add_option('-E', '--erase_time', default=1000, help='page erase time (usecs)', action='store', type='int', dest='erase_time') parser.add_option('-J', '--show_gc', default=False, help='show garbage collector behavior', action='store_true', dest='show_gc') parser.add_option('-F', '--show_state', default=False, help='show flash state', action='store_true', dest='show_state') parser.add_option('-C', '--show_cmds', default=False, help='show commands', action='store_true', dest='show_cmds') parser.add_option('-q', '--quiz_cmds', default=False, help='quiz commands', action='store_true', dest='quiz_cmds') parser.add_option('-S', '--show_stats', default=False, help='show statistics', action='store_true', dest='show_stats') parser.add_option('-c', '--compute', default=False, help='compute answers for me', action='store_true', dest='solve') (options, args) = parser.parse_args() random.seed(options.seed) print('ARG seed %s' % options.seed) print('ARG num_cmds %s' % options.num_cmds) print('ARG op_percentages %s' % options.op_percentages) print('ARG skew %s' % options.skew) print('ARG skew_start %s' % options.skew_start) print('ARG read_fail %s' % options.read_fail) print('ARG cmd_list %s' % options.cmd_list) print('ARG ssd_type %s' % options.ssd_type) print('ARG num_logical_pages %s' % options.num_logical_pages) print('ARG num_blocks %s' % options.num_blocks) print('ARG pages_per_block %s' % options.pages_per_block) print('ARG high_water_mark %s' % options.high_water_mark) print('ARG low_water_mark %s' % options.low_water_mark) print('ARG erase_time %s' % options.erase_time) print('ARG program_time %s' % options.program_time) print('ARG read_time %s' % options.read_time) print('ARG show_gc %s' % options.show_gc) print('ARG show_state %s' % options.show_state) print('ARG show_cmds %s' % options.show_cmds) print('ARG quiz_cmds %s' % options.quiz_cmds) print('ARG show_stats %s' % options.show_stats) print('ARG compute %s' % options.solve) print('') s = ssd(ssd_type=options.ssd_type, num_logical_pages=options.num_logical_pages, num_blocks=options.num_blocks, pages_per_block=options.pages_per_block, block_erase_time=float(options.erase_time), page_program_time=float(options.program_time), page_read_time=float(options.read_time), high_water_mark=options.high_water_mark, low_water_mark=options.low_water_mark, trace_gc=options.show_gc, show_state=options.show_state) # # generate cmds (if not passed in by cmd_list) # hot_cold = False skew_start = options.skew_start if options.skew != '': hot_cold = True skew = options.skew.split('/') if len(skew) != 2: print('bad skew specification; should be 80/20 or something like that') exit(1) hot_percent = int(skew[0])/100.0 hot_target = int(skew[1])/100.0 if options.cmd_list == '': max_page_addr = int(options.num_logical_pages) num_cmds = int(options.num_cmds) p = options.op_percentages.split('/') assert(len(p) == 3) percent_reads, percent_writes, percent_trims = int(p[0]), int(p[1]), int(p[2]) if percent_writes <= 0: print('must have some writes, otherwise nothing in the SSD!') exit(1) printable = string.digits + string.letters cmd_list = [] valid_addresses = [] while len(cmd_list) < num_cmds: which_cmd = int(random.random() * 100.0) if which_cmd < percent_reads: # READ if random.randint(0, 99) < int(options.read_fail): address = random.randint(0, max_page_addr - 1) else: if len(valid_addresses) < 2: continue address = random.choice(valid_addresses) cmd_list.append('r%d' % address) elif which_cmd < percent_reads + percent_writes: # WRITE if skew_start == 0 and hot_cold and random.random() < hot_percent: address = random.randint(0, int(hot_target * (max_page_addr - 1))) else: address = random.randint(0, max_page_addr - 1) if address not in valid_addresses: valid_addresses.append(address) data = random.choice(list(printable)) cmd_list.append('w%d:%s' % (address, data)) if skew_start > 0: skew_start -= 1 else: # TRIM if len(valid_addresses) < 1: continue address = random.choice(valid_addresses) cmd_list.append('t%d' % address) valid_addresses.remove(address) else: cmd_list = options.cmd_list.split(',') s.dump() print('') show_state = options.show_state show_cmds = options.show_cmds quiz_cmds = options.quiz_cmds if quiz_cmds: show_state = True op = 0 for cmd in cmd_list: if cmd == '': break if cmd[0] == 'r': # r10 address = int(cmd.split('r')[1]) data = s.read(address) if show_cmds or (quiz_cmds and options.solve): print('cmd %3d:: read(%d) -> %s' % (op, address, data)) elif quiz_cmds: print('cmd %3d:: read(%d) -> ??' % (op, address)) op += 1 elif cmd[0] == 'w': # w80:b parts = cmd.split(':') address = int(parts[0].split('w')[1]) data = parts[1] rc = s.write(address, data) if show_cmds or (quiz_cmds and options.solve): print('cmd %3d:: write(%d, %s) -> %s' % (op, address, data, rc)) elif quiz_cmds: print('cmd %3d:: command(??) -> ??' % op) op += 1 elif cmd[0] == 't': address = int(cmd.split('t')[1]) rc = s.trim(address) if show_cmds or (quiz_cmds and options.solve): print('cmd %3d:: trim(%d) -> %s' % (op, address, rc)) elif quiz_cmds: print('cmd %d:: command(??) -> ??' % op) op += 1 if show_state: print('') s.dump() print('') # Do GC? s.upkeep() if not show_state: print('') s.dump() print('') if options.show_stats: s.stats() print('')
Questions
-
The exercise will mostly focus on the log-structured SSD, which is simulated with the “-T log” flag. We’ll use the other types of SSDs for comparison. First, run with flags
-T log -s 1 -n 10 -q
. Can you figure out which operations took place? Use-c
to check your answers (or just use-C
instead of-q -c
). Use different values of-s
to generate different random workloads. -
Now just show the commands and see if you can figure out the intermediate states of the Flash. Run with flags
-T log -s 2 -n 10 -C
to show each command. Now, determine the state of the Flash between each command; use-F
to show the states and see if you were right. Use different random seeds to test your burgeoning expertise. -
Let’s make this problem ever so slightly more interesting by adding the
-r 20
flag. What differences does this cause in the commands? Use-c
again to check your answers. -
Performance is determined by the number of erases, programs, and reads (we assume here that trims are free). Run the same workload again as above, but without showing any intermediate states (e.g.,
-T log -s 1 -n 10
). Can you estimate how long this workload will take to complete? (default erase time is 1000 microseconds, program time is 40, and read time is 10) Use the-S
flag to check your answer. You can also change the erase, program, and read times with the-E
,-W
,-R
flags. -
Now, compare the performance of the log-structured approach and the (very bad) direct approach (
-T direct
instead of-T log
). First, estimate how you think the direct approach will perform, then check your answer with the-S
flag. In general, how much better will the log-structured approach perform than the direct one? -
Let us next explore the behavior of the garbage collector. To do so, we have to set the high (
-G
) and low (-g
) watermarks appropriately. First, let’s observe what happens when you run a larger workload to the log-structured SSD but without any garbage collection. To do this, run with flags-T log -n 1000
(the high watermark default is 10, so the GC won’t run in this configuration). What do you think will happen? Use-C
and perhaps-F
to see. -
To turn on the garbage collector, use lower values. The high watermark (
-G N
) tells the system to start collecting onceN
blocks have been used; the low watermark (-G M
) tells the system to stop collecting once there are onlyM
blocks in use. What watermark values do you think will make for a working system? Use-C
and-F
to show the commands and intermediate device states and see. -
One other useful flag is
-J
, which shows what the collector is doing when it runs. Run with flags-T log -n 1000 -C -J
to see both the commands and the GC behavior. What do you notice about the GC? The final effect of GC, of course, is performance. Use-S
to look at final statistics; how many extra reads and writes occur due to garbage collection? Compare this to the ideal SSD (-T ideal
); how much extra reading, writing, and erasing is there due to the nature of Flash? Compare it also to thedirect
approach; in what way (erases, reads, programs) is the log-structured approach superior? -
One last aspect to explore is workload skew. Adding skew to the workload changes writes such that more writes occur to some smaller fraction of the logical block space. For example, running with
-K 80/20
makes 80% of the writes go to 20% of the blocks. Pick some different skews and perform many randomly-chosen operations (e.g.,-n 1000
), using first-T direct
to understand the skew, and then-T log
to see the impact on a log-structured device. What do you expect will happen? One other small skew control to explore is-k 100
; by adding this flag to a skewed workload, the first 100 writes are not skewed. The idea is to first create a lot of data, but then only update some of it. What impact might that have upon a garbage collector?
Get hands-on with 1400+ tech skills courses.