Способ сборки мусора в твердотельном накопителе информации
GARBAGE COLLECTION METHOD IN A SOLID STATE DRIVE

Изобретение относится к контроллерам твердотельных накопителей информации и может быть использовано при разработке твердотельных накопителей информации, используемых вычислительных устройствах.
Твердотельные накопители (ТНИ или SSD solid state disk) являются устройствами хранения данных, которые хранят пользовательские данные в энергонезависимой памяти, состоящей из одной или нескольких ячеек твердотельной полупроводниковой памяти. В общем случае, ТНИ содержат модуль энергонезависимой памяти и контроллер или многофункциональный блок управления.
Контроллер может быть выполнен управляющим передачей пользовательских данных между энергонезависимой памятью и хост-устройством, где в качестве энергонезависимой памяти используется NAND флэш-память.
Флэш-память обычно организована в виде нескольких кристаллов полупроводниковой памяти, матрицы которой подключаются к цепи контроллера с помощью последовательности каналов (дорожек).
Матрицы подразделяются на более мелкие физические и логические блоки.
Особенностью NAND-флэш памяти является то, что минимальная порция информации, которая может быть удалена – это один блок. Блок состоит из множества страниц. Обычно один блок содержит несколько сотен страниц. Также необходимо отметить, что все ячейки блока деградируют при выполнении операции стирания. Процесс деградации приводит к повышению вероятности битовой ошибки при чтении информации с ТНИ. Поэтому необходимо минимизировать число операций стирания в процессе работы ТНИ.
В связи с тем, что ячейки памяти чувствительны к операциям записи и стирания, в предпочтительных вариантах реализации ТНИ, операции стирания логических секторов реализуются в виде операций инвалидации физических секторов, использование которых блокируется до того момента, когда физический блок, к которому относится не валидный сектор, не будет стерт полностью.
Операция подготовки не валидных физических секторов к повторному использованию называется «сборкой мусора» и ее реализация существенно загружает функциональные узлы контроллера, в связи с чем снижается общая производительность диска при выполнении операций записи-считывания.
Как показано, например, в заявке на выдачу патента США US2020379903A1, операции по сборке мусора выполняются как фоновые процедуры для периодической утилизации стираемых блоков для повторного использования.
Операция сборки мусора обычно включает в себя поиск в блоках, предназначенных для стирания, сведений о валидных секторах, перезапись валидных секторов в новое место и затем применение операции стирания для сброса ячеек памяти не валидных и перезаписанных блоков.
Блоки стирания обычно группируются в более крупные блоки сбора мусора (GCU), которые включают один или несколько блоков стирания из разных матриц и которые можно стирать и выделять как единое целое.
Известное техническое  решение, а также другие технические решения не предполагают проведение предварительный анализ ячеек или секторов блока, а перезапись валидных ячеек блока производится путем перебора ячеек и перезаписи выявленных валидных ячеек.
Задачей, решаемой настоящим изобретением и техническим результатом, достигаемым при реализации изобретения, является повышение скорости сборки мусора, сокращение загрузки контроллера, при выполнении соответствующих операций и, соответственно, повышение производительности ТНИ в целом. Указанный технический результат обусловлен обеспечением возможности аппаратной реализации самых трудоемких операций, используемых при сборке мусора и, следовательно, минимизацией участия в сборке мусора программируемой и/или перепрограммируемой подсистемы контроллера ТНИ, а также оптимизацией объема данных, декодируемых при сборке мусора и обеспечивается за счет того, что в способе аппаратной сборки мусора в твердотельном накопителе информации (ТНИ), содержащим несколько независимых матриц памяти, сектора памяти которых характеризуются физическими адресами, наборы которых одинаковы для всех матриц памяти:
для каждой из матриц памяти задают одинаковое количество блоков памяти, разделенных на заданное количество строк, состоящих из заданного количества страниц, с обеспечением возможности поблочного стирания информации, построчной записи информации и постраничного чтения информации, где каждая из страниц состоит из одинакового количества секторов, характеризуемых последовательными физическим адресами;
группируют матрицы в страйпы, каждый из которых включает в себя более одной матрицы;
блоки матриц каждого страйпа, содержащие сектора с идентичными физическими адресами группируют в суперблоки;
производят запись данных в сектора на твердотельный накопитель информации таким образом, что при первоначальной записи сектора, производят запись сектора в исходную строку и соответствующему сектору присваивают логический адрес, а при повторной записи сектора, производят запись сектора в другую строку с присвоением соответствующему сектору другой строки того же логического адреса и присвоение соответствующему сектору исходной строки статуса «не валидный»;
при этом, обеспечивают хранение таблиц соответствия физических и логических адресов секторов одного суперблока хранят на выделенной матрице, а значения секторов соответствующего суперблока хранят на рабочих матрицах суперблока,
при удалении сектора присваивают соответствующему сектору статуса «не валидный»;
задают минимальное количество не валидных секторов, относящихся к одному страйпу, где минимальное количество больше чем заранее заданное количество секторов в суперблоке;
и, при достижении количеством не валидных секторов, относящихся к соответствующему страйпу, заранее заданного минимального количества,
задают один из суперблоков, содержащий максимальное количество не валидных секторов;
для заданного суперблока активируют управляющий блок аппаратного сборщика мусора с указанием адреса суперблока, с использованием управляющего блока сборщика мусора загружают из выделенной матрицы заданного суперблока в выделенную динамическую память с произвольным доступом таблицу соответствия логических адресов физическим адресам секторов заданного суперблока и с использованием управляющего блока сборщика мусора для каждой из рабочих матриц заданного суперблока инициируют процесс сборки мусора, заключающийся в том, что:
с использованием выделенного для каждой из матриц обработчика матрицы производят независимую сборку мусора, для чего для каждого из обработчиков рабочих матриц  устанавливают флаг начала сборки мусора, с использованием обработчика матрицы, для которого установлен флаг начала сборки мусора,
по запросу обработчика матрицы, с использованием аппаратного блока определения валидных секторов:
загружают логические адреса секторов;
для загруженной таблицы соответствия, для каждой из рабочих матриц суперблока, для каждого из логических адресов последовательно проверяют наличие совпадения физического адреса сектора, соответствующего логическому адресу с физическим адресом сектора блока суперблока;
отмечают проверенные сектора, для которых имеется совпадение с формированием маски валидности секторов; после чего
используют маску валидности при сборке мусора соответствующим обработчиком матрицы так, что:
в соответствии с маской валидности секторов последовательно считывают страницы блока, содержащие валидные сектора, выполняют избирательное декодирование валидных секторов считанной страницы, формируют строки, содержащие декодированные валидные сектора с указанием логических адресов декодированных секторов, перезаписывают декодированные валидные сектора путем записи сформированных строк в свободные ячейки ТНИ,
после перезаписи всех секторов, указанных в маске валидных секторов, производят стирание блоков суперблока;
после стирания всех блоков суперблока формируют сигнал завершения сборки мусора в суперблоке, деактивирующий блок управления аппаратного сборщика мусора.  В частном случае реализации производят параллельную сборку мусора нескольких суперблоков, содержащих блоки различных матриц. При этом дополнительно могут определять частоту перезаписи секторов, и в каждой из матриц группируют в различных блоках сектора, имеющие частоту перезаписи, находящуюся в диапазоне, соответствующем соответствующему блоку, при этом, при сборке мусора производят перезапись секторов в блоки других матриц, соответствующие диапазону частоты перезаписи исходного блока.
На фиг. 1 изображена иллюстративная архитектура системы управления твердотельного накопителя информации, в котором может быть реализован предложенный способ.
Каждый путь или матрица памяти содержит некоторое количество доступных блоков памяти (например, их может быть 1024), которые делятся на некоторое число строк (wordline) (например, их может быть 256). Каждая строка состоит нескольких страниц (например, в строке может быть 1, 2, 3 или 4 страницы). Каждая страница имеет размер (16384 + 32)  байт и состоит из 4 секторов. Сектор - это единица информации хоста, равная 4096 байт. Страница - это единица информации микросхемы флэш-памяти и считывать информацию с микросхему флэш-памяти можно только страницами. Записывать информацию на микросхему флэш-памяти можно только сроками. Стирать информацию можно только блоками. Записать строку можно только в чистый блок, то есть, в блок, в котором предварительно было произведено стирание информации.
Если некоторый сектор записывается повторно, то он записывается в некоторый чистый блок, при этом часть страницы, где он был записан раньше, становится не валидной. Не валидные части страниц образуют неиспользуемую часть от общего объема ТНИ. Чтобы сократить эту неиспользуемую часть ТНИ, включается процесс, называемый «сборкой мусора».
Страйп (stripe) – это некоторое подмножество путей или матриц. Объединение всех страйпов равно множеству путей контроллера. Разные страйпы не пересекаются. Запись или супер строка (superwordline) – это множество строк, принадлежащим путям страйпа и имеющих одинаковые адреса в пределах пути. Иными словами, количество путей в страйпе в точности равно количеству строк в записи, которая связана со страйпом, и каждая строка записи будет записана на соответствующий ей путь страйпа. Суперблок – это множество блоков, принадлежащим путям страйпа и имеющих одинаковые адреса в пределах пути. Один из путей страйпа назначается проверочным (parity), аналогично, одна из строк записи (и один из блоков суперблока) является проверочной – parity. Остальные строки для целей раскрытия изобретения обозначаются полезными или рабочими. Проверочная строка используется для проверки правильность дешифрованных значений блоков и секторов, при этом записанный ранее  сектор может считаться не валидным не только в том случае, если для него не задан логический адрес, но и в том случае, если контрольная сумма дешифрованного сектора не соответствует проверочной контрольной сумме.
Запись в массив флэш-памяти ведется строками. Открытой записью называется запись, в которую в настоящий момент осуществляется накопление строк. Неполной строкой называется строка, в которую можно добавить еще хотя бы один сектор.
В каждом блоке последняя запись содержит логические адреса всех секторов, которые записаны в этот блок.
Сборщик мусора (GC - Garbage Collector) – это подсистема, предназначенная для формирования и очистки суперблоков из уже побывавших в использовании, но ставших неактуальными фрагментов данных, то есть Сборщик мусора занимается подготовкой свободного места для записи данных на накопитель.
В качестве изобретения предлагается способ ускорения алгоритмов сборки мусора с помощью аппаратных модулей, входящих в состав контроллера ТНИ. Для целей описания изобретения, на фиг. 1 тонкими стрелками обозначаются управляющие команды, а широкими стрелками – процессы передачи данных, например, значений секторов.
Как показано на фиг. 1, сборка мусора начинается с того, что CPU  или процессорная подсистема ТНИ) 1 принимает решение, что для некоторого страйпа надо очистить суперблок. После этого CPU выбирает суперблок страйпа с минимальной валидностью. Следующим шагом CPU загружает все последние строки суперблока, где содержится список логических адресов секторов блока, в DRAM 9 (стрелка команд 1 и стрелка данных 2). Далее CPU сообщает Блоку определения невалидных  секторов 3 номер страйпа и номер суперблока, который надо очистить (стрелка команд 3). Ту же информацию CPU сообщает Управляющему блоку сборщика мусора 4 (стрелка команд 4). Отправив на очистку один суперблок, CPU может подготовить и отправить на сборку мусора суперблок с другого страйпа. Иными словами, в процессе очистки мусора могут одновременно находиться несколько суперблоков, единственное ограничение, чтобы они принадлежали разным страйпам.
Блок определения невалидных секторов запоминает номер суперблока, инициализирует состояния счетчиков, соответствующих путям страйпа. Управляющий блок аппаратного сборщика мусора или управляющий блок сборщика мусора передает адрес очищаемого блока каждому из обработчиков полезных путей (обработчиков матриц) очищаемого страйпа и запускает на этих путях процесс сборки мусора (стрелка команд 5).
Блок обработчиков путей содержит независимые обработчики путей по одному на каждый путь. Все эти обработчики осуществляют сборку мусора независимо друг от друга. Каждый обработчик пути, получив команду начать сборку мусора, просит у Блока определения невалидных секторов дать ему маску валидности для первых 32 секторов очищаемого блока (стрелка команд 6). После получения маски валидных секторов, обработчик пути считывает валидные сектора с блока NANDs и отправляет их на декодирующий блок. Затем, после декодирования, эти сектора передаются в Блок записи для перезаписи в блок NANDs.
Аппаратный блок блок определения валидных  секторов 3, используя QATC 8, запрашивает из DRAM 9 первые, например, 32 логических адреса секторов из требуемого блока (стрелки команд 7 и 8 и стрелки данных 10 и 11).
Блок QATC (Queues And Tables Control – блок управления очередями и таблицами)  отвечает за управление таблицами и связь со средствами трансляции адресов памяти и используется для:
1) Получения многосекторных запросов от блока  бесперебойной памяти.
2) Разбиения многосекторного запроса на односекторные, получение температуры для запроса от софтвера и передача запроса в ядро контроллера.
3) Передачу необходимой информации модулю, отправляющему задания DMA при запросах записи и обеспечение возможности поиска информации при запросах чтения.
4) Формирование таблицы путем записи в DRAM информации, которая получена от ядра контроллера в ответ на запросы хоста.
5) Формирование и запись специальных секторов.
6) Связь с центральных блоком управления памятью, обработка и выполнение его команд, передача центральному блоку сообщений об ошибках, произошедших в ядре контроллера.
7) Передача блоку валидности сообщений от средств трансляции адресов памяти и обеспечение их связи с DRAM.
8) Отправка completion (сообщений о завершении выполнения запроса) на запросы обратно в блок бесперебойной памяти.
Информация о валидности сектора в явном виде не хранится. В таблицах средств трансляции адресов памяти, которыми управляет QATC,  хранится информация о соответствии логических и физических адресов валидных секторов. Во время работы ТНИ эти таблицы размещаются в DRAM памяти. При подаче команды на выключение эти таблицы сохраняются во флэш-памяти в специальном разделе.
Получив указанные 32 логических адреса сектора, блок определения невалидных  секторов обрабатывает по очереди каждый из этих адресов и через стрелки 7 и 8 запрашивает из таблицы соответствия логических и физических адресов физический адрес сектора, соответствующий данному логическому сектору. По порядковому номеру рассматриваемого сектора блок определения невалидных секторов вычисляет физический адрес сектора в очищаемом блоке и сравнивает вычисленный физический адрес с физическим адресом, полученным из таблицы соответствия. Если эти адреса совпадают, то сектор считается валидным, в противном случае – невалидным. Опросив все 32 адреса, блок определения невалидных  секторов формирует маску валидности из 32 бит и возвращает ее по стрелке 6 тому обработчику пути, который эту маску просил.
Обработчик пути, получив маску валидности, обращается по стрелке 11 к NANDs и просит считать страницы, которые содержат валидные сектора. Одновременно обработчик пути запрашивает маску валидности следующих 32 секторов очищаемого блока, но при этом продолжает обрабатывать текущую маску валидности. Получив по стрелке 11 сигнал, что запрашиваемая страница считана в буфер, обработчик пути передает Декодирующему блоку 5 по стрелке 12 команду на декодирование только валидных секторов данной страницы. Декодирующий блок по стрелке 13 забирает данные этих секторов, декодирует их и передает по стрелке 14 декодированные сектора блоку записи 6.
Блок записи 6 формирует из этих и других секторов новые строки и записывает эти строки по стрелке 15 на NANDs. Одновременно Блок записи по стрелке 16 сообщает новые физические адреса записанных секторов QATC. А QATC записывает эти адреса в таблицу соответствия логических и физических адресов секторов.
Когда обработчик пути завершит считывание всех валидных секторов очищаемого блока, он сообщает об этом по стрелке 5 управляющему блоку сборщика мусора. Когда управляющий блок сборщика мусора получит такие сигналы от всех полезных путей очищаемого суперблока, он понимает что суперблок очищен и посылает всем обработчикам путей этого суперблока ( в том числе пути, содержащему проверочный блок суперблока) команду на стирание блоков суперблока. Обработчики путей передают эти команды NANDs по стрелке 11, и по завершении стирания сообщают об этом Управляющему блоку 4. Управляющий блок, получив сообщения о стирании со всех путей суперблока, понимает, что сборка мусора на данном суперблоке завершена и сообщает об этом по стрелке 4.
По завершении операции сборки мусора Управляющий блок по стрелке 4 передает в CPU (центральному процессору) соответствующий сигнал с помощью аппаратного прерывания.
На этом сборка мусора на суперблоке завершается.