мимоходом

[avva]

Интересно, а почему современные операционные системы не предоставляют возможности писать внутрь файла, раздвигая его? Т.е. запись в режиме insert, а не overwrite?

Полагаю, что все или почти все современные файловые системы могут поддерживать эту операцию с такой же лёгкостью, как и добавление данных в конец файла.

Или это не слишком часто нужно, и можно просто рассчитывать на то, что программа, которой это нужно, будет переписывать весь файл заново, как и происходит на практике?

Comments

[tangodancer.livejournal.com]

я тебя правильно понял?????
Как ето не позволяют?
На любом языке такое можно написать

[avva.livejournal.com]

Как?

[tangodancer.livejournal.com]

zapomni vse ot nachala tvoego kursora do konca faila-i vpered.eto zhe prosto

[sobaker.livejournal.com]

Операциями перезаписи. Раздвинуть нельзя на уровне FS нельзя.

[nine_k]

Нетрудно вообразить FS, которая умела бы такую операци. эффективно поддерживать. Умеют же FS поддерживать файлы с "дырками".

Но кому файлы с дырками нужны, более-менее понятно; кому нужен эффективный append, тоже понятно. Кому нужен insert? Не знаю :)

[sabalin.livejournal.com]

Dynamic FS

Это дорого.

[potan.livejournal.com]

Если сдвиг идет не на целое счисло блоков - то все-равно придется переписывать, пусть и в нутри драйвера. Даже если на целое - будет увеличено количество фрагментов, что тоже не есть хорошо.

Re: Это дорого.

[avva.livejournal.com]

Мне казалось, что современные файловые системы уже все умеют более эффективно использовать блоки. Например, использовать только часть блока для содержимого файла, а потом прыгать на следующий блок (если вообще организовывать дисковое пространство, разбивая его на блоки). Например, я знаю, что reiserfs умеет в один "блок" писать много маленьких файлов - почему же тогда нельзя в середине файла использовать часть блока, а не целый?

Хотя тогда, наверное, seek делать сложнее будет, и нужно добавлять больше информации куда-нибудь в управляющие структуры... да, надо подумать.

Re: Это дорого.

[potan.livejournal.com]

По моему недозаполненное пространство в блоке reiserfs использует только если маленький файл помещается туда целиком. Но иметь в середине файла невыровненную на границу блока цепочку точно не позволяет.

Кстати, аналогичкая задача - откусовать кусочки от начала файла. Актуальна например при организации очереди. Один мой знакомый такое под DOS делал :-)).

Re: с такой же лёгкостью

[alll]

Насчет легкости - это сильно сказано. Все-таки файловые системы так или иначе оперируют блоками, а не отдельными байтами. Так что получится либо морока несусветная (одна "сборка мусора" чего будет стоить), либо то же самый overwrite, только спрятаный от программиста и оттого труднопредсказуемый.

Вот добавление в начало файла - другое дело.

[aeriman.livejournal.com]

Операционные системы типа *nix позволяют. Для этого даже примитивы в stdlib есть. Дело в том, что это ОЧЕНЬ медленная операция, всё равно связанная с overwrite.

[avva.livejournal.com]

Какие примитивы?

Стыдно признаться...

[dimrub.livejournal.com]

Я, если честно, на Longhorn еще совсем не смотрел. Может, там такое будет?

[aamonster.livejournal.com]

Потому что современные файловые системы на это не рассчитаны: файл хранится в виде блоков (кластеров) фиксированного размера, и если вставляется не целое число кластеров - придется переписывать весь конец файла...

В принципе, можно создать FS c возможностью вставки (с файлами, состоящими из записей различной длины). ЕМНИП, такая "файловая система" реализована в PalmOS.

Кстати, в стародавние времена, когда компьютеры были большие, а диски и оперативка - маленькие, существовало изящное решение этой задачки для частного случая текстового редактора (редактирующего текст много больше доступной RAM): начало текста (до текущей позиции) держалось в одном файле (в нормальном порядке), а хвост (от текущей позиции до конца текста) складывался в отдельный файл в обратном порядке. И при передвижении по файлу часть данных перекладывалась из одного файла в другой (из хвоста файла в хвост).

[lazha.livejournal.com]

Ого, мне идея нравится.
Можно флаг файлу в INode давать, который будет говорить можноего инсерт или нет.

[lazha.livejournal.com]

Кстати - append - получается как частный случай insert'a.

[alll]

А если нельзя, то что?
В смысле - когда этот пресловутый insert пойдет в ход в промышленых количествах, чем этот флаг будет отличаться от read-only прав доступа? :)

[pargentum.livejournal.com]

OS/390 - z/OS вам достаточно современная система? Там есть индексно-последовательные файлы, которые позволяют делать вставку (в том числе, IIRC, записей переменной длины) в любое желаемое место. :)

А на уровне реализации - это несколько отличается от дырок в файле, дырка не приводит к изменению логических смещений данных, которые находятся после дырки. А ваша операция требует именно такого изменения смещений. Как это сделать на величину, кратную размеру блока - понятно, но не очень интересно. Сделать это на произвольную величину - сложно и, наверное, может убить производительность.

А в базах данных обычно, насколько я знаю, делают те же индексно-последовательные файлы, только не на уровне ОС, а на уровне приложения.

[grur.livejournal.com]

Операция Insert имеет логический смысл только для файлов, у которых обычный режим доступа - последовательный. Для того чтобы был еще и экономический смысл, нужно чтобы файлы были сравнительно большими. Сходу приходит в голову разве что редактирование фильмов в формате DivX.

[avva.livejournal.com]

Да, но одно это уже неплохо ;)

Не согласен

[kroman139.livejournal.com]

Не согласен! Можно уточнить - не просто "обычный режим доступа последовательный", но "обычный режим доступа по чтению последовательный".

Операция "insert" является очень удобной для постоянного сохранения некой структуры на диск.

Например, мы хотим сохранять какой список при вставке новых элементов. Было бы очень удобно, чтобы эти элементы в файле лежали последовательно.

concurrent access

[vzaliva.livejournal.com]

Потому что обычно системы разрешают чтобы файл может быть открыт
более чем одним процессом, и такая операция инвалидирует смещения
других указателей чтения/записи. В двух словах API backward compatibility.

Дорого это...

[kroman139.livejournal.com]

Это слишком, слишком дорого.

В настоящее время файлы обычно лежат в виде последовательности блоков, отдельно хранится длина файла (дабы использовать только часть последнего блока, но не весь целиком).

Если же разрешить "вставку" в куда-то-в-файле, то появляется вопросы:

а) Как это сделать удобно?
б) Как это сделать быстро?

Вариант с копированием остатка файла и всем таким успешно реализуется в пользовательском приложении, а посему нет особого смысла реализовывать его в ОС.

Любой другой вариант - сделать своеобразные "дыры" в файле, хранить некий двусвязный список областей, хранить для каждого блока файла размер байт, которые в нем используются - слишком дорогие по времени.

1) "Дыры"

Примечание: описываемые "дыры" отличаются от "sparse"-файлов. Я говорю именно о "дырах", которые прячет ОС и никогда не показывает наверх.

Непонятно, где хранить "дыры", какие у них должны быть размеры и как ими управлять.

2) Список

Список опять же сказывается на производительности.

3) "Подблоки"

Выглядит интересно, но не очень. Потому что могут быть большие (очень большие) потери в остатках блоков.

********

Любой из этих примеров утыкается в производительность - при вставке блока надо будет перелопатить кучу информации и что-то где-то обновить.

Опять же, любая реализация запинается очень простыми сценариями:

1) Сценарий 1

Представим себе простенький файл на 1 Мб.

Мы начинаем вставлять по 1 Кб в цент файла. Причем каждый раз вставляем по смещению .5 Мб

2) Сценарий 2

Все тот же файл на 1 Мб.

Мы начинаем делать "insert" с конца файла в начало.

3) Сценарий 3

Файл 1 Мб.

Мы вставляем в центр файла (со смещения 0.5 Мб) блок размером 1 байт, 2 байта, 3 байта, 4 байта и так далее.

4) Сценарий 4

Наш любимый файл на 1 Мб.

Мы проигрываем сценарий 3, но после каждой вставки переписываем вставленный блок плюс по 1 Кб до и после оного.

***************

Сценарии можно продолжать и продолжать, для подавляющего большинства реализаций можно придумать свой сценарий "упадения".

Как только мы придумываем супер-пупер-алгоритм, сразу же вспоминаем, что файлы нынче идут не 1 Мб, а по 200-300 Мб в среднем, плюс видео и что-нибудь рабочее по 1 Гб. Если наш алгоритм все еще справляется с такими объемами, то запускаем алгоритм на файловом сервере.

В итоге приходим к выводу, что самое оптимальное - придумать свой специфичный алгоритм и реализовать его в своем же приложении.

Только почему-то кажется мне, что исследования на эту тему уже проводились и даже что-нибудь придумали.

Это все из-за "unix way"...

[sysprg.livejournal.com]

Это очередная дурь Unix, в которой смешались гениальность в одних решениях и удивительная, редкостная тупизна в других (хотя сейчас принято считать, что Unix - это нечто во всех смыслах самое лучшее). Файл в Unix не имеет никакой внутренней организации. Например, как Вы наверняка знаете, текстовый файл – это последовательность байтов с символом-разделителем CR (или вообще CR/LF, а так же все прочие мыслимые сочетания). В результате операция вставки на логическом уровне принципиально требует перемещения ВСЕГО содержимого файла за местом вставки. Найти строку по номеру нельзя без пролистывания всего файла до этой строки. Даже выяснить, сколько именно строк в файле без ПОЛНОГО прочтения всего файла (!) невозможно! Чтобы показать последний экран с содержимым файла во viewer требуется суперхитрозапутанный код, читающий его с конца и ищущий CR/LF в обратном направлении. Все криво просто до жути... Так же и с бинарными файлами - они ведь тоже просто поток байтов. В результате вставка - это на логическом уровне сдвиг всего содержимого файла начиная с места вставки. На физическом уровне, ТЕОРЕТИЧЕСКИ, это можно было бы оптимизировать - но ни одна современная FS для Unix и Windows не умеет такого делать. Да в общем-то не мудрено - без понятия "записи" подобные манипуляции будут приводить к излишней фрагментации. Да что там говорить - через API этим системам нельзя даже ЗАРАНЕЕ сообщить размер файла при его создании, чтобы они сразу выделили под него continuous место на диске.
Замечу, что ВСЕХ этих проблем не было даже в OS/360 1968 (!) года выпуска и во всех последующих OS для IBM Manframe.

Re: Это все из-за "unix way"...

[bish0nen.livejournal.com]

Это - не юниксовая дурь, а один из подходов к работе с файлами со своими недостатками и преимуществами. В RSX-11M (ну и в VMS до кучи из легко доступных ОС) при открытии файла задавался режим доступа к нему - последовательный, произвольный, индексный файл или нет итп, в айбиэмовских мейнфреймовых ОС тоже беспроблемно, только там понятие файловой системы есть разве что в VM/SP, а у остальных - тома, монтируемые в них библиотеки и прочая ботва, т.е. несколько отличная от юниксовой парадигма. Это уж не говоря о том, что MVS & Co - это ОС ориентированные на обработку пакетных заданий в первую очередь, вещь исключительно сомнительной полезности для интерактивной работы.

Собственно, мне как раз неюниксовый подход и не нравился - замучаешься открывать файл: операция простая, а чихать надо много и часто для получения конечного результата - создай контрольный блок, позови пятнадцать сисколлов, потом, пожалуй, и файл давайте откроем. Мне это до сих пор кажется муторным. Практическая польза тоже спорна - файловая система должна поддерживать, VMM должна поддерживать, реализация относительно сложная и рассадник багов, а реально нужно только полутора приложениям, тем более что та же RDBMS всё равно потребует себе выделенного тома, и этот том внутри перекроит как ей надо и будет работать с ним по-своему.