СПОСОБ ЗАПИСИ ДАННЫХ НА НАКОПИТЕЛЬ ЦИФРОВОЙ ИНФОРМАЦИИ НА БАЗЕ FLASH-ПАМЯТИ ТИПА NAND
METHOD OF RECORDING DATA TO DIGITAL INFORMATION DRIVE ON BASIS OF NAND TYPE FLASH-MEMORY

Область техники, к которой относится изобретение
Изобретение относится к вычислительной технике и представляет собой способ записи данных на накопитель цифровой информации на базе flash-памяти типа NAND, отличающийся от известных аналогов выбором сценария работы пользователя с накопителем, определяющего наиболее часто перезаписываемые страницы, журналированием наиболее часто перезаписываемых страниц, выполнением слияния журнального блока и соответствующего блока данных при запросе на чтение, а также «отложенной записью» блоков для операций перезаписи страниц, не относящихся к журналируемым. Технический результат заключается в продлении срока эксплуатации flash-памяти и увеличении скорости записи информации на носитель за счет сокращения количества операций блочного стирания, а также увеличении скорости считывания информации.
Уровень техники
Твердотельные накопители информации на базе flash-памяти широко используются в различных электронных устройствах. Компактность, дешевизна, механическая прочность, низкое энергопотребление позволяют flash-накопителям оставаться одним из самых распространенных способов хранения и транспортировки цифровой информации.
Технология flash-памяти типа NAND имеет ряд особенностей:
1) ячейки памяти обеспечивают ограниченное количество циклов записи-стирания, после чего они приходят в негодность;
2) доступ для записи или чтения возможен к произвольному числу ячеек, но стирание информации производится только для группы ячеек. Логические единицы чтения данных – страницы, которые объединены в блоки – единицы стирания. Запись данных, таким образом, осуществляется постранично, а стирание поблочно;
3) при перезаписи информации в уже используемую область памяти для обеспечения ее корректности, данный участок необходимо предварительно стереть, то есть в случае перезаписи нескольких страниц производится очищение целого блока. На операции перезаписи данных расходуется большое количество ресурсов (копирование неперезаписываемых страниц блока, стирание блока, запись новых и скопированных данных).
Эти особенности технологии flash-памяти накладывают ограничения на срок эксплуатации накопителей, а также на скорость записи информации.
С целью решения этих проблем применяется концепция логических и физических адресов: для адресации информации со стороны операционной системы используются логические адреса, расположенные по порядку, а для доступа к физическому хранилищу данных – физические адреса. Соответствия логических и физических адресов устанавливаются в таблице, содержащей логические адреса и указатели на соответствующие им физические адреса.
Для уменьшения количества операций блочного стирания, а следовательно, продления срока службы flash-накопителей, было предложено решение, заключающееся в следующем: при записи новой информации в занятый блок (перезапись), осуществляется запись в какой-либо неиспользуемый блок, а занятый блок очищается; затем вносятся изменения в таблицу соответствия логических и физических адресов (логический адрес первоначально адресованного блока назначается реально записанному блоку). При описанной выше перестановке блоков многократный доступ, направленный в один и тот же логический блок, в действительности производят в разные физические блоки, что делает возможным продление срока службы флэш-памяти, определяемого количеством выполненных в ней операций записи [патент RU2243588, МПК G06F 12/06, G06F 12/10, опубликован 27.12.2004].
Блок, из которого данные были удалены, теперь считается неиспользуемым блоком, то есть при следующей операции записи может быть задействован. Очевидным улучшением является идея учета количества осуществленных циклов записи-стирания для каждого физического блока – различные методы «выравнивания износа» (wear-leveling). В [заявка US20070050536, МПК G06F 12/00, опубликована 01.03.2007] очередной блок для записи выбирается из списка, упорядоченного по времени последнего стирания и/или по количеству выполненных ранее циклов записи блока. В [патент US6850443, МПК G11C 11/00, опубликован 01.02.2005] при обнаружении неравномерности износа, т.е. в случае, когда какие-либо физические блоки имеют большее количество циклов перезаписи, чем другие, эти блоки обмениваются информацией с наименее перезаписываемыми блоками, а в таблицу соответствия логических и физических адресов вносятся изменения, отражающие осуществленный обмен.
Существенно уменьшается производительность и увеличивается износ флеш-памяти в случае многократной перезаписи малого объема данных (меньше размера блока). В этом случае необходимо сначала произвести копирование неперезаписываемых страниц блока, затем стирание блока и, наконец, запись как новых, так и скопированных данных. Было предложено проводить журналирование страниц [патент US6938116, МПК G06F 12/16, G06F 12/00, G06F 12/02, G06F 13/42, G11C 16/02, опубликован 30.08.2005]. Вся доступная память разбивается на 3 группы: блоки данных (занятые), свободные блоки и журнальные блоки (зарезервированные). При осуществлении операции перезаписи страницы данные записываются не в запрошенный блок данных, а в назначенный ему журнальный блок. При повторном запросе перезаписи данной страницы, она снова записывается в журнальный блок (на свободное место). Когда журнальный блок будет заполнен полностью, производится слияние: последняя актуальная версия журналируемой страницы и остальные непереписываемые страницы запрошенного блока копируются в третий свободный блок, которому назначается логический адрес запрошенного. Запрошенный блок очищается. Чтение данных из блока, содержащего журналируемую страницу (страницы), осуществляется следующим образом: нежурналируемые страницы считываются по своему непосредственному адресу, а чтение данных журналируемых страниц осуществляется из журнальной области. При данном подходе улучшается также и скорость работы накопителя за счет сокращения количества операций стирания. Данное решение является наиболее близким аналогом (прототипом) предлагаемого способа записи данных на накопитель цифровой информации на базе flash-памяти типа NAND.
Раскрытие изобретения
Сущность изобретения как технического решения заключается в способе записи данных на носитель информации на базе flash-памяти типа NAND, включающем в себя
получение запроса на запись данных в незаполненные страницы определенного блока и непосредственную запись данных в эти страницы,
получение запроса на перезапись данных в заполненные страницы определенного блока и журналирование данных в журнальном блоке, соответствующем запрошенному блоку,
слияние блока данных и соответствующего ему журнального блока,
отличающемся тем, что
в начале сеанса работы пользователя с накопителем происходит автоматический выбор сценария работы пользователя из набора предложенных, сформированных на этапе разработки в ходе предварительного моделирования работы пользователя с накопителем на основе собранной статистической информации о частоте перезаписи страниц,
журналирование выполняется только для наиболее часто перезаписываемых страниц, определяемых выбранным в начале сеанса работы пользователя с накопителем сценарием,
слияние блока данных и соответствующего ему журнального блока выполняется при получении запроса на чтение журналируемой страницы из данного блока,
для операций перезаписи страниц, не относящихся к журналируемым, выполняется «отложенная запись» блоков, которая состоит в записи информации в буферный блок вместо адресуемого блока до момента смены номера текущего адресуемого блока либо первого запроса на чтение данных.
Изобретение направлено на решение задачи увеличения срока эксплуатации и быстродействия накопителей информации на базе flash-памяти типа NAND. Технический результат заключается в продлении срока эксплуатации flash-памяти и увеличении скорости записи информации на носитель за счет сокращения количества операций блочного стирания, а также увеличении скорости считывания информации.
В начале сеанса работы накопителя информации осуществляется автоматический выбор сценария пользовательского поведения. Исходя из выбранного сценария фиксируется некоторое число (n) наиболее часто перезаписываемых страниц (областей) и осуществляется их журналирование. Слияние последних актуальных данных из журнальных блоков с соответствующими им блоками, в отличие от прототипа, производится не при полном заполнении журнальных блоков, а при поступлении первого запроса на чтение данных. Для перезаписи остальных страниц (не относящихся к журналируемым) предложена «отложенная запись» блоков. При получении запроса на перезапись запись новых данных осуществляется в свободный буферный  блок. Если следующий запрос на перезапись относится к тому же блоку, но другим страницам, запись снова осуществляется в буферный блок. При переходе к другому блоку (или при получении запроса на чтение) в незаполненные страницы буферного блока копируются страницы исходного блока, затем исходный блок стирается, а в таблице соответствия логических и физических адресов логический адрес первоначально адресованного блока назначается реально записанному (буферному) блоку.
Журналирование часто используемых страниц (небольших областей) позволяет сократить количество операций их перезаписи (циклов записи-стирания) в число раз, равное количеству страниц (областей данного размера) в блоке (от 64 до 512 в зависимости от объема накопителя), что продлевает срок службы накопителя, а также существенно улучшает скорость записи информации.
Слияние последних актуальных данных из журнального блока с соответствующим блоком данных не при полном заполнении журнального блока, а, в отличие от аналога, при поступлении запроса на чтение данных журналируемой страницы позволяет повысить скорость как записи (за счет избавления от лишних операций процедуры слияния в случае непрерывной серии запросов на перезапись), так и чтения, поскольку доступ к нефрагментированным, последовательно расположенным данным в пределах одного блока выполняется быстрее.
В современных операционных системах запись данных большого объема осуществляется небольшими пакетами в порядке возрастания логических адресов. Размер пакета часто меньше размера блока. «Отложенная запись» блоков улучшает срок службы и быстродействие в случаях перезаписи большого объема данных за счет сокращения количества операций блочного стирания в число раз, равное размеру блока, деленному на размер пакета.
Краткое описание чертежей
Фиг. 1 – Назначение журнальных блоков для журналируемых страниц.
Фиг. 2 – Обобщенная схема алгоритма записи данных (журналирование).
Фиг. 3 – Пример состояния журнала страницы.
Фиг. 4 – Обобщенная схема алгоритма слияния журнального блока и соответствующего блока данных.
Фиг. 5 – Обобщенная схема алгоритма отложенной записи («отложенная запись» блоков).
Фиг. 6 – Схематичное изображение серии транзакций в соответствии с «отложенной записью».
Фиг. 7 – Схематичное изображение слияния блоков в соответствии с «отложенной записью».
Осуществление изобретения
Выбор сценария работы пользователя
В тестовом режиме работы носителя информации проведено моделирование пользовательской работы с памятью и собрана статистика о частоте перезаписи страниц. В результате анализа статистической информации сформированы различные сценарии работы пользователя с носителем информации, определяющие наиболее часто используемые (перезаписываемые) области памяти.
Например, данные сценарии могут соответствовать типу используемой файловой системы. Вне зависимости от того, какой тип файловой системы используется, отдельные логические области памяти небольшого объема (1-2 страницы) при эксплуатации задействованы для записи/перезаписи наиболее часто (так в файловой системе FAT32 это области загрузочной записи BOOT, корневой каталог ROOT, а также сама таблица размещения файлов FAT). Информация о том, в какой файловой системе отформатирован накопитель информации, находится в области загрузочной записи и считывается в начале сеанса работы. Выбирается соответствующий данной файловой системе сценарий работы.
При получении запроса на запись данных в определенный блок проверяется, свободны ли требуемые страницы блока. На свободные страницы запрошенного блока запись данных осуществляется непосредственно. В случае запроса на перезапись (запись информации в заполненные страницы блока) применяется один из двух вариантов: журналирование (для наиболее часто перезаписываемых страниц) или «отложенная запись»  блоков.
Журналирование наиболее часто используемых страниц
В соответствии с выбранным сценарием работы пользователя определяется некоторое число (n) наиболее часто перезаписываемых страниц для журналирования: A.x, B.y, C.z …, где A, B, C – адреса блоков, x, y, z – номера страниц в соответствующих блоках A, B, C. Каждой журналируемой странице назначается журнальный (зарезервированный) блок: A’, B’, C’ … соответственно (рис. 1).
Обобщенная схема алгоритма перезаписи данных представлена на рисунке 2. При получении запроса на перезапись данных по адресу A.x поверяется, является ли страница A.x журналируемой (1). Если да, то проверяется, заполнен ли соответствующий журнальный блок A’ (2). Если блок A’ заполнен, то производится очищение блока A’ (3). Затем производится запись на первую пустую страницу блока A’ (4). Если страница A.x не относится к журналируемым, то для адреса A.x работает «отложенная запись» блоков (5), рисунок 5.
Слияние журнального блока и блока данных
При поступлении запроса на чтение данных производится слияние запрошенного блока и соответствующего журнального блока, если журнальный блок непустой. Обобщенная схема алгоритма слияния блоков представлена на рисунке 4.
При получении запроса на чтение данных по адресу A.x поверяется, является ли страница A.x журналируемой (1). Если да, то проверяется, есть ли данные в соответствующем журнальном блоке A’ (2). Если блок A’ непустой, то выделяется третий чистый блок В (3), в который производится копирование последней заполненной (актуальной) страницы журнального блока A’ на свое место (по адресу B.x) (4), а также копирование данных остальных страниц запрошенного блока А (5); блоки А и A’ очищаются (6); в таблице соответствия логических и физических адресов логический адрес первоначально адресованного блока А  назначается новому блоку В и наоборот (7). После данных операций, а также если страница A.x не относится к журналируемым или соответствующий журнальный блок A’ не содержит данных, производится непосредственное чтение данных по адресу A.x (8).
«Отложенная запись» блоков
Для реализации «отложенной записи» зарезервирован один блок, называемый буферным (R).
Обобщенная схема алгоритма «отложенной записи» блоков представлена на рисунке 5. При получении запроса на перезапись данных по адресу D запись производится в буферный блок R (1). Номер блока текущей транзакции запоминается в переменной prevD (2). Если следующий запрос на перезапись относится к тому же блоку D, но другим страницам, запись снова осуществляется в буферный блок R (1). При переходе к другому блоку (prevD ≠ D) (3) в незаполненные страницы буферного блока R копируются страницы исходного блока prevD (слияние блоков - 4), затем исходный блок prevD очищается (5), а в таблице соответствия логических и физических адресов логический адрес первоначально адресованного блока prevD  назначается реально записанному (буферному) блоку R (6).
При первом запросе на чтение данных из блока D также производится слияние блоков prevD и R, стирание prevD и изменение указателей в таблице соответствия логических и физических адресов.
Схематично «отложенная запись» изображена на рисунках 6-7.