image
Предупреждение: Этот график сделан для скрипта второй части статьи за которую я ещё не брался. Поэтому не очень обращайте внимание на данные в нём. Графики для этой статьи в конце.


Информацию из этой статьи используйте на свой страх и риск. Мы будем стирать данные из файлов. Статья написана под операционную систему Windows и файловую систему NTFS. Также в статье много изображений.


Что такое разреженный файл


Разрежённый файл (англ. sparse file) — файл, в котором последовательности нулевых байтов[1] заменены на информацию об этих последовательностях (список дыр).

Дыра (англ. hole) — последовательность нулевых байт внутри файла, не записанная на диск. Информация о дырах (смещение от начала файла в байтах и количество байт) хранится в метаданных ФС.

На Geektimes также есть небольшая статья о них: "Разреженные файлы в NTFS"


Операционная система по умолчанию не создаёт разреженные файлы. Этот флаг можно установить файлу программно или при помощи утилиты.


Устанавливаем флаг при помощи утилиты:


fsutil sparse setflag <имя файла>

Программно (С++ Windows):


DeviceIoControl( m_hFile, FSCTL_SET_SPARSE, NULL, 0, NULL, 0, &dwOut, NULL )

Автоматически нулевые последовательности в файле не освободят место на диске и это также нужно делать программно или при помощи утилиты.


Затираем нулями часть файла помощи утилиты:


fsutil sparse setrange <имя файла> <позиция> <длинна>

Программно (С++ Windows):


FILE_ZERO_DATA_INFORMATION range;
range.FileOffset.QuadPart = start;
range.BeyondFinalZero.QuadPart = start + size;

DeviceIoControl( m_hFile, FSCTL_SET_ZERO_DATA, &range, sizeof(range), NULL, 0, &dwOut, NULL );

Простые файлы


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


Загружаемые файлы


  1. С флагом разреженного файл будет занимать столько сколько нужно загруженным данным. Это полезно когда в очереди на загрузку стоит много файлов и их полный общий объём может превышать доступный.
  2. По хешам частей можно определить части заполненные нулями и пометить их уже загруженными. Эти части не будут загружаться и занимать место на диске.


    Функция для поиска пустых кусочков в торренте (С++ Shareaza)

    BTInfo.cpp:


    BOOL CBTInfo::IsZeroBlock(uint32 nBlock) const
    {
    static const uint32 ZeroHash[22][5] = {
        // Hash: 897256B6709E1A4DA9DABA92B6BDE39CCFCCD8C1       Size: 16384
        { 0xB6567289, 0x4D1A9E70, 0x92BADAA9, 0x9CE3BDB6, 0xC1D8CCCF },
        // Hash: 5188431849B4613152FD7BDBA6A3FF0A4FD6424B       Size: 32768
        { 0x18438851, 0x3161B449, 0xDB7BFD52, 0x0AFFA3A6, 0x4B42D64F },
        // Hash: 1ADC95BEBE9EEA8C112D40CD04AB7A8D75C4F961       Size: 65536
        { 0xBE95DC1A, 0x8CEA9EBE, 0xCD402D11, 0x8D7AAB04, 0x61F9C475 },
        // Hash: 67DFD19F3EB3649D6F3F6631E44D0BD36B8D8D19       Size: 131072
        { 0x9FD1DF67, 0x9D64B33E, 0x31663F6F, 0xD30B4DE4, 0x198D8D6B },
        // Hash: 2E000FA7E85759C7F4C254D4D9C33EF481E459A7       Size: 262144
        { 0xA70F002E, 0xC75957E8, 0xD454C2F4, 0xF43EC3D9, 0xA759E481 },
        // Hash: 6A521E1D2A632C26E53B83D2CC4B0EDECFC1E68C       Size: 524288
        { 0x1D1E526A, 0x262C632A, 0xD2833BE5, 0xDE0E4BCC, 0x8CE6C1CF },
        // Hash: 3B71F43FF30F4B15B5CD85DD9E95EBC7E84EB5A3       Size: 1048576
        { 0x3FF4713B, 0x154B0FF3, 0xDD85CDB5, 0xC7EB959E, 0xA3B54EE8 },
        // Hash: 7D76D48D64D7AC5411D714A4BB83F37E3E5B8DF6       Size: 2097152
        { 0x8DD4767D, 0x54ACD764, 0xA414D711, 0x7EF383BB, 0xF68D5B3E },
        // Hash: 2BCCBD2F38F15C13EB7D5A89FD9D85F595E23BC3       Size: 4194304
        { 0x2FBDCC2B, 0x135CF138, 0x895A7DEB, 0xF5859DFD, 0xC33BE295 },
        // Hash: 5FDE1CCE603E6566D20DA811C9C8BCCCB044D4AE       Size: 8388608
        { 0xCE1CDE5F, 0x66653E60, 0x11A80DD2, 0xCCBCC8C9, 0xAED444B0 },
        // Hash: 3B4417FC421CEE30A9AD0FD9319220A8DAE32DA2       Size: 16777216
        { 0xFC17443B, 0x30EE1C42, 0xD90FADA9, 0xA8209231, 0xA22DE3DA },
        // Hash: 57B587E1BF2D09335BDAC6DB18902D43DFE76449       Size: 33554432
        { 0xE187B557, 0x33092DBF, 0xDBC6DA5B, 0x432D9018, 0x4964E7DF },
        // Hash: 44FAC4BEDDE4DF04B9572AC665D3AC2C5CD00C7D       Size: 67108864
        { 0xBEC4FA44, 0x04DFE4DD, 0xC62A57B9, 0x2CACD365, 0x7D0CD05C },
        // Hash: BA713B819C1202DCB0D178DF9D2B3222BA1BBA44       Size: 134217728
        { 0x813B71BA, 0xDC02129C, 0xDF78D1B0, 0x22322B9D, 0x44BA1BBA },
        // Hash: 7B91DBDC56C5781EDF6C8847B4AA6965566C5C75       Size: 268435456
        { 0xDCDB917B, 0x1E78C556, 0x47886CDF, 0x6569AAB4, 0x755C6C56 },
        // Hash: 5B088492C9F4778F409B7AE61477DEC124C99033       Size: 536870912
        { 0x9284085B, 0x8F77F4C9, 0xE67A9B40, 0xC1DE7714, 0x3390C924 },
        // Hash: 2A492F15396A6768BCBCA016993F4B4C8B0B5307       Size: 1073741824
        { 0x152F492A, 0x68676A39, 0x16A0BCBC, 0x4C4B3F99, 0x07530B8B },
        // Hash: 91D50642DD930E9542C39D36F0516D45F4E1AF0D       Size: 2147483648
        { 0x4206D591, 0x950E93DD, 0x369DC342, 0x456D51F0, 0x0DAFE1F4 },
        // Hash: 1BF99EE9F374E58E201E4DDA4F474E570EB77229       Size: 4294967296
        { 0xE99EF91B, 0x8EE574F3, 0xDA4D1E20, 0x574E474F, 0x2972B70E },
        // Hash: BCC8C0CA9E402EEE924A6046966D18B1F66EB577       Size: 8589934592
        { 0xCAC0C8BC, 0xEE2E409E, 0x46604A92, 0xB1186D96, 0x77B56EF6 },
        // Hash: DC44DD38511BD6D1233701D63C15B87D0BD9F3A5       Size: 17179869184
        { 0x38DD44DC, 0xD1D61B51, 0xD6013723, 0x7DB8153C, 0xA5F3D90B },
        // Hash: 7FFB233B3B2806328171FB8B5C209F48DC095B72       Size: 34359738368
        { 0x3B23FB7F, 0x3206283B, 0x8BFB7181, 0x489F205C, 0x725B09DC }
    };
    
    int i = 0;
    for(; m_nBlockSize > ( (uint64) 16384 << i ); i++)
        if ( i > 21 )
            return FALSE;
    
    return memcmp( &m_pBlockBTH[ nBlock ], ZeroHash[ i ], sizeof( ZeroHash[ i ] ) ) == 0;
    }



Недостатки:


Файл фрагментируется. Это происходит и с обычными файлами но с разреженными это более выражено. Файл загружается в случайном порядке и место под данные выделяется по мере необходимости. Кусочки файла разбрасываются по диску.


Частичное стирание ненужных файлов на раздаче.


Разрежённые файлы позволяют постепенно высвобождать место под другие данные. Заданный командой fsutil sparse setrange участок освобождается и читаются далее из него только нули.


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


Польза:


  1. Тем самым мы можем остаться на раздаче при этом освободив достаточно места под загрузку нового торрента.
  2. Оставшись на раздаче мы не увеличиваем нагрузку на другие источники.
  3. Чем больше источников раздают тем выше скорость загрузки.

Пример


Скриншот qBittorent


У нас есть файл "linux.iso". Его размер 1.4 гигабайта. Для новой загрузки нам не хватает 1 гигабайта свободного пространства на диске.


Используем fsutil sparse напрямую (не правильно!)


fsutil sparse setflag linux.iso
fsutil sparse setrange linux.iso 0 1073741824

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


Пишем простой скрипт выбора случайной позиции


Поскольку используются большие числа и для удобства ведём вычисления в JavaScript


sparse_light.js


// Нам нужны два аргумента
if (WScript.Arguments.Length == 2)
{
    // Первый аргумент размер файла
    var file_size = parseInt( WScript.Arguments.Item(0) );

    // Второй аргумент размер части файла которую стираем
    var sparse_size = parseInt( WScript.Arguments.Item(1) ); 

    if ( file_size > 0 && sparse_size > 0 && sparse_size < file_size )
    {
        // Если стираемая часть меньше половины файла то
        if ( file_size / 2 > sparse_size )
            // Вычисляем позицию с которой будем стирать файл и возврашаем размер стираемой части без изменений
            WScript.Echo( Math.round( ( file_size - sparse_size ) * Math.random() ), sparse_size );
        else 
        {
            // Здесть мы стираем большую часть файла поэтому вычисляем позицию для оставшегося кусочка данных
            var data_size = file_size - sparse_size;
            var data_pos = Math.round( ( file_size - data_size ) * Math.random() );

            // Возвращаем стираемый отрезок до данных
            if ( data_pos > 0 )
                WScript.Echo( 0, data_pos );

            var sparse_pos = data_pos + data_size;
            // Возвращаем стираемый отрезок после данных
            if ( sparse_pos < file_size )
                WScript.Echo( sparse_pos, file_size - sparse_pos );
        }
    }
}

Получение размера файла и работу с fsutil sparse оставим в командном файле.


sparse_light.cmd


@rem %1 Первый аргумент это полный путь к файлу
@rem %2 Второй аргумент часть которую мы стираем

@setlocal

@rem Предупреждаем перед тем как затирать части файла
@echo This script will erase some of the data (%2 bytes) from the file: %1
@set /P AREYOUSURE=Are you sure (Y/[N])?
@if /I "%AREYOUSURE%" NEQ "Y" goto END

@rem Устанавливаем флаг разрежённого файла
fsutil sparse setflag %1

@rem Циклом читаем позицию и размер участка которые нам вернёт sparse_light.js и прореживаем эту часть файла
for /f "tokens=1,2" %%i in ('cscript //nologo "%~dp0sparse_light.js" %~z1 %2') do (
 fsutil sparse setrange %1 %%i %%j
)

:END
@endlocal

Вызываем:


sparse_random.cmd linux.iso 1073741824

Этот скрипт затрёт один или два случайных участка файла. Скрипт подходит для затирания одиночного файла.


Пример использования скрипта с qBittorent (много скриншотов)


  1. Открываем qBittorent
    Скриншот qBittorent
  2. Выбираем нужный торрент (в данном случае linux.iso). Вызываем контекстное меню и нажимаем "Приостановить".
    Скриншот qBittorent. Открыто контекстное меню и выбран пункт Приостановить
  3. Прореживаем файл при помощи скрипта:
    sparse_light.cmd G:\linux\linux.iso 500000000
    Скриншот окна cmd.exe в котором результат выполнения скрипта
  4. Убеждаемся что освободили заданное количество места на диске. Открываем свойства файла и сравниваем "Size" и "Size on disk".
    Окно свойств файла
  5. В qBittorent переключаемся на вкладку содержимое
    Скриншот qBittorent. Вкладка содержимое. Стоит галочка рядом с файлом
  6. И снимаем галочку рядом с файлом чтобы он после проверки не начал загружаться заново
    Скриншот qBittorent. Вкладка содержимое. Галочка рядом с файлом снята
  7. Правой кнопкой мыши на раздаче вызываем контекстное меню и нажимаем пункт "Проверить принудительно"
    Скриншот qBittorent. Открыто контекстное меню. Выбран пункт Проверить принудительно
  8. Да мы уверены, что хотим выполнить повторную проверку выбранных торрентов.
    Скриншот qBittorent. Окно подтверждения повторной проверки.
  9. После окончания проверки. Правой кнопкой мыши на раздаче вызываем контекстное меню и нажимаем пункт "Возобновить"
    Скриншот qBittorent. Открыто контекстное меню. Выбран пункт Возобновить
  10. Таким образом мы остались на раздаче и высвободили немного места на диске
    Скриншот qBittorent. Показана отсутствующая часть раздачи. Статус раздачи Раздаётся
  11. Правой кнопкой мыши на раздаче вызываем контекстное меню и нажимаем пункт "Переместить" (Надо бы это делать первым пунктом но я сегодня только об этом подумал)
    Скриншот qBittorent. Открыто контекстное меню. Выбран пункт Переместить
  12. Подбираем имя директории так чтобы было понятно что файлы в ней не пригодны к использованию.
    Скриншот окна выбора директории. Выбрана директория !sparse_files

Считаем статистику в SVG


image


Файл разделён на 100 блоков. На графиках учитываются только полные блоки. Каждая строка в сетке это одна эмуляция роя. Ниже сетки с веху в низ опускаются графики доступности.


  1. В синем графике столбик под каждым блоком показывает количество циклов в которых был он полным.
  2. В тёмно синем(на самом деле полупрозрачном сером) графике показывается слева(0%) на право(100%) процент доступных данных и сверху в низ количество циклов к которых этот процент был доступен.

Для тех кто хочет поиграться с эмуляцией: https://ivan386.github.io/sparse_light/emulator.svg


Управление с клавиатуры:
P/З — пауза
+/= — добавить один источник
-/_ — убрать один источник


Управление мышью:
Кликая мышкой по сетке можно выбрать процент который будет стёрт у всех источников. Чем правее тем больше стирается.


Разбираем графики


  1. 5 источников стёрли 81% процент файла с разных позиций. При этом осталось доступным 64% в большинстве циклов. Блоки по краям при этом практически всегда остаются недоступны.
    image
  2. 5 источников стёрли 49% процентов файла с разных позиций. Осталось доступно 88% файла.
    Поскольку высвобождается меньше половины файла скрипт выбирает позицию для стирания. Таким образом в середине файла блоки становятся менее доступны чем по краям.
    image
  3. 5 источников стёрли 52% процента файла с разных позиций. Осталось доступно 86% файла.
    Выбрано для стирания больше половины файла. Скрипт в данном случае выбирает позицию для данных и стирает до и после этого кусочка.
    image
  4. 5 источников стёрли 40% процентов файла с разных позиций. Осталось доступно 100% файла. Тут мы видим что при стирании до 40% файла при 5 источниках мы наиболее вероятно получим 100% доступность файла.
    image

Графики 2 и 3 компенсируют друг друга.


Заключение


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


Источники


  1. Разрежённый файл
  2. Разреженные файлы в NTFS
  3. FSCTL_SET_SPARSE control code
  4. FSCTL_SET_ZERO_DATA control code
  5. FILE_ZERO_DATA_INFORMATION structure
  6. How can I make an “are you sure” prompt in a Windows batchfile?
  7. How to set environment variables in vbs that can be read in calling batch script

Комментарии (17)


  1. TrllServ
    26.02.2018 11:13

    Мы можем стереть часть и раздавать дальше
    того чего у нас нет?
    Само по себе описанное — интересно. Но каково практическое применение?
    Приходит на ум только на крутка раздач или доступности файла, но на трекерах счетчики остались для красоты, и былой функционал не выполняют.
    Наоборот, теперь ценится наличие всех частей файла для резкого контента.


    1. ivan386 Автор
      26.02.2018 11:28

      того чего у нас нет?
      Остальная часть данных(не стёртая) будет раздаваться дальше.

      Но каково практическое применение?

      Поддержание раздачи. Естественно это нельзя делать создателю раздачи. На раздаче обязательно должны быть полные источники. В дополнение к ним частичные источники. За счёт большего количества источников будет больше скорость загрузки.


      Такой метод поддержания раздачи становится более актуальном при росте размера раздач и ограниченном месте на диске.


      Например BDRip может занимать до 25гигабайт при этом 20 из них это один цельный файл. Это проблема когда SSD всего на 60ГБ.


      Так мы можем высвободить пару гигов и раздавать дальше.


  1. vesper-bot
    26.02.2018 11:25

    Главное потом не забыть, что файл-то у тебя с дыркой, когда затеешь его использовать :) По мне, в этом случае правильно именно перепроверить файл/торрент, поставить состояние do not download и раздавать оставшиеся данные. Тогда твой клиент будет честно рапортовать, что у него есть 31% файла вместо ста процентов, и с тебя не будут тянуть неверные нули в сеть, забивая полосу и потом сбрасывая как ненадежный источник.


    1. ivan386 Автор
      26.02.2018 11:32

      В пример использования скрипта с qBittorent я так и предлагаю делать. Прореженные раздачи переносятся в папку в которой будет понятно что это не полные файлы.


  1. aamonster
    26.02.2018 11:27
    +1

    С ходу вопрос: а торрент-клиент отследит, что вы так поступили с файлом? Или с точки зрения трекера вы останетесь seed-ом, и только когда у вас попросят фрагмент файла — дадите отлуп ("ну нет его у меня!") или, того хуже, перешлёте другому клиенту пачку нулей, от которой он посчитает хэш, отбросит и начнёт качать заново из другого источника?


    1. aamonster
      26.02.2018 11:39

      Упс, перечитал пост, увидел ответ на свой вопрос. Т.е. только руками, только хардкор… Нет, такой хоккей нам не нужен. Лучше стереть одну из раздач целиком (посмотрев, по какой есть больше сидов).


      1. ivan386 Автор
        26.02.2018 11:46

        Ну я надеюсь что после моего поста программисты клиентов осознают нужность данной фишки и реализуют интерфейс на пару кликов в клиенте.


        Ещё можно доработать скрипт. Научить его автоматически работать с клиентом. В статье Proof of concept.


        1. TrllServ
          26.02.2018 12:12

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

          И решить эту проблему можно будет только дополнительным протоколом между сидами, которые будут договариваться, какие части «нулить», что б при этом файл все еще можно было скачать.

          PS: Что-то подобное я где-то уже встречал. Вот только где?


          1. ivan386 Автор
            26.02.2018 12:18

            Можно не договариваться. Клиент видит доступность частей в рое и может стирать только самые распространённые части.


            1. TrllServ
              26.02.2018 14:24

              Нельзя, потому, что то что сейчас самое распространенное может пустовать уже через несколько часов. Потому, что это не сервера, а пользовательские устройства которые в любой момент могут выключить.
              Простой пример время 10-18 доступность одна — много рабочих машин, закончилась работа, тысячи машин выключены и фрагменты недоступны.


              1. ivan386 Автор
                26.02.2018 14:38

                Тут выбор между полностью уйти с раздачи удалив торрент или остаться на ней не полным источником. С этой точки зрения уход других источников не имеет значения. Поддерживаем как можем.


                Есть другая проблема. Рой поддельных пиров при строгом алгоритме может заставить остальных проредить одни и теже части. Поэтому прореживание должно быть с примесью рандома.


                1. TrllServ
                  26.02.2018 14:41

                  Именно поэтому, я написал выше, что нужен отдельный протокол, что б рой недосидов, точно определился, чем кто и что удалит. И при этом учтет свой среднестатистический онлайн.
                  А не просто глянет чего больше и удалит у себя.


                  1. ivan386 Автор
                    26.02.2018 14:46

                    Так поддельные пиры тоже будут участвовать в этом и смогут стереть всё. Нельзя доверять никому. Рандом наше всё))


                    1. TrllServ
                      26.02.2018 14:49

                      это всё относительно не сложно решаемо. Был бы в этом смысл.
                      Мы уже пришли к разработке протокола? :)


                      1. ivan386 Автор
                        26.02.2018 15:04

                        Я не против. Разрабатывайте.


                        С моей стороны единственное что можно добавить в протоколе BitTorrent это сообщение lost которое будет сообщать что у пира больше нет этого куска или участка. Тогда не прийдётся переподключаться после перепроверки.


                        Можно сделать отложенное стирание. Клиент помечает выбранные куски как удалённые и наблюдает некоторое время за роем. Если выбранные куски не стали редкими то стирает их окончательно. Иначе выбирает другие заместо редких и повторяет процедуру для них.


                        1. rkfg
                          27.02.2018 00:55

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


    1. ivan386 Автор
      26.02.2018 11:41

      1. В qBittorent переключаемся на вкладку содержимое
        Скриншот qBittorent. Вкладка содержимое. Стоит галочка рядом с файлом
      2. И снимаем галочку рядом с файлом чтобы он после проверки не начал загружаться заново
        Скриншот qBittorent. Вкладка содержимое. Галочка рядом с файлом снята
      3. Правой кнопкой мыши на раздаче вызываем контекстное меню и нажимаем пункт "Проверить принудительно"
        Скриншот qBittorent. Открыто контекстное меню. Выбран пункт Проверить принудительно
        ...
      4. Таким образом мы остались на раздаче и высвободили немного места на диске
        Скриншот qBittorent. Показана отсутствующая часть раздачи. Статус раздачи Раздаётся

      Пришлось убрать спойлер.