СПОСОБ И УСТРОЙСТВО ХРАНЕНИЯ, ЧТЕНИЯ И ЗАПИСИ СОСТАВНОГО ДОКУМЕНТА
METHOD AND APPARATUS FOR STORING, READING AND WRITING COMPOUND DOCUMENT

Область изобретения
Настоящее изобретение относится к технологии обработки данных, в частности к способу и устройству хранения, чтения и записи составного документа.
Уровень техники
Составной документ содержит не только текст, но и графику, данные электронных таблиц, звук, видеоизображение и другую информацию. Например, файлы записи сообщений и файлы фраз клиентов службы обмена Мгновенными Сообщениями МС (IM) могут сохраняться с использованием составных документов. С увеличением времени использования средств службы МС (IM) соответствующий составной документ будет становиться все больше и больше.
На фиг.1 схематично показана логическая структура хранения и потоков составного документа. Логическая структура составного документа очень похожа на структуру файловой системы. Каждый документ содержит корневое хранилище, имеющее от нуля до нескольких обычных хранилищ или потоков. У каждого хранилища и потока есть имя, которое обычно состоит из 16-разрядных символов Юникода и имеет длину не более 31 символа. Имена хранилищ или потоков в одном хранилище должны быть разными, а имена хранилищ или потоков в разных хранилищах могут быть одинаковыми.
За исключением заголовка, все данные составного документа организуются в виде потоков. Все потоки составного документа делятся на блоки данных меньшего размера, называемых секторами. Сектор может содержать данные управления или пользовательские данные. Весь составной документ состоит из заголовка, после которого следует ряд секторов. Все сектора имеют одинаковый размер, который задается в заголовке.
Сектора перечисляются в документе по порядку. Индекс сектора (начинающийся с 0) называется Идентификатором Сектора ИС (SID) и представляет собой 32-разрядное целое число со знаком. Если ИС (SID) имеет значение не меньше 0, он должен указывать на существующий сектор; если значение ИС (SID) отрицательное, он может иметь специальное назначение.
Связанный список, образованный всеми секторами потока, называется цепочкой секторов. Соседние сектора цепочки секторов могут не являться соседними физически. Чтобы упростить указание относительного положения каждого сектора в цепочке секторов, введено понятие цепочки идентификаторов секторов. Цепочка идентификаторов секторов - это массив идентификаторов секторов. В цепочке идентификаторов секторов последовательно записываются идентификаторы секторов потока, начиная с идентификатора первого сектора потока, до конца связанного списка (-2).
Потоки составного документа могут быть разделены по назначению на внутренние потоки управления и поток пользовательских данных. Внутренний поток управления содержит следующие компоненты: поток каталога, Главную Таблицу Выделения Секторов таблицы ГТВС (MSAT), Таблицу Выделения Секторов ТВС (SAT), Таблицу Выделения Коротких Секторов таблицы ТВКС (SSAT) и поток контейнера коротких потоков.
Главная таблица выделения секторов - это массив ИС (SID), содержащий последовательные идентификаторы секторов, которые используются для хранения таблицы выделения секторов. Размер таблицы ГТВС (MSAT) равен числу секторов, используемых для хранения таблицы ТВС (SAT), и хранится в заголовке.
Таблица ТВС (SAT) - это массив идентификаторов секторов, содержащий весь поток пользовательских данных и внутренний поток управления. Размер таблицы ТВС (SAT) равен числу секторов во всем составном документе. Индекс элемента массива таблицы ТВС (SAT) - это идентификатор сектора, представляемый этим элементом. Значение элемента - следующий узел сектора, представляемого этим элементом в цепочке секторов. Таблица ТВС (SAT) может содержать в любой позиции идентификатор свободного сектора (-1). Такие сектора не будут использоваться ни одним потоком. Если в этой позиции находится индикатор конца цепочки ИС (SID) (-2), это означает конец одного потока. Если в этой позиции находится индикатор конца цепочки ИС (SID) (-3), это означает, что представленный сектор используется для хранения таблицы ТВС (SAT). Если в этой позиции находится индикатор конца цепочки ИС (SID) (-4), это означает, что представленный сектор используется для хранения таблицы ГТВС (MSAT). Например, если значение элемента массива таблицы ТВС (SAT) равно -1, это означает, что сектор, соответствующий индексу этого элемента не используется ни одним потоком. Если значение элемента равно -2, это означает конец одного потока. Если значение элемента равно -3, это означает, что сектор, соответствующий индексу этого элемента, используется для хранения таблицы ТВС (SAT). Если значение элемента равно -4, это означает, что сектор, соответствующий индексу этого элемента, используется для хранения таблицы ГТВС (MSAT).
Поток контейнера коротких потоков идентичен другому обычному пользовательскому потоку, длина которого не меньше длины стандартного потока. В цепочке секторов потока контейнера коротких потоков идентификатор первого сектора хранится в записи каталога корневого хранилища. Цепочку идентификаторов секторов потока контейнера коротких потоков можно получить из таблицы ТВС (SAT).
Таблица ТВКС (SSAT) - это другой массив ИС (SID), содержащий цепочки идентификаторов секторов всех коротких потоков. Таблица ТВКС (SSAT), соответствующая внутреннему потоку управления, создается так же, как таблица ТВКС (SSAT) обычных потоков. Первый идентификатор сектора таблицы ТВКС (SSAT) хранится в заголовке. Функция таблицы ТВКС (SSAT) очень похожа на функцию таблицы ТВС (SAT). Единственное отличие состоит в том, что идентификаторы секторов таблицы ТВКС (SSAT) указывают на короткие, а не на обычные сектора.
Поток каталога - это внутренний поток управления, содержащий массив записей каталога. Каждый массив записей каталога указывает на хранилище или поток в составном документе. В потоке каталога индекс записи каталога 0 является начальным и называется Идентификатором Записи Каталога ИЗК (DID).
Упомянутый выше составной документ не управляет выделением секторов, что приводит к большому числу маленьких сегментов; перемещения во всем составном документе поддерживаются средствами ввода-вывода, что серьезно влияет на эффективность. Таблицы ГТВС (MSAT), ТВС (SAT), ТВКС (SSAT) и запись каталога распределяются по всему составному документу, что серьезно влияет на такие его характеристики, как скорость открытия, просмотра, записи и подобные характеристики. Для обычных потоков и коротких потоков очень маленький блок выделения и выделение секторов без управления также приводят к большому числу маленьких сегментов.
Краткое описание изобретения
В вариантах осуществления настоящего изобретения предлагаются способ и устройство хранения, чтения и записи составного документа.
В соответствии с одним из вариантов осуществления изобретения предложен способ хранения составного документа, в котором предусмотрены следующие действия: предварительное выделение для внутреннего потока управления составного документа начальной области памяти, состоящей из непрерывных секторов или кластеров секторов, и хранение в ней этого потока.
В соответствии с одним из вариантов осуществления изобретения предлагается также способ чтения и записи составного документа. При этом для хранения внутреннего потока управления составного документа используется указанный выше способ. В способе чтения и записи составного документа предусмотрены следующие действия:
оценка при чтении сектора или кластера секторов внутреннего потока управления, хранится ли в одном или нескольких секторах или кластерах секторов, соседних с этим сектором или кластером секторов, внутренний поток управления того же типа, что и в данном секторе или кластере секторов;
при положительном результате оценки выполняют единовременное считывание в память данных, хранящихся в этом секторе или кластере секторов и одном или нескольких секторах или кластерах секторов, соседних с данным сектором или кластером секторов.
В соответствии с одним из вариантов осуществления настоящего изобретения предлагается также устройство хранения составного документа, содержащее следующие модули:
первый модуль предварительного выделения памяти для потока управления, предназначенный для предварительного выделения начальной области памяти для внутреннего потока управления составного документа, причем начальная область памяти состоит из непрерывных секторов или кластеров секторов;
второй модуль предварительного выделения памяти для потока управления, предназначенный для хранения внутреннего потока управления в начальной области памяти.
В одном из вариантов осуществления настоящего изобретения предлагается также устройство чтения и записи составного документа. При этом для хранения внутреннего потока управления составного документа используется указанное выше устройство. Устройство чтения и записи составного документа содержит следующие модули:
модуль оценки сектора, предназначенный для того, чтобы при чтении сектора или кластера секторов внутреннего потока управления определить, хранится ли в одном или нескольких секторах или кластерах секторов, соседних с этим сектором или кластером секторов, внутренний поток управления того же типа, что и в данном секторе или кластере секторов;
модуль чтения потока управления, предназначенный для того, чтобы при положительном результате оценки единовременно считать в память данные, хранящиеся в этом секторе или кластере секторов и одном или нескольких секторах или кластерах секторов, соседних с данным сектором или кластером секторов.
В решениях, предложенных в вариантах осуществления настоящего изобретения, для хранения внутреннего потока управления применяется стратегия предварительного выделения пространства памяти, что сокращает число маленьких сегментов этого потока в составном документе. Предварительное выделение области памяти повышает вероятность целостного хранения потока пользовательских данных и внутреннего потока управления в составном документе. Ввод-вывод может быть оптимизирован с помощью стратегии использования кэша чтения и пакетной записи, которая позволяет повысить эффективность чтения и записи.
Краткое описание чертежей
На фиг.1 схематично показана логическая структура хранения и потоков составного документа в соответствии с известным уровнем техники.
На фиг.2 представлена блок-схема способа хранения согласно предложенной в соответствии с одним из вариантов осуществления настоящего изобретения стратегии предварительного выделения области памяти для внутреннего потока управления.
На фиг.3 приведена блок-схема способа хранения согласно предложенной в соответствии с настоящим изобретением стратегии предварительного выделения области памяти для потока пользовательских данных.
На фиг.4 представлена блок-схема записи состояния зарезервированного пространства хранения данных для каждого потока пользовательских данных в способе хранения, проиллюстрированном на фиг.3.
На фиг.5 показана блок-схема устройства хранения составного документа в соответствии с одним из вариантов настоящего изобретения.
На фиг.6 представлена другая блок-схема устройства хранения составного документа в соответствии с вариантом осуществления настоящего изобретения.
На фиг.7 представлена другая блок-схема устройства хранения составного документа в соответствии с вариантом осуществления настоящего изобретения.
На фиг.8 приведена еще одна блок-схема устройства хранения составного документа в соответствии с вариантом осуществления настоящего изобретения.
На фиг.9 показана блок-схема устройства хранения составного документа в соответствии с другим вариантом осуществления настоящего изобретения.
На фиг.10 представлена другая блок-схема устройства хранения составного документа в соответствии с вариантом осуществления настоящего изобретения.
На фиг.11 представлена еще одна другая блок-схема устройства хранения составного документа в соответствии с вариантом осуществления настоящего изобретения.
На фиг.12 приведена диаграмма с результатами сравнения временных затрат при использовании интерфейса составного документа Microsoft для открытия базы данных db1 и использовании интерфейса составного документа в соответствии с вариантом осуществления настоящего изобретения для открытия базы данных db2.
На фиг.13 показана диаграмма с результатами сравнения временных затрат при использовании интерфейса составного документа Microsoft для аналогового чтения семи записей сообщений друзей в базе данных db1 и использовании интерфейса составного документа в соответствии с вариантом осуществления настоящего изобретения для аналогового чтения семи записей сообщений друзей в базе данных db2.
На фиг.14 показана диаграмма с результатами сравнения временных затрат для аналоговой записи семи сообщений друзей при использовании интерфейса составного документа Microsoft и интерфейса составного документа в соответствии с вариантом осуществления настоящего изобретения.
Подробное описание примеров осуществления изобретения
Ниже со ссылками на приложенные чертежи подробно рассматриваются варианты осуществления предложенного изобретения. Подробно рассмотренные варианты осуществления представляют только некоторые из его возможных вариантов. Другие варианты осуществления, полученные специалистами в данной области на основе представленных вариантов без внесения какого-либо изобретательского вклада, подпадают под объем охраны настоящего изобретения.
Чтобы решить проблему плохих характеристик открытия, чтения и записи известного составного документа Microsoft вследствие большого числа маленьких сегментов, в одном из вариантов осуществления настоящего изобретения предлагается новый составной документ, который может быть полностью совместим с форматом известного составного документа Microsoft. В соответствии с вариантом осуществления настоящего изобретения для хранения составного документа используется стратегия предварительного выделения области памяти определенного размера для хранения внутреннего потока управления и (или) потока пользовательских данных, чтобы обеспечить непрерывность блока данных и сократить число маленьких сегментов. Кроме того, согласно применяемому в настоящем изобретении режиму хранения составного документа в одном из вариантов осуществления изобретения предлагается также стратегия использования кэша чтения и пакетной записи для оптимизации ввода-вывода, которая повышает скорость открытия, чтения и записи составного документа.
Составной документ в соответствии с вариантом осуществления настоящего изобретения может храниться в блоке памяти, называемом сектором или кластером секторов. На этапе начальных исследований было обнаружено, что в таблице ГТВС (MSAT), в записи каталога и в таблице ТВКС (SSAT) известного составного документа Microsoft сектора не являются непрерывными и память выделяется секторами размером 512 бит, что очень мало и повышает вероятность создания маленьких сегментов. Чтобы существенно сократить число маленьких сегментов, в варианте осуществления настоящего изобретения память выделяется более крупными блоками - кластерами секторов (аналогичными кластеру в диспетчере дисков). Согласно критерию оценки составного документа один поток размером менее 4 килобайтов (4×1024 байтов, 4КБ) считается коротким потоком. Таким образом, в качестве размера кластера может быть выбран блок величиной более 4 КБ, например 8 КБ. Для осуществления блочного режима выделения кластеров используется очень простой принцип: при каждом выделении выделяются сектора с выравниванием по границе 8 КБ. При этом всегда обеспечивается выделение памяти блоками размером не меньше размера кластера секторов. Поскольку размер кластера 8 КБ кратен 512 байтам, составной документ в соответствии с вариантом осуществления настоящего изобретения может быть полностью совместим с форматом известного составного документа Microsoft. В зависимости от конкретных условий размер кластера может быть также другим, например кратным размеру сектора.
Как указывалось выше, для хранения составного документа в соответствии с вариантом осуществления настоящего изобретения используется стратегия предварительного выделения памяти. Поскольку сущность внутреннего потока управления отличается от сущности потока пользовательских данных, конкретные стратегии выделения памяти для этих потоков различаются. Как видно из фиг.2, в способе хранения с использованием стратегии предварительного выделения памяти для внутреннего потока управления предусмотрены следующие действия.
Шаг 201: для внутреннего потока управления составного документа предварительно выделяется начальная область памяти, состоящая из непрерывных секторов или кластеров секторов.
В этом или другом варианте осуществления настоящего изобретения блоком названной области памяти может быть сектор или упомянутый выше кластер секторов. Однако независимо от применяемых блоков (секторов или кластеров секторов) в соответствии с одним вариантом осуществления в качестве блока памяти не будут использоваться одновременно и сектор, и кластер секторов, то есть в варианте осуществления одного составного документа в качестве базового блока памяти будет использоваться либо сектор, либо кластер секторов. Другими словами, в соответствии с одним вариантом осуществления для хранения как внутреннего потока управления, так и потока пользовательских данных используется один и тот же базовый блок памяти.
Внутренним потоком управления в данном варианте осуществления может быть один или несколько из следующих компонентов: главная таблица выделения секторов, таблица выделения секторов, поток контейнера коротких потоков, таблица выделения коротких секторов и поток каталога. Решение о предварительном выделении области памяти в данном варианте осуществления может быть принято для одного из названных выше внутренних потоков управления, например таблицы ГТВС (MSAT) составного документа, а также для нескольких или всех внутренних потоков управления составного документа.
Следует отметить, что в случае предварительного выделения областей памяти для нескольких или всех внутренних потоков управления составного документа для внутренних потоков управления разных типов предварительно выделяются разные начальные области памяти.
Шаг 202: сохранение внутреннего потока управления в начальной области памяти.
Поскольку в данном варианте осуществления настоящего изобретения используется стратегия предварительного выделения памяти, для хранения внутреннего потока управления составного документа предварительно выделяется область памяти определенного размера, что обеспечивает непрерывность блока данных и уменьшение числа маленьких сегментов. Предварительное выделение области памяти повышает вероятность целостного хранения внутреннего потока управления в составном документе. При этом ввод-вывод можно оптимизировать путем применения стратегии использования кэша чтения и пакетной записи, которая дополнительно повышает эффективность чтения и записи.
Если в данном варианте осуществления настоящего изобретения размер внутреннего потока управления превышает размер начальной области памяти, в описанном выше способе может быть также предусмотрено предварительное выделение второй области памяти для хранения такого потока, причем вторая область памяти также состоит из непрерывных секторов или кластеров секторов.
Поскольку в данном варианте осуществления настоящего изобретения внутренний поток управления, например таблицы ТВС (SAT), большой и при увеличении составного документа таблица ТВС (SAT) увеличивается, выделенных начальной области памяти и второй области памяти становится недостаточно, и согласно стратегии предварительного выделения пространства памяти для хранения внутреннего потока управления может быть предварительно выделена новая область памяти. Стратегия предварительного выделения пространства памяти состоит в том, что, если выделенной области памяти недостаточно для хранения внутренних потоков управления, всегда предварительно выделяется новая область памяти, и каждая из предварительно выделенных областей памяти состоит из непрерывных секторов или кластеров секторов.
Кроме того, в описанном выше варианте осуществления размеры кластера секторов и предварительно выделяемого пространства памяти могут быть следующими: кластер секторов - непрерывная область размером 8 КБ; размер предварительно выделяемой начальной области памяти - 8 КБ; размеры предварительно выделяемых новых областей памяти могут быть (по порядку) 80 КБ (вторая область памяти), 800 КБ и 1 МБ. Если размер предварительно выделенной области памяти - 1 МБ, то размер каждой следующей выделяемой области памяти - также 1 МБ. Кластером секторов может также быть непрерывная область размером, кратным 4 КБ.
Ниже описываются некоторые варианты осуществления предварительного выделения памяти для внутренних потоков управления разных типов.
(1) Способ предварительного выделения памяти для главной таблицы выделения секторов
Если каждая таблица ГТВС (MSAT) содержит идентификаторы ИС (SID) 128-ми секторов таблицы ТВС (SAT), то каждый сектор таблицы ТВС (SAT) содержит идентификаторы ИС (SID) 128-ми секторов. При этом для одного документа размером 1 ГБ потребуется главная таблица выделения секторов размером 64 КБ. В заголовок составного документа включаются 109 ИС (SID) таблицы ГТВС (MSAT). При этом даже если дополнительная таблица ГТВС (MSAT) не используется, может поддерживаться составной документ максимальным размером 6,8 МБ. 1 ГБ=1024 МБ=1024×1024 КБ.
В способе предварительного выделения памяти для главной таблицы выделения секторов предусмотрено выделение новой непрерывной области памяти в соответствии с размером таблицы ГТВС (MSAT) и с учетом его возможного увеличения. Например, размер начальной области памяти может быть установлен равным 8 КБ, размер второй области памяти может составлять 80 КБ, а размеры других предварительно выделяемых непрерывных областей памяти могут быть (по порядку) 80 КБ, 800 КБ, 1 МБ, 1 МБ, 1 МБ и так далее, то есть принцип задания размера предварительно выделяемой области памяти может быть следующим: для размера менее 1 МБ размер увеличивается путем умножения на 10, а для размера более 1 МБ остается равным 1 МБ. Все использованные предварительно выделенные области памяти объединяются для образования цепочки секторов таблицы ГТВС (MSAT). ИС (SID) для таблицы ТВС (SAT), отсутствующей в секторе таблицы ГТВС (MSAT), принимает значение - 1. Для документа размером менее 1,28 ГБ существует только один маленький сегмент таблицы ГТВС (MSAT), кроме заголовка. Поэтому проблему слияния таблицы ГТВС (MSAT) можно не учитывать.
(2) Способ предварительного выделения памяти для таблицы выделения секторов
Согласно определению формата составного документа размер таблицы ТВС (SAT) непосредственно зависит от размера документа. Теоретически, когда размер таблицы ТВС (SAT) возрастает, размер составного документа также возрастает, но размер потоков данных, хранящихся в составном документе, может оставаться неизменным. Поскольку для известного составного документа Microsoft принцип предварительного выделения памяти не предусмотрен, размер его таблицы ТВС (SAT) увеличивается с увеличением размера составного документа. Однако различие между составным документом в соответствии с вариантом осуществления настоящего изобретения и известным составным документом Microsoft состоит в том, что для таблицы ТВС (SAT) составного документа в соответствии с вариантом осуществления настоящего изобретения может предварительно выделяться память и при увеличении размера составного документа размер хранящихся в нем данных может оставаться неизменным.
Каждый сектор таблицы ТВС (SAT) содержит идентификаторы ИС (SID) 128-ми секторов. При этом для одного документа размером 1 ГБ потребуется главная таблица выделения секторов размером 8 МБ.
Подобно случаю предварительного выделения памяти для таблицы ГТВС (MSAT), начальный размер области памяти таблицы ТВС (SAT) может быть 8 КБ, а размер следующих выделяемых областей памяти может быть (по порядку) 80 КБ, 800 КБ, 1 МБ, 1 МБ, 1 МБ и так далее, то есть для размера менее 1 МБ размер увеличивается путем умножения на 10, а для размера более 1 МБ остается равным 1 МБ. Для документа размером менее 800 МБ существует 8 маленьких сегментов. В этом режиме имеется мало маленьких сегментов таблицы ТВС (SAT), и, следовательно, осуществление слияния таблицы ТВС (SAT) не требуется.
Поскольку 4 байта в таблице ТВС (SAT) могут указывать на сектор потока данных (512 байтов), при отсутствии предварительного выделения таблица ТВС (SAT) занимает пространство 4/512, то есть 1/128 часть составного документа. Максимальный размер предварительно выделяемого пространства для таблицы ТВС (SAT) в варианте осуществления настоящего изобретения в 10 раз превышает используемое в текущий момент пространство таблицы ТВС (SAT). Следовательно, при предварительном выделении памяти для таблицы ТВС (SAT) потребляется максимум 10/128=8 пространства составного документа.
(3) Способ предварительного выделения памяти для потока контейнера коротких потоков
Поток контейнера коротких потоков - это контейнер потоков размером менее 4 КБ, используемый для хранения всех потоков пользователя. Как правило, большинство потоков в средствах службы обмена мгновенными сообщениями являются короткими, например gif- или bmp-файлы ресурсов и небольшие конфигурационные файлы. Таким образом, маленькие сегменты потока контейнера коротких потоков будут существенно влиять на характеристики составного документа.
Подобно случаю предварительного выделения памяти для таблицы ГТВС (MSAT), начальный размер предварительно выделяемой области памяти для потока контейнера коротких потоков может быть 8 КБ, а размер других выделяемых областей памяти может быть (по порядку) 80 КБ, 800 КБ, 1 МБ, 1 МБ, 1 МБ и так далее, то есть для размера менее 1 МБ размер увеличивается путем умножения на 10, а для размера более 1 МБ остается равным 1 МБ. Если размер предварительно выделяемой области памяти является фиксированным и равен 1 МБ, то каждый раз можно добавлять 256 коротких потоков согласно фактическому взаимодействию с пользователем. Такая скорость достаточна для удовлетворения требований.
(4) Способ предварительного выделения памяти для таблицы выделения коротких секторов
Хотя кажется, что размер таблицы ТВКС (SSAT) должен быть прямо пропорционален размеру потока контейнера коротких потоков, фактически, таблица ТВКС (SSAT) составного документа, созданного Windows, может превышать это значение. При этом размер таблицы ТВКС (SSAT) не должен быть больше 512 байтов. Способ предварительного выделения памяти для таблицы выделения коротких секторов идентичен способу выделения памяти для потока контейнера коротких секторов. В нем также используется следующая модель: увеличение до 8 КБ, 80 КБ, 800 КБ, 1 МБ, 1 МБ, 1 МБ и так далее.
Поскольку поток контейнера коротких потоков не должен точно соответствовать таблице ТВКС (SSAT), условие его расширения - невозможность записи из-за недостатка емкости. Когда емкости недостаточно, она может быть расширена (примечание: максимальное значение после расширения не может превышать размер, соответствующий таблице ТВКС (SSAT)).
(5) Способ предварительного выделения памяти для потока каталога
Рассмотрим в качестве примера составной документ Microsoft. В определении его формата каждая запись каталога имеет размер 128 байтов.
В способе предварительного выделения памяти для потока каталога может использоваться следующая модель: начальная область размером 8 КБ (может содержать 64 записи каталога), последующие области размером 8 КБ, 80 КБ, 800 КБ, 1 МБ, 1 МБ, 1 МБ и так далее; в качестве неиспользуемой записи каталога устанавливается пустая запись. Таким образом, если число записей каталога меньше 6400, имеется только два маленьких сегмента размером 80 КБ и 800 КБ, и слияние потока каталога не требуется.
Если при использовании рассмотренных выше способов предварительного выделения памяти для различных внутренних потоков управления выделенной в данный момент емкости недостаточно, емкость может быть расширена согласно указанной выше модели предварительного выделения памяти. Например, условие расширения таблицы ТВС (SAT) - недостаточная емкость для записи потока данных; условие расширения таблицы ГТВС (MSAT) - недостаточное пространство для хранения таблицы ГТВС (MSAT) при увеличении таблицы ТВС (SAT).
Способы предварительного выделения памяти для внутренних потоков управления описаны выше. Как видно из фиг.3, в способе предварительного выделения области памяти для потока пользовательских данных (называемого потоком данных) предусмотрены следующие шаги.
Шаг 301: для потока данных открытого в настоящий момент составного документа резервируется пространство памяти. Другими словами, при предварительном выделении памяти для потока пользовательских данных используется режим резервирования пространства памяти, то есть при каждом выделении новых секторов или кластеров секторов резервируется пространство заданного размера, которое не должно использоваться другими объектами. Например, при записи потока данных резервируется соседний кластер секторов, размер которого превышает размер записываемых в настоящий момент данных для записи этого потока. Поскольку при записи потока существует вероятность его повторной записи позже, для того чтобы записанные два раза данные были непрерывными, при записи может быть зарезервировано непрерывное пространство для следующей записи.
Область памяти потока данных может содержать пространство памяти обычного потока и (или) пространство памяти короткого потока. Пространство памяти обычного потока в некоторых вариантах осуществления может иметь размер 50 или больше от длины соответствующего текущего потока, а пространство памяти короткого потока может иметь размер 4 КБ.
Шаг 302: поток данных составного документа сохраняется в зарезервированном для него пространстве памяти.
Шаг 303: когда составной документ закрывается, неиспользуемое пространство зарезервированной для потока данных памяти освобождается.
Поскольку в текущий момент может требоваться обработка нескольких потоков пользовательских данных, необходимо регистрировать состояние зарезервированного пространства памяти для каждого потока пользовательских данных, чтобы это состояние можно было учитывать при необходимости зарезервировать новое пространство памяти потока данных. Таким образом, в данном варианте осуществления могут быть также предусмотрены следующие шаги.
Шаг 401: регистрация состояния зарезервированного пространства памяти для потока данных открытого в текущий момент составного документа. Например, на период от открытия до закрытия составного документа в памяти может быть создана таблица состояния зарезервированного пространства для отслеживания состояния зарезервированного пространства составного документа. К этой таблице можно обращаться при запросе свободных кластеров секторов. Поскольку одновременно может быть открыто несколько составных документов, созданная (например, с помощью кодов) таблица состояний зарезервированных пространств может представлять собой глобальную карту. При этом состояния зарезервированных пространств потоков данных становятся известными всем составным документам.
Шаг 402: при необходимости запросить зарезервированное пространство памяти для потока данных составного документа выполняются следующие действия: запрос неиспользуемых секторов или кластеров секторов в таблице выделения секторов; проверка, не зарезервированы ли неиспользуемые сектора или кластеры секторов в качестве пространств памяти для потоков данных; выделение неиспользуемых секторов или кластеров секторов, не зарезервированных в качестве пространств памяти для потоков данных, в качестве зарезервированного пространства памяти для потока данных составного документа. Например, при необходимости запросить зарезервированное пространство памяти для одного потока данных составного документа выполняются следующие действия: запрос неиспользуемых секторов или кластеров секторов в таблице выделения секторов; проверка, не зарезервированы ли неиспользуемые сектора или кластеры секторов в качестве пространств памяти другими потоками данных; выделение неиспользуемых секторов или кластеров секторов, не зарезервированных в качестве пространств памяти другими потоками данных, в качестве зарезервированного пространства памяти потока данных. Например, при запросе нового кластера секторов сначала выполняется поиск неиспользуемого сектора в таблице ТВС (SAT), а затем, перед выделением, проверяется, не относится ли этот кластер к зарезервированному пространству другого объекта. Зарезервированное пространство в таблице ТВС (SAT) не регистрирует данные цепочки секторов.
Шаг 403: когда составной документ закрывается, информация о состояниях зарезервированных для него пространств памяти потоков данных удаляется. Например, при закрытии составного документа таблица состояний зарезервированных пространств также удаляется и не будет записывать в этот документ никакой информации.
Ниже на основе описания способов хранения в рассмотренных выше вариантах осуществления описываются некоторые варианты осуществления способа предварительного выделения памяти для потоков пользовательских данных разных типов.
(1) Способ предварительного выделения памяти для обычного потока
При предварительном выделении памяти для обычного потока используется следующая модель резервирования пространства памяти. Поскольку большую часть времени открытые в текущий момент потоки с операциями записи составляют лишь малую часть потоков, для них может быть зарезервировано относительно большое пространство. Каждый раз пространство предварительно выделяемой памяти определяется равным 15 длины текущего потока, благодаря чему в нем содержится больше маленьких сегментов. Если зарезервированное пространство не может использоваться в текущий период открытого состояния, при открытии составного документа в следующий раз оно будет использоваться другими потоками.
(2) Способ предварительного выделения памяти для короткого потока
Согласно определениям формата составного документа Microsoft поток размером менее 4 КБ считается коротким потоком. При предварительном выделении памяти для короткого потока используется следующая модель резервирования пространства памяти: чтобы исключить появление маленьких сегментов в одном коротком потоке, для каждого короткого потока, независимо от его размера, резервируется одинаковое пространство памяти размером 4 КБ. В данном варианте осуществления сектора выделяются по принципу выравнивания начального адреса 4 КБ, чтобы обеспечить выделение для каждого короткого потока пространства размером 4 КБ.
Как указано в приведенном выше описании, для хранения внутренних потоков управления и потоков пользовательских данных составного документа используется стратегия предварительного выделения памяти, что позволяет сократить число маленьких сегментов в составном документе и обеспечить непрерывность данных.
После применения стратегии предварительного выделения памяти, предложенной в варианте осуществления настоящего изобретения, теоретически, данные системы составного документа представляют собой большие порции, и к некоторым внутренним потокам управления, например таблицы ТВКС (SSAT) и таблицы ТВС (SAT), требуется частое обращение, и они характеризуются высокой частотой повторного доступа.
Хотя в Windows имеется алгоритм прогнозирования содержимого буфера, содержимое, к которому осуществляется повторный доступ, предпочтительно добавляется в кэш, но, поскольку конкретное применение данных документа неизвестно и уровень приоритета данных кэша также неизвестен, алгоритм прогнозирования не может быть на 100% точным. Поэтому для дополнительного повышения эффективности чтения и записи составных документов, для которых используются способы хранения, описанные в рассмотренных выше вариантах осуществления, может применяться описанный ниже способ. В способе чтения и записи составного документа одним из вариантов осуществления настоящего изобретения при чтении и записи внутреннего потока управления предусмотрены следующие действия.
Шаг А1: оценка при чтении сектора или кластера секторов внутреннего потока управления, хранится ли в одном или нескольких секторах или кластерах секторов, соседних с этим сектором или кластером секторов, внутренний поток управления того же типа, что и в данном секторе или кластере секторов. Внутренним потоком управления может быть один из следующих компонентов: главная таблица выделения секторов, таблица выделения секторов, поток контейнера коротких потоков, таблица выделения коротких секторов и поток каталога.
Шаг А2: если результат оценки - да, единовременное считывание в память данных, хранящихся в этом секторе или кластере секторов и одном или нескольких секторах или кластерах секторов, соседних с данным сектором или кластером секторов.
Например, в варианте осуществления настоящего изобретения при необходимости чтения какого-либо сектора (или кластера секторов) таблицы ТВС (SAT) сначала определяется, хранится ли также в секторах (или кластерах секторов), соседних с этим сектором (или кластером секторов), таблица ТВС (SAT) (идентификаторы секторов, хранящиеся в массиве таблицы ТВС (SAT), имеют некоторые специальные значения, например, значение -3 указывает, что в данном секторе хранится таблица ТВС (SAT)). Если да - эта порция данных единовременно считывается в память. Поскольку ресурсы ввода-вывода в основном используются для перемещения по заголовкам, так как для перемещения к целевому объекту требуется много времени, должно считываться немного больше данных. Поэтому при использовании рассмотренного выше решения без замены механизма кэширования Windows осуществляется просто предварительное чтение большой порции данных, к которым требуется частый доступ, вместо чтения каждый раз фиксированного числа порций, что может существенно повысить эффективность ввода-вывода.
С другой стороны, если при чтении потока пользовательских данных (известного составного документа Microsoft, например, составного документа, реализованного корпорацией Microsoft, для которого чтение и запись осуществляются секторами) считан некоторый блок данных, необходимо вызвать по очереди функции SetFilePointerEx и ReadFile. Использование этого способа ведет к нескольким отрицательным результатам: (1) при чтении сектора система предварительно считывает и кэширует следующие данные большого объема; если размер запрошенного блока данных превышает размер кэша, предусмотренного в системе, выполняется поиск на диске (среднее время поиска на обычных жестких дисках - более 10 мс); (2) функции SetFilePointerEx и ReadFile вызываются ядром, и для выполнения этих вызовов расходуются ресурсы; только в процессе входа в систему Hummer функции ReadFile и SetFilePointerEx вызываются более 40000 раз; (3) частое выполнение ввода-вывода также может влиять на системные характеристики создаваемых транзакционных документов.
Таким образом, в варианте осуществления настоящего изобретения при чтении потока данных выполняются следующие действия.
В1: при чтении потока данных определяется, существует ли в потоке непрерывный блок данных;
В2: если да, выполняется пакетное чтение потока данных с учетом максимальной длины непрерывного блока.
Поскольку стратегия предварительного выделения пространства памяти для потока данных может обеспечивать непрерывность данных потока, в стратегии использования кэша чтения составного документа в соответствии с вариантом осуществления настоящего изобретения должна выполняться попытка кэшировать данные считываемого в текущий момент потока. В кэше чтения известного составного документа Microsoft кэшируются только данные задней части текущего сектора, но из-за наличия в известном составном документе Microsoft большого числа маленьких сегментов эта часть данных, вероятно, не относится к текущему потоку. Поэтому использование описанного выше способа чтения данных, предложенного в варианте осуществления настоящего изобретения, позволяет решить указанную проблему, имеющуюся в известной технологии.
С другой стороны, из-за необходимости часто записывать и удалять записи таблицы ТВС (SAT) и таблицы ТВКС (SSAT) во время выделения и освобождения списков, связанных с секторами, в варианте осуществления настоящего изобретения блоки данных потоков являются непрерывными. Соответствующие записи таблицы ТВС (SAT) также непрерывны. Поэтому при работе с записями таблицы ТВС (SAT) могут выполняться следующие действия.
С1: при выделении и освобождении списка, связанного с сектором, определяется, является ли соответствующая запись внутреннего потока управления непрерывной.
С2: если да, выполняется пакетная обработка непрерывной записи внутреннего потока управления.
Согласно вариантам осуществления описанных выше способов в одном из вариантов осуществления настоящего изобретения предлагается также соответствующее устройство. Как видно из фиг.5, соответствующее устройство 1 хранения составного документа содержит следующие модули:
первый модуль 10 предварительного выделения памяти для потока управления, предназначенный для предварительного выделения начальной области памяти для внутреннего потока управления составного документа, причем начальная область памяти состоит из непрерывных секторов или кластеров секторов;
второй модуль 12 предварительного выделения памяти для потока управления, предназначенный для хранения внутреннего потока управления в начальной области памяти и (при превышении этим потоком размера начальной области памяти) предварительного выделения второй области памяти для хранения внутреннего потока управления размером больше размера начальной области памяти, причем вторая область памяти также состоит из непрерывных секторов или кластеров секторов.
Внутренним потоком управления может быть один или несколько из следующих компонентов: главная таблица выделения секторов, таблица выделения секторов, поток контейнера коротких потоков, таблица выделения коротких секторов и поток каталога. Если внутренний поток управления состоит из двух или более перечисленных выше компонентов, первый модуль 10 предварительного выделения памяти для потока управления служит для предварительного выделения разных начальных областей памяти для внутренних потоков управления разных типов.
Как видно из фиг.6, устройство 1 может также содержать следующий модуль:
модуль 14 стратегии предварительного выделения памяти для потока управления, предназначенный для предварительного выделения новой области памяти для внутреннего потока управления согласно стратегии предварительного выделения пространства памяти, когда размер внутреннего потока управления превышает размер второй области памяти. Стратегия предварительного выделения пространства памяти состоит в том, что, если выделенной области памяти недостаточно для хранения внутреннего потока управления, всегда предварительно выделяется новая область памяти, и каждая из предварительно выделенных областей памяти состоит из непрерывных секторов или кластеров секторов.
В некоторых вариантах осуществления кластером секторов является непрерывная область размером 8 КБ; размер предварительно выделяемой начальной области памяти - 8 КБ, размер предварительно выделяемых новых областей памяти может быть (по порядку) 80 КБ, 800 КБ и 1 МБ. Если размер предварительно выделенной области памяти - 1 МБ, то размер каждой следующей выделяемой области памяти - также 1 МБ.
Как видно из фиг.7 и 8, устройство 1 может также содержать следующие модули:
модуль 11 резервирования памяти для потока данных, предназначенный для резервирования пространства памяти для потока данных открытого в текущий момент составного документа;
модуль 13 хранения потока данных, предназначенный для хранения потока данных составного документа в зарезервированном для этого потока пространстве памяти;
модуль 15 освобождения зарезервированной памяти для потока данных, предназначенный для освобождения неиспользуемого пространства зарезервированной для потока данных памяти при закрытии составного документа;
модуль 17 регистрации состояния, предназначенный для регистрации состояния зарезервированного пространства памяти для потока данных открытого в текущий момент составного документа. При наличии модуля 17 регистрации состояния модуль 15 освобождения зарезервированной памяти для потока данных служит также для запроса неиспользуемых секторов или кластеров секторов в таблице выделения секторов, проверки, не зарезервированы ли неиспользуемые сектора или кластеры секторов в качестве пространств памяти для потоков данных, и выделения неиспользуемых секторов или кластеров секторов, не зарезервированных в качестве пространств памяти для потоков данных, в качестве зарезервированного пространства памяти для потока данных составного документа, когда необходимо запросить такое пространство. Модуль 15 освобождения зарезервированной памяти для потока данных может также быть настроен для удаления информации о состояниях зарезервированных пространств памяти потоков данных составного документа при закрытии составного документа.
Пунктирными линиями на фиг.7 и 8 обозначен модуль, который может присутствовать или отсутствовать в составном документе.
В некоторых вариантах осуществления пространство памяти потока данных может содержать пространство памяти обычного потока и (или) пространство памяти короткого потока. Пространство памяти обычного потока может иметь размер 50% или больше от длины соответствующего текущего потока, а пространство памяти короткого потока может иметь размер 4 КБ.
Как видно из фиг.9-11, устройство 2 чтения и записи составного документа в соответствии с одним из вариантов осуществления настоящего изобретения содержит следующие модули:
модуль 20 оценки сектора, предназначенный для того, чтобы при чтении сектора или кластера секторов внутреннего потока управления определить, хранится ли в одном или нескольких секторах или кластерах секторов, соседних с этим сектором или кластером секторов, внутренний поток управления того же типа, что и в данном секторе или кластере секторов;
модуль 22 чтения потока управления, предназначенный для того, чтобы при положительном результате оценки единовременно считать в память данные, хранящиеся в этом секторе или кластере секторов и одном или нескольких секторах или кластерах секторов, соседних с данным сектором или кластером секторов;
модуль 24 чтения потока данных, предназначенный для выявления при чтении потока данных наличия в нем непрерывного блока данных и выполнения пакетного чтения потока с учетом максимальной длины непрерывного блока, если такой блок в потоке есть;
модуль 26 оценки записи потока управления, предназначенный для того, чтобы при выделении и освобождении списка, связанного с сектором, определить, является ли соответствующая запись внутреннего потока управления непрерывной;
модуль 28 пакетной обработки, служащий для пакетной обработки непрерывной записи внутреннего потока управления при положительном результате оценки.
Внутренним потоком управления может быть один из следующих компонентов: главная таблица выделения секторов, таблица выделения секторов, поток контейнера коротких потоков, таблица выделения коротких секторов и поток каталога.
Конкретные концепции и рабочие режимы варианта осуществления описанного выше устройства соответствуют концепциям и режимам реализации рассмотренного выше способа и здесь повторяться не будут.
С помощью предложенных в вариантах осуществления настоящего изобретения стратегии предварительного выделения памяти для хранения составного документа и стратегии использования кэша чтения и пакетной записи для одновременного выполнения операций ввода-вывода можно существенно улучшить характеристики открытия, чтения и записи составного документа. Составной документ, полученный с использованием способа хранения, предложенного в варианте осуществления настоящего изобретения, может быть полностью совместим с известным составным документом Microsoft.
Скорость чтения составного документа в соответствии с вариантом осуществления настоящего изобретения в 4 раза выше скорости чтения составного документа Microsoft, а скорость записи нового составного документа примерно в 100 раз выше скорости записи составного документа Microsoft. Как видно из фиг.12-14, характеристики нового составного документа намного лучше характеристик составного документа Microsoft.
На фиг.12-14 показаны результаты сравнения временных затрат при использовании способа, предложенного в варианте осуществления настоящего изобретения, и способа, предусмотренного в известной технологии. На фиг.12 сравниваются временные затраты при использовании интерфейса составного документа Microsoft (применяемого в известной технологии) для открытия базы данных db1 и временные затраты при использовании интерфейса составного документа в соответствие с вариантом осуществления настоящего изобретения для открытия базы данных db2. На фиг.13 сравниваются временные затраты при использовании интерфейса составного документа Microsoft для аналогового чтения семи записей сообщений друзей в базе данных db1 и использовании интерфейса составного документа в соответствии с вариантом осуществления настоящего изобретения для аналогового чтения семи записей сообщений друзей в базе данных db2. На фиг.14 сравниваются временные затраты для аналоговой записи семи сообщений друзей при использовании интерфейса составного документа Microsoft и интерфейса составного документа в соответствии с вариантом осуществления настоящего изобретения.
Базы данных db составных документов, использованные в трех названных выше экспериментах, были созданы путем моделирования процесса генерации записей сообщений средств службы обмена мгновенными сообщениями: для создания данных составного документа объемом 600 МБ, названных базой данных db1, использовался интерфейс составного документа Microsoft, а для создания данных составного документа объемом 600 МБ, названных базой данных db2, использовался интерфейс составного документа в соответствии с вариантом осуществления настоящего изобретения.
Из приведенного выше описания примеров специалисты в данной области могут легко понять, что настоящее изобретение можно реализовать программно с использованием соответствующих широко распространенных аппаратных платформ или аппаратно. Основная часть технического решения настоящего изобретения или часть, вносящая вклад в развитие известной технологии, может быть реализована в виде программного продукта, хранящегося в машиночитаемой среде хранения (например, в ПЗУ, ОЗУ, на дискете или компакт-диске) и содержащего несколько кодов для выполнения компьютерным устройством (например, персональным компьютером, сервером или сетевым устройством) действий, предусмотренных в способе каждым из вариантов осуществления настоящего изобретения или некоторых их частей.
Описанные выше варианты осуществления не ограничивают область изобретения. Любые модификации, эквивалентные замены и улучшения, сделанные в рамках сущности и согласно принципам настоящего изобретения, подпадают под объем его охраны.