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

В статье я покажу как мы решили эту задачу в новом проекте, используя сжатие и современные возможности 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. Это очень простой алгоритм. В примере воспользуемся такой реализацией:

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

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

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

Шаг 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); 

Объем запроса — 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. Как использовать 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 позволит не блокировать взаимодействие пользователя со страницей.
• И, конечно, не передавайте излишние данные без необходимости.

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