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

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

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

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

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

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

В ходе разработки у нас появилось две проблемы:

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

Решение

Есть множество способов решения. В нашем случае прокатил вариант, основанный на современных стандартах: Typed Arrays ^[3], Workers ^[4], XHR 2 ^[5]. В двух словах: мы сжимаем данные и отправляем их на сервер в двоичном виде. Эти простые действия позволили нам сократить размер передаваемых данных в 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 ^[6], Deflate ^[7], LZMA ^[8] и другие. Выбор будет зависеть, в основном, от наличия библиотек под клиент и сервер. Соответствующие javascript библиотеки легко находятся на гитхабе: раз ^[9], два ^[10], три ^[11].

Мы пробовали использовать все три варианта, но с PHP удалось подружить только 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, предварительно переведем данные в base64. Библиотека взята здесь ^[12].
Итак, сжимаем данные и отправляем на сервер:

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

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

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

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

 // используем 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); 

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

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

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

<?php 
$data = readBinaryData(file_get_contents('php://input'));
$data = lzw_decompress($data);
$data = base64_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;
}

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

Шаг 4: Workers

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

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

Очевидно, что приведенный выше javascript код не будет работать в IE6 =)
Для работы нам необходимы Typed Arrays ^[13], XHR 2 ^[14] и Workers ^[15].
Список поддерживаемых браузеров: 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: страница ^[16], worker ^[17]. Открываете страницу, открываете инструменты разработчика и смотрите на размер трех post запросов.

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

Заключение

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

Резюме:

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

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

Автор: Nodge

Источник ^[20]