Сжатие данных при передаче от браузера к серверу

  • Tutorial
Обрабатываете много данных в браузере?
Хотите отправлять их обратно на сервер?
Да так, чтобы отправлялось побыстрее и помещалось в один http запрос?

В статье я покажу как мы решили эту задачу в новом проекте, используя сжатие и современные возможности javascript.



Описание задачи


Хабраюзер aneto пожаловался мне, что Яндекс.Директ плохо обрабатывает пересечения ключевиков между собой. А тем временем задача актуальная и практически нерешаемая вручную. Так мы и сделали небольшой сервис, решающий эту проблему.

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

В ходе разработки у нас появилось две проблемы:
  1. При медленном соединении данные передаются слишком долго.
  2. Часто данные не умещаются в один post запрос из-за ограничений nginx/apache/php/etc.


Решение


Есть множество способов решения. В нашем случае прокатил вариант, основанный на современных стандартах: Typed Arrays, Workers, XHR 2. В двух словах: мы сжимаем данные и отправляем их на сервер в двоичном виде. Эти простые действия позволили нам сократить размер передаваемых данных более чем в 2 раза.

Рассмотрим алгоритм пошагово.

Шаг 0: Исходные данные

Для примера я сгенерировал массив, содержащий различные данные о множестве пользователей. В примере он будет загружаться через JSONP и отправляться обратно на сервер.

Код загрузки и функция отправки данных
<script>
    function setDemoData(data) {
        window.initialData = data;
    }
    function send(data) {
        var http = new XMLHttpRequest();
	http.open('POST', window.location.href, true);
	http.setRequestHeader('X-Requested-With', 'XMLHttpRequest');
	http.onreadystatechange = function() {
		if (http.readyState == 4) {
			if (http.status === 200) {
				// xhr success
			}
			else {
				// xhr error;
			}
		}
	};
	http.send(data);
    }
</script>
<script src="http://nodge.ru/habr/demoData.js"></script>

Попробуем отправить данные как есть и посмотрим в дебагер:

var data = JSON.stringify(initialData);
send(data);



При простой передаче объем запроса — 9402 Кб. Много, будем сокращать.

Шаг 1: Сжатие данных

В javascript нет встроенных функций для сжатия данных. Для сжатия можно использовать любой удобный для вас алгоритм: LZW, Deflate, LZMA и другие. Выбор будет зависеть, в основном, от наличия библиотек под клиент и сервер. Соответствующие javascript библиотеки легко находятся на гитхабе: раз, два, три.

Мы пробовали использовать все три варианта, но с PHP удалось подружить только LZW. Это очень простой алгоритм. В примере воспользуемся такой реализацией:

Функция сжатия по LZW
var LZW = {
	compress: function(uncompressed) {
		"use strict";

		var i, l,
			dictionary = {},
			w = '', k, wk,
			result = [],
			dictSize = 256;

		// initial dictionary
		for (i = 0; i < dictSize; i++) {
			dictionary[String.fromCharCode(i)] = i;
		}

		for (i = 0, l = uncompressed.length; i < l; i++) {
			k = uncompressed.charAt(i);
			wk = w + k;
			if (dictionary.hasOwnProperty(wk)) {
				w = wk;
			}
			else {
				result.push(dictionary[w]);
				dictionary[wk] = dictSize++;
				w = k;
			}
		}

		if (w !== '') {
			result.push(dictionary[w]);
		}

		result.dictionarySize = dictSize;
		return result;
	}
};

Так как LZW рассчитан на работу с ASCII, предварительно экранируем unicode символы. Библиотека взята здесь.
Итак, сжимаем данные и отправляем на сервер:

var data = JSON.stringify(initialData);
data = stringEscape(data);
data = LZW.compress(data);
send(data.join('|'));

Объем запроса — 6079 Кб (сжатие 65%), сэкономили 3323 Кб. Более сложный алгоритм сжатия покажет лучшие результаты, но мы идем к следующему шагу.

Шаг 2: Перевод в двоичные данные

Так как после сжатия по LZW мы получаем массив чисел, то совершенно неэффективно передавать его в качестве строки. Намного эффективнее передать его как двоичные данные.
Для этого мы можем использовать Typed Arrays:


 // используем 16-битный или 32-битный массив в зависимости от объема данных
var type = data.dictionarySize > 65535 ? 'Uint32Array' : 'Uint16Array',
    count = data.length,
    buffer = new ArrayBuffer((count+2) * window[type].BYTES_PER_ELEMENT), 
    // по первому байту будем определять тип массива
    bufferBase = new Uint8Array(buffer, 0, 1),
    // для оптимизации распаковки на сервере передадим итоговый размер словаря LZW
    bufferDictSize = new window[type](buffer, window[type].BYTES_PER_ELEMENT, 1), 
    bufferData = new window[type](buffer, window[type].BYTES_PER_ELEMENT*2, count);

bufferBase[0] = type === 'Uint32Array' ? 32 : 16; // записываем тип массива
bufferDictSize[0] = data.dictionarySize; // записываем размер словаря LZW
bufferData.set(data); // записываем данные

data = new Blob([buffer]); // оборачиваем ArrayBuffer в Blob для передачи по XHR
send(data); 

Объем запроса — 3686 Кб (сжатие 39%), сэкономили 6079 Кб. Теперь размер запроса уменьшился более чем в два раза, обе описанные проблемы решены.

Шаг 3: Обработка на сервере.

Пришедшие на сервер данные теперь необходимо распаковать перед обработкой. Естественно, нужно использовать тот же алгоритм что и на клиенте. Вот пример как это можно сделать на php:

Пример обработки на PHP
<?php 
$data = readBinaryData(file_get_contents('php://input'));
$data = lzw_decompress($data);
$data = unicode_decode($data);
$data = json_decode($data, true);

function readBinaryData($buffer) {
    $bufferType = unpack('C', $buffer); // первый байт - тип массива
    if ($bufferType[1] === 16) {
        $dataSize = 2;
        $unpackModifier = 'v';
    }
    else {
        $dataSize = 4;
        $unpackModifier = 'V';
    }
    $buffer = substr($buffer, $dataSize); // remove type from buffer
    $data = new SplFixedArray(strlen($buffer)/$dataSize);
    $stepCount = 2500; // распаковываем частями по 2500 элементов
    for ($i=0, $l=$data->getSize(); $i<$l; $i+=$stepCount) {
        if ($i + $stepCount < $l) {
            $bytesCount = $stepCount * $dataSize;
            $currentBuffer = substr($buffer, 0, $bytesCount);
            $buffer = substr($buffer, $bytesCount);
        }
        else {
            $currentBuffer = $buffer;
            $buffer = '';
        }
        $dataPart = unpack($unpackModifier.'*', $currentBuffer);
        $p = $i;
        foreach ($dataPart as $item) {
            $data[$p] = $item;
            $p++;
        }
    }
    return $data;
}

function lzw_decompress($compressed) {
    $dictSize = 256;
    // первый элемент - размер словаря
    $dictionary = new SplFixedArray($compressed[0]);
    for ($i = 0; $i < $dictSize; $i++) {
        $dictionary[$i] = chr($i);
    }
    $i = 1;
    $w = chr($compressed[$i++]);
    $result = $w;
    for ($l = count($compressed); $i < $l; $i++) {
        $entry = '';
        $k = $compressed[$i];
        if (isset($dictionary[$k])) {
            $entry = $dictionary[$k];
        }
        else {
            if ($k === $dictSize) {
                $entry = $w . $w[0];
            }
            else {
                return null;
            }
        }
        $result .= $entry;
        $dictionary[$dictSize++] = $w .$entry[0];
        $w = $entry;
    }
    return $result;
}

function replace_unicode_escape_sequence($match) {
    return mb_convert_encoding(pack('H*', $match[1]), 'UTF-8', 'UCS-2BE');
}
 
function unicode_decode($str) {
    return preg_replace_callback('/\\\\u([0-9a-f]{4})/i', 'replace_unicode_escape_sequence', $str);
}

Для других языков, думаю, все так же просто.

Шаг 4: Workers

Так как приведенным выше кодом сжимаются достаточно объемные данные, то страница будет подвисать на время сжатия. Довольно неприятный эффект. Чтобы от него избавиться создадим поток, в котором будем производить все вычисления. В javascript для этого есть Workers. Как использовать Workers можно посмотреть в полном примере ниже или в документации.

Шаг 5: Поддержка браузерами

Очевидно, что приведенный выше javascript код не будет работать в IE6 =)
Для работы нам необходимы Typed Arrays, XHR 2 и Workers.
Список поддерживаемых браузеров: IE10+, Firefox 21+, Chrome 26+, Safari 5.1+, Opera 15+, IOS 5+, Android 4.0+ (без Workers).

Для проверки можно использовать Modernizr, либо примерно такой код:
Определение поддержки необходимых стандартов
var compressionSupported = (function() {
        var check = [
                'Worker',
                'Uint16Array', 'Uint32Array', 'ArrayBuffer', // Typed Arrays
                'Blob', 'FormData' // xhr2
        ];

        var supported = true;
        for (var i = 0, l = check.length; i<l; i++) {
                if (!(check[i] in window)) {
                        supported = false;
                        break;
                }
        }

        return supported;
})();

Примеры


Код из статьи опубликован на JS Bin: страница, worker. Открываете страницу, открываете инструменты разработчика и смотрите на размер трех post запросов.

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

Заключение


Конечно, данный метод подойдет не для всех случаев, но он имеет право на жизнь. Иногда проще/разумнее вместо сжатия сделать несколько запросов. А может у вас изначально числовые данные, то не нужно переводить их в строку и сжимать — достаточно использовать Typed Arrays.

Резюме:
  • Можно использовать сжатие не только server→client, но и client→server.
  • XHR 2 и Typed Arrays позволяют существенно уменьшить объем передаваемых данных.
  • Использование Workers позволит не блокировать взаимодействие пользователя со страницей.
  • И, конечно, не передавайте излишние данные без необходимости.


С удовольствием отвечу на вопросы и приму улучшения для кода. Ошибки и опечатки проверил, но на всякий случай — пишите в личные сообщения. Всем добра.

UPDATE 1:
Отдельно стоит сказать про изображения. Большинство форматов (jpeg, png, gif) уже сжаты, поэтому сжимать их повторно нет смысла. Изображения нужно передавать как бинарные данные, а не в строковом виде (base64). Я сделал небольшой пример для canvas показывающий преобразование base64 в Blob.

UPDATE 2:
Если используете или планируете использовать SSL, то прочитайте эту статью. В SSL уже предусмотрено двухстороннее сжатие запросов.

UPDATE 3:
Заменил base64 на экранирование unicode символов. Получилось намного эффективнее. Спасибо consumer, seriyPS и TolTol.
Поделиться публикацией

Комментарии 37

    0
    Есть ли смысл сжимать вышеописанными способами, если от браузера на сервер передаются изображения?
      +5
      Jpg, Gif, PNG уже же сжаты
        +2
        По идее, нет. Большинство изображений и так пожаты.
          +2
          Имеет смысл передавать в бинарном виде, а не в виде Base64 строки. А вот пережимать там уже нечего будет.
            +1
            Как верно ответил Fesor, нужно передавать как бинарные данные. Вот небольшой пример для canvas.
              0
              Если вы пытаетесь несколько изображений передать, то сейчас с этим отлично справляются HTML5 и FIleApi. Просто файлы надо отправлять по одному, а не пачкой (собственно «очередь» загрузки реализуется на JavaScript без проблем).
              –1
              Как-то грустно получается у.15% Рунета (Opera 12, IE8,9), это работать не будет.
              15%, ИМХО, это слишком много, что бы использовать в продакшн.
              Часто данные не умещаются в один post запрос из-за ограничений nginx/apache/php/etc.

              ИМХО, стоит, в первую очередь, решать увеличением максимального размера запроса на сервере. Сжали в 2 раза это хорошо, но станет данных больше и опять упретесь в эти же лимиты
              Из-за квадратичной сложности алгоритм обработки требователен к памяти и вычислительным мощностям. Поэтому не грешно было бы привлечь браузер пользователя.

              По факту вы дополнительно нагружаете, как браузер пользователя сжатием, так и сервер — разжатием. Хотя и экономите немного времени, на медленном канале.
                +3
                Ну для 15% можно сделать фэлбэк в виде стандартного POST запроса, а на остальных 85% экономить трафик и пользователя и сервера.
                  +2
                  Еще немаловажным фактом является экономия сил пользователя. Чем быстрее работает сервис, тем меньше устаешь от его использования. Причем сознательно задержку можно и не ощутить. Ну и, конечно, никто не запрещает разместить ненавязчивый информационный блок «Сайт может работать быстрее с этими браузерами».
                  +1
                  15% Рунета могут загружать несжатые данные. В нашем проекте старые браузеры все равно пролетают из-за скорости работы, поэтому вопрос совместимости не стоял.
                  Нет проблемы увеличить максимальный размер запроса. Сжимая мы экономим трафик и ускоряем загрузку данных, особенно для пользователей с медленным соединением.

                  А приведенная цитата про алгоритм относится к обработке ключевых слов в нашем проекте. Само сжатие вносит относительно незаметный overhead.
                    +1
                    не 15 а более, не забывайте про мобильный трафик, который все более и более ощутим. Единственное что на андроиде не все так печально ибо на девайсах от 4.х часто в комплекте идет гугл хром а не стандартный браузер. И там webworkers работает очень даже хорошо.
                      +1
                      В рамках того проекта про ключевики можно сказать с уверенностью, что мобильный трафик там еще долго не появится. Это я к тому, что инструменты и задача должны быть согласованы.
                    +1
                    Есть подозрение, что подобный сервис не особо посещаем «всем Рунетом». Это не Вконтакт, и не mail.ru…

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

                    Ну а уж сделать fallback в что-то более обычное (чистый POST) — это уж просто вежливость, как ни крути )
                    +1
                    помещалось в один http запрос

                    Если и есть ограничения для запроса, то они касаются конкретного веб-сервера или заданы в настройках веб-приложения.
                    Сжатие на клиенте сильно повысит нагрузку на процессор на клиенте же — тоже важно учитывать, надо ли вам оно.
                      +1
                      Тут будет иметь значение баланс «время сжатия минус время передачи сжатого — время передачи несжатого». И это зависит от размера, канала и сжимаемости данных.
                    • НЛО прилетело и опубликовало эту надпись здесь
                        +1
                        Спасибо за наводку, не знал.
                        В таком случае, если есть подписанный ssl сертификат, то действительно выгоднее использовать сжатие на уровне протокола. Работать должно быстрее и эффективнее.
                        0
                        А можете сравнить финальный размер с lz4 в режиме hc
                        Javascript — github.com/pierrec/node-lz4
                        PHP — github.com/kjdev/php-ext-lz4
                          0
                            0
                            Для php не ставил, а рабочей реализации на браузерном javascript не видел. По ссылкам выше: первая для node.js, вторую можно запустить в браузере, но она не работает: lz4.uncompress(lz4.compress('test')) выдаст ошибку.
                          +3
                          Попробуйте вместо base64 кодировать в шестнадцатиричную запись в виде строки, например, «ABC» -> байты с кодами 65 (0x41), 66 (0x42), 67 (0x43) -> шестнадцатиричная строка «414243», так чтобы каждому байту на входе соответствовало два символа на выходе.

                          Base64 кодирует каждые 3 байта на входе 4-мя на выходе. Это будет нарушать повторения во входных данных для алгоритма сжатия (на основе которых он и сжимает). Используя base64, вы понижаете качество сжатия. Например:

                          данные:«12345678901234567890»
                          base64: MTIzNDU2Nzg5MDEyMzQ1Njc4OTA= (повторение потерялось)
                          hex: 3132333435363738393031323334353637383930 (повторение сохранилось)

                          данные:«123456789123456789»
                          base64: MTIzNDU2Nzg5MTIzNDU2Nzg5 (повторение сохранилось, потому что период кратен трем)
                          hex: 313233343536373839313233343536373839 (повторение сохранилось)

                          Или еще пример:
                          данные:12341234
                          base64: MTIzNDEyMzQ= (повторение потерялось)

                          данные:1234_1234
                          base64: MTIzNF8xMjM0 (повторение потерялось)

                          данные:1234__1234
                          base64: MTIzNF9fMTIzNA== (повторение сохранилось)
                            +1
                            Обновил статью и код примера. Экранировать unicode оказалось эффективнее, чем hex. И, тем более, чем base64. Спасибо за подсказку.
                            0
                            > 7872 Кб (сжатие 84%)

                            Сжатие от исходных 9402 Кб будет не 84% (точнее, 83,73%), а как раз 100-83,73%=16,27%. Мы же говорим о сжатии, т.е. о величине, на которую размер уменьшается.
                              0
                              Имеется ввиду сколько осталось от первоначального объема, как пишут в архиваторах.
                              +1
                              Вы закодировали unicode строку в base64 и затем её сжимаете компрессором? Но это же жесть какая то… Зачем base64? Сразу 33% оверхед. Закодируйте какой-нибудь кодировкой и потом сразу в компрессор.

                              Ну и саму задачу на мой взгляд можно эффективнее чем за O(n^2) решить. Не могли бы кратко описать алгоритм?
                                0
                                Обновил статью и код примера, заменил base64 на экранирование unicode символов. Получилось действительно намного эффективнее. Спасибо за подсказку.

                                Сам алгоритм обработки ключевиков выходит за рамки данной статьи. Возможно напишу о нем позже.
                                  0
                                  Попробуйте тогда уж вместо stringEscape такую конструкцию unescape(encodeURIComponent(data)).
                                  Если интернет не врёт, то это самый простой способ получить UTF-8 из Unicode.
                                  Если сконвертишь в cp1251, то можно ещё сэкономить.
                                    0
                                    Функции escape и unescape обозначены как deprecated. Стоит ли их использовать в новых проектах?
                                –1
                              • НЛО прилетело и опубликовало эту надпись здесь
                                  0
                                  Может быть вы знаете, как такое детектить на стороне сервера?
                                  0
                                  Что мешает воспользоваться готовым бинарным протоколом, который ко всему прочему еще и тормозить на сжатии не будет? Тем же Thrift, например?

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

                                  Самое читаемое