JavaScript Ajv

https://github.com/ajv-validator/ajv

Java Snow

https://github.com/ssilverman/snowy-json

C# JSON.net

Schema

https://www.newtonsoft.com/jsonschema

Python jschon

https://github.com/marksparkza/jschon

Ruby JSONSchemer

https://github.com/davishmcclurg/json_schemer

Тео: Итак, если я вызову validate с этим поисковым запросом и этой схемой, будет

возвращено значение true?

Тео имеет в виду пример поискового запроса из листинга 7.7 и схему из листинга 7.6.

Листинг 7.7. Пример поискового запроса

{

"title": "habit",

"fields": ["title", "weight", "number_of_pages"]

}

Джо: А вы попробуйте сами!

И в самом деле! Когда Тео выполняет код для проверки поискового запроса, возвращается значение true.

Листинг 7.8. Валидация поискового запроса

var searchBooksRequestSchema = {

"type": "object",

"properties": {

"title": {"type": "string"},

"fields": {

"type": "array",

"items": {"type": "string"}

}

},

"required": ["title", "fields"]

};

var searchBooksRequest = {

"title": "habit",

"fields": ["title", "weight", "number_of_pages"]

};

Глава 7. Основы валидации данных

187

validate(searchBooksRequestSchema, searchBooksRequest);

// → true

Джо: А теперь попробуйте выполнить невалидный запрос.

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

опечатку в поле title и назову его tilte с буквой l перед буквой t.

Как и ожидалось, код с типом возвращает значение false. Тео не удивлен, а Джо

улыбается от уха до уха.

Листинг 7.9. Валидация недействительного поискового запроса

var invalidSearchBooksRequest = {

"tilte": "habit",

"fields": ["title", "weight", "number_of_pages"]

};

validate(searchBooksRequestSchema, invalidSearchBooksRequest);

// → false

Тео: Синтаксис JSON-схемы гораздо более многословный, чем синтаксис объявле-ния элементов в классе. Почему это?

Джо: По двум причинам. Во-первых, поскольку JSON-схема не зависит от языка, ее

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

Тео: Ясно.

Джо: Во-вторых, JSON-схема позволяет вам выражать условия валидации, которые

гораздо сложнее, а то и невозможно выразить, когда данные представлены с помощью классов.

СОВЕТ. Выразительные способности JSON-схемы очень мощные!

Тео: Вы меня заинтриговали! А сможете привести еще несколько примеров?

Джо: Сейчас поговорим о композиции схемы. А однажды я покажу вам несколько

примеров расширенной валидации.

ПРИМЕЧАНИЕ. Расширенная валидация описана в главе 12.

Тео: А что такое расширенная валидация?

Джо: Под расширенной валидацией я подразумеваю, например, проверку того, что

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

Тео: Есть ли способ получить подробную информацию о том, почему запрос невалиден?

188

Часть 2. Масштабируемость

Джо: Конечно! Я покажу вам попозже. А пока позвольте мне показать вам, как

проверить, что ответ, который сервер отправляет обратно клиенту, является

валидным.

Тео: Это выглядит намного сложнее, чем поисковый запрос книги!

Джо: Почему?

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

7.3. Гибкость и строгость схемы

Джо: А не могли бы вы привести мне пример того, как будет выглядеть ответ на

запрос о поиске книги?

Тео: Взгляните-ка на такой пример. Это поисковый запрос с информацией о двух

книгах: «Семь навыков высокоэффективных людей» и «Сила привычки».

Листинг 7.10. Пример ответа на поисковый запрос

[

{

"title": "7 Habits of Highly Effective People",

"available": true,

"isbn": "978-0812981605",

"subtitle": "Powerful Lessons in Personal Change",

"number_of_pages": 432

},

{

"title": "The Power of Habit",

"available": false,

"isbn_13": "978-1982137274",

"subtitle": "Why We Do What We Do in Life and Business",

"subjects": [

"Social aspects",

"Habit",

"Change (Psychology)"

]

}

]

Джо: Какое совпадение, что вы упомянули о «Силе привычки». Я как раз сейчас

читаю эту книгу, чтобы избавиться от своей привычки грызть ногти. Итак, какие

поля обязательны, а какие необязательны в ответе на поиск книги?

Тео: В информации о книге поля title и available обязательны для заполнения.

Остальные поля являются необязательными.

Глава 7. Основы валидации данных

189

Джо: Когда мы создавали схему для запроса на поиск книг, я уже упоминал, что

поля на карте по умолчанию являются необязательными. Чтобы сделать поле

обязательным, мы должны включить его в массив required. Я бы попробовал

реализовать это с помощью чего-то такого.

Листинг 7.11. Схема ответа на поисковый запрос

var searchBooksResponseSchema = {

"type": "array",

"items": {

"type": "object",

"required": ["title", "available"],

"properties": {

"title": {"type": "string"},

"available": {"type": "boolean"},

"subtitle": {"type": "string"},

"number_of_pages": {"type": "integer"},

"subjects": {

"type": "array",

"items": {"type": "string"}

},

"isbn": {"type": "string"},

"isbn_13": {"type": "string"}

}

}

};

СОВЕТ. В JSON-схеме поля карты являются необязательными по умолчанию.

Тео: Однако же указывать список обязательных полей намного проще, чем указывать, что элемент в классе допускает значение null!

Джо: Согласен!

Тео: С другой стороны, мне кажется, что при вложении схемы информации о книге

в схему ответов на поисковый запрос код становится труден для чтения.

Джо: Ничего не мешает вам отделить схему информации о книге от схемы ответов

на поисковый запрос.

Тео: Как это?

Джо: Это нормально для JSON, друг мой. Вы можете свободно манипулировать

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

схему, чтобы показать вам, что я имею в виду.

190

Часть 2. Масштабируемость

Листинг 7.12. Реорганизованная схема ответа на поисковый запрос

var bookInfoSchema = {

"type": "object",

"required": ["title", "available"],

"properties": {

"title": {"type": "string"},

"available": {"type": "boolean"},

"subtitle": {"type": "string"},

"number_of_pages": {"type": "integer"},

"subjects": {

"type": "array",

"items": {"type": "string"}

},

"isbn": {"type": "string"},

"isbn_13": {"type": "string"}

}

};

var searchBooksResponseSchema = {

"type": "array",

"items": bookInfoSchema

};

Тео: В самом деле, должен признать, что JSON-схемы более компонуемы, чем определения классов.

СОВЕТ. JSON-cхемы — это просто карты. Мы вольны компоновать их и манипулировать

ими, как и любой другой картой.

Джо: Давайте перейдем к валидации данных, полученных из внешних источников.

Тео: А разве есть отличия?

Джо: На самом деле нет, но я воспользуюсь этим как возможностью показать вам и

другие возможности JSON-схемы.

Тео: С удовольствием узнал бы, как используется валидация данных, когда мы

обращаемся к данным из базы данных.

Джо: Каждый раз, когда мы обращаемся к данным извне, рекомендуется валидировать их. Покажите мне, пожалуйста, пример того, как будет выглядеть ответ

базы данных на поисковый запрос.

СОВЕТ. Рекомендуется валидировать данные, поступающие из внешнего источника.

Тео: Когда мы запрашиваем книги из базы данных, мы ожидаем получить массив

книг с тремя полями: title, isbn и available. Первые два значения должны быть

строками, а третье должно быть булевым значением (Boolean).

Глава 7. Основы валидации данных

191

Джо: А эти поля необязательные или обязательные?

Тео: Что вы имеете в виду?

Джо: Могут ли существовать книги, для которых некоторые поля не определены?

Тео: Нет.

Джо: В этом случае схема довольно проста. Не хотите ли попробовать написать

схему для ответа базы данных?

Тео: Дайте подумать. Это массив объектов, где каждый объект имеет три свойства, так что получится что-то вроде этого?

Листинг 7.13. Схема ответа базы данных

{

"type": "array",

"items": {

"type": "object",

"required": ["title", "isbn", "available"],

"properties": {

"title": {"type": "string"},

"available": {"type": "boolean"},

"isbn": {"type": "string"}

}

}

}

Джо: Отлично, друг мой! Теперь я хочу рассказать вам о поле additionalProperties в JSON-схеме.

Тео: А что это?

Джо: Взгляните на этот массив.

Листинг 7.14. Массив книг с дополнительным свойством

[

{

"title": "7 Habits of Highly Effective People",

"available": true,

"isbn": "978-0812981605",

"dummy_property": 42

},

{

"title": "The Power of Habit",

"available": false,

"isbn": "978-1982137274",

"dummy_property": 45

}

]

192

Часть 2. Масштабируемость

Джо: Это валидный ответ базы данных?

Тео: Нет. В ответе базы данных не должно быть поля dummy_property. В нем должны

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

Джо: Это может вас удивить, но по умолчанию поля, не указанные в схеме объекта, разрешены в JSON-схеме. Чтобы запретить их, нужно установить для поля

additionalProperties значение false, как здесь.

Листинг 7.15. Запрещение свойства, не упомянутого в схеме

var booksFromDBSchema = {

"type": "array",

"items": {

"type": "object",

"required": ["title", "isbn", "available"],

"additionalProperties": false,

"properties": {

"title": {"type": "string"},

"available": {"type": "boolean"},

"isbn": {"type": "string"}

}

}

};

СОВЕТ. В JSON-схеме по умолчанию разрешены поля, не указанные в схеме карты.

Тео: А почему так?

Джо: Причина в том, что обычно наличие дополнительных полей на карте не

вызывает проблем. Если ваш код не интересуется каким-либо полем, он просто

игнорирует его. Но иногда нам нужно быть максимально точными, тогда мы

установим false в качестве значения для additionalProperties.

Тео: А как насчет схемы поискового запроса и ответа из предыдущего обсуждения?

Должны ли мы установить для additionalProperties значение false?

Джо: Прекрасный вопрос. Я бы сказал, что это дело вкуса. Лично мне нравится

разрешать дополнительные поля в запросах и запрещать их в ответах.

Тео: В чем здесь преимущество?

Джо: Ну, веб-сервер занимается ответами, которые он отправляет своим клиентам.

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

клиентами, и я предпочитаю делать все возможное, чтобы обслуживать своих

клиентов, даже когда они не так точны, как следовало бы.

Тео: Ах, конечно. «Клиент всегда прав».

Джо: На самом деле мне больше нравится принцип надежности, сформулирован-ный Джоном Постелом: «Будьте консервативны в том, что вы отправляете, будьте либеральны в том, что вы принимаете».

Глава 7. Основы валидации данных

193

СОВЕТ. Рекомендуется досконально точно относиться к данным, которые вы отправляете, и проявлять гибкость в отношении данных, которые вы получаете.

7.4. Композиция схемы

Тео: А что насчет валидации данных, поступающих с внешнего веб-сервиса?

Джо: Приведите-ка пример!

Тео: В ближайшем будущем нам придется интегрироваться с сервисом под названием Open Library Books API, который предоставляет подробную информацию

о книгах.

ПРИМЕЧАНИЕ. Для получения информации об API Open Library Books

см. https://openlibrary.org/dev/docs/api/books.

Джо: Покажите, пожалуйста, ответ сервиса для, допустим, комикса «Хранители».

Тео: Хорошо. Вот.

Тео нажимает несколько клавиш на своей клавиатуре и выводит ответ. Джо долго

смотрит на получившуюся JSON-схему.

Листинг 7.16. Пример ответа API Open Library Books

{

"publishers": [

"DC Comics"

],

"number_of_pages": 334,

"weight": "1.4 pounds",

"physical_format": "Paperback",

"subjects": [

"Graphic Novels",

"Comics & Graphic Novels",

"Fiction",

"Fantastic fiction"

],

"isbn_13": [

"9780930289232"

],

"title": "Watchmen",

"isbn_10": [

"0930289234"

],

"publish_date": "April 1, 1995",

"physical_dimensions": "10.1 x 6.6 x 0.8 inches"

}

194

Часть 2. Масштабируемость

Тео недоумевает: «Что может быть особенного в этой схеме?» Пока Джо размышляет над этим фрагментом JSON, Тео пишет JSON-схему для ответа Books API. Это

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

Листинг 7.17. Схема ответа API Open Library Books

{

"type": "object",

"required": ["title"],

"properties": {

"title": {"type": "string"},

"publishers": {

"type": "array",

"items": {"type": "string"}

},

"number_of_pages": {"type": "integer"},

"weight": {"type": "string"},

"physical_format": {"type": "string"},

"subjects": {

"type": "array",

"items": {"type": "string"}

},

"isbn_13": {

"type": "array",

"items": {"type": "string"}

},

"isbn_10": {

"type": "array",

"items": {"type": "string"}

},

"publish_date": {"type": "string"},

"physical_dimensions": {"type": "string"}

}

}

Джо: Вышло отлично!

Тео: Было не так уж и сложно. Я только не могу понять, почему вы так долго смотрели на ту схему ответа.

Джо: А это все из-за полей isbn_10 и isbn_13. Я предполагаю, что они оба не являются обязательными.

Тео: Верно! Поэтому я и не включил их в поле required своей схемы.

Джо: Но одно из них всегда должно там присутствовать, не так ли?

Тео: Иногда одно, а иногда и оба, как для «Хранителей». Это зависит от года издания книги. Книги, опубликованные до 2007 года, имеют isbn_10, а книги, опубликованные после 2007 года, имеют isbn_13.

Глава 7. Основы валидации данных

195

Джо: А, понятно. И у «Хранителей» есть и то и другое, потому что первоначально

этот комикс был опубликован в 1986 году, а затем снова начал публиковаться

после 2007 года.

Тео: Точно.

Джо: Значит, вам нужно, чтобы ваша схема указывала, что одно из полей isbn является обязательным. Это дает мне шанс рассказать вам о композиции JSON-схемы.

Тео: Что же это такое?

Джо: Это способ комбинирования схем аналогично тому, как мы комбинируем ло-гические условия с AND, OR и NOT.

Тео: Давайте на это посмотрим.

Джо: Сейчас. Как бы вы выразили схему для ответа Books API в виде композиции

из трех схем: basicBookInfoSchema, написанной вами схемы, где обязательно

только поле title; mandatoryIsbn13, схемы, где обязательно только поле isbn_13, и mandatoryIsb10, схемы, где обязательно только isbn_10?

Тео: Я думаю, это должно быть так: basicBookInfoSchema AND (mandatoryIsbn13 OR

mandatoryIsbn10).

Джо: Абсолютно верно! Правда, в JSON-схеме мы используем ключевые слова

allOf вместо AND и anyOf вместо OR.

Джо показывает Тео результат в листинге 7.18 и пример его использования в листинге 7.19.

Листинг 7.18. Схема ответа внешнего API

var basicBookInfoSchema = {

"type": "object",

"required": ["title"],

"properties": {

"title": {"type": "string"},

"publishers": {

"type": "array",

"items": {"type": "string"}

},

"number_of_pages": {"type": "integer"},

"weight": {"type": "string"},

"physical_format": {"type": "string"},

"subjects": {

"type": "array",

"items": {"type": "string"}

},

"isbn_13": {

"type": "array",

"items": {"type": "string"}

},

196

Часть 2. Масштабируемость

"isbn_10": {

"type": "array",

"items": {"type": "string"}

},

"publish_date": {"type": "string"},

"physical_dimensions": {"type": "string"}

}

},

var mandatoryIsbn13 = {

"type": "object",

"required": ["isbn_13"]

};

var mandatoryIsbn10 = {

"type": "object",

"required": ["isbn_10"]

};

var bookInfoSchema = {

"allOf": [

basicBookInfoSchema,

{

"anyOf": [mandatoryIsbn13, mandatoryIsbn10]

}

]

};

Листинг 7.19. Проверка ответа внешнего API

var bookInfo = {

"publishers": [

"DC Comics"

],

"number_of_pages": 334,

"weight": "1.4 pounds",

"physical_format": "Paperback",

"subjects": [

"Graphic Novels",

"Comics & Graphic Novels",

"Fiction",

"Fantastic fiction"

],

"isbn_13": [

"9780930289232"

],

Глава 7. Основы валидации данных

197

"title": "Watchmen",

"isbn_10": [

"0930289234"

],

"publish_date": "April 1, 1995",

"physical_dimensions": "10.1 x 6.6 x 0.8 inches"

};

validate(bookInfoSchema, bookInfo);

// → true

Тео: Понятно, почему они называются allOf и anyOf. Первое ключевое слово означает, что данные должны соответствовать всем схемам, а второе означает, что

данные должны соответствовать любой из схем.

Джо: Ага.

ПРИМЕЧАНИЕ. JSON-схема также поддерживает ключевое слово oneOf для случаев, когда данные должны быть действительны только для одной схемы.

Тео: Неплохо. Кажется, что при использовании композиции JSON-схема обладает

большей выразительностью, чем та, к которой я привык для представления данных с помощью классов.

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

с помощью классов.

ПРИМЕЧАНИЕ. О расширенной валидации данных рассказывается в главе 12.

Тео: Однако меня все еще беспокоит один момент. Когда данные невалидны, невозможно узнать, что именно пошло не так.

7.5. Сведения о сбоях при валидации данных

Джо: До сих пор мы рассматривали валидацию в JSON-схеме так, как если бы она

была двоичной: либо фрагмент данных валиден, либо нет.

Тео: Ну да...

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

Тео: Можем ли мы, например, когда отсутствует обязательное поле, получить название этого поля?

Джо: Да. И даже когда фрагмент данных не соответствует ожидаемому типу, мы

можем получить информацию и об этом.

Тео: Полезная штука!

198

Часть 2. Масштабируемость

Джо: Несомненно. Позвольте мне показать вам, как это работает. До сих пор мы

использовали общую функцию validate, но когда мы сталкиваемся с ошибками

валидации, нам нужно что-то более конкретное.

Тео: Почему?

Джо: Потому что каждая библиотека валидации данных имеет свой собственный

способ выведения информации о сбоях валидации. Например, в валидаторе Ajv из JavaScript ошибки с последней валидации данных хранятся в виде массива

внутри экземпляра валидатора.

Тео: А почему в массиве?

Джо: Потому что сбоев может быть несколько. Но давайте начнем с единичного

сбоя. Представьте, что мы сталкиваемся с запросом на поиск книги, где поле

заголовка называется myTitle вместо title. Взгляните на этот пример. Как вы

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

Листинг 7.20. Доступ к ошибкам валидации в Ajv

var searchBooksRequestSchema = {

"type": "object",

"properties": {

"title": {"type": "string"},

"fields": {

"type": "array",

"items": {"type": "string"}

}

},

"required": ["title", "fields"]

};

var invalidSearchBooksRequest = {

"myTitle": "habit",

"fields": ["title", "weight", "number_of_pages"]

};

var ajv = new Ajv(); ❶

ajv.validate(searchBooksRequestSchema, invalidSearchBooksRequest); ajv.errors ❷

❶ Создает экземпляр валидатора.

❷ Отображает ошибки валидации.

Тео: А как выглядит информация внутри массива errors?

Джо: Выполните фрагмент кода — и увидите.

Глава 7. Основы валидации данных

199

Когда Тео выполняет фрагменты кода из листинга 7.20, он едва верит своим глазам.

Он изучает информацию, с трудом ее переваривая.

Листинг 7.21. Сведения об одном сбое валидации данных в формате массива

[

{

"instancePath": "",

"schemaPath": "#/required",

"keyword": "required",

"params": {

"missingProperty":"title"

},

"message": "must have required property 'title'"

}

]

Тео: Мне довольно сложно понять содержимое массива errors.

Джо: Мне тоже. К счастью, Ajv предоставляет служебную функцию errorsText для

преобразования массива errors в удобочитаемый формат. Посмотрите, например, что возвращается при вызове errorsText.

Листинг 7.22. Отображение ошибок в удобочитаемом формате

ajv.errorsText(ajv.errors);

// → "data must have required property 'title'"

Тео: Давайте посмотрим, что происходит, когда в данных более одного сбоя валидации.

Джо: По умолчанию Ajv улавливает только одну ошибку валидации.

СОВЕТ. По умолчанию Ajv фиксирует только первый сбой валидации.

Тео: Насколько я понимаю, это сделано из соображений производительности. Как

только валидатор обнаруживает ошибку, он прекращает парсинг данных.

Джо: Наверное, так оно и есть. В любом случае, чтобы перехватить более одного

сбоя валидации, вам нужно передать параметры allErrors конструктору Ajv. Посмотрите на такой код.

Листинг 7.23. Обнаружение множественных сбоев валидации

var searchBooksRequestSchema = {

"type": "object",

"properties": {

"title": {"type": "string"},

200

Часть 2. Масштабируемость

"fields": {

"type": "array",

"items": {"type": "string"}

}

},

"required": ["title", "fields"]

};

var invalidSearchBooksRequest = { ❶

"myTitle": "habit",

"fields": [1, 2]

};

var ajv = new Ajv({allErrors: true}); ❷

ajv.validate(searchBooksRequestSchema, invalidSearchBooksRequest); ajv.errorsText(ajv.errors); ❸

// → "data must have required property 'title',

// → data/fields/0 must be string,

// → data/fields/1 must be string"

❶ Запрос с тремя сбоями.

❷ Создает экземпляр конструктора Ajb с allErrors: значение true задается для того, чтобы

обнаружить более чем один сбой.

❸ Конвертирует ошибки в удобочитаемый формат.

Джо: Мы валидируем поисковый запрос с полем myTitle вместо title и цифрами

вместо строк в массиве fields. Как вы можете увидеть в выходных данных

фрагмента кода, возвращаются три ошибки.

Тео: Великолепно! Похоже, что теперь у меня есть все, что нужно, чтобы добавить

валидацию данных к границам моей системы, на случай если Нэнси попросит

меня превратить Систему управления библиотекой в веб-сервер.

Джо: Вы позволите мне сделать вам небольшой подарок в знак нашей дружбы?

Тео: Почту за честь.

Джо достает из сумки небольшой сверток, перевязанный светло-зеленой лентой.

Торжественным жестом он вручает его Тео.

Когда Тео развязывает ленту, он обнаруживает элегантный листок бумаги, укра-шенный симпатичными миниатюрными узорами. В центре листа Тео читает надпись «Шпаргалка по JSON-схеме». Он улыбается, просматривая шпаргалку. Очень

полезный подарок.

Листинг 7.24. Шпаргалка по JSON-схеме

{

"type": "array", ❶

"items": {

Глава 7. Основы валидации данных

201

"type": "object", ❷

"properties": { ❸

❹ "myNumber": {"type": "number"},

❺ "myString": {"type": "string"},

"myEnum": {"enum": ["myVal", "yourVal"]}, ❻

❼ "myBool": {"type": "boolean"}

},

"required": ["myNumber", "myString"], ❽

"additionalProperties": false ❾

}

}

❶ На корневом уровне данные — это массив.

❷ Каждый элемент массива — это карта.

❸ Свойства каждого поля в карте.

❹ myNumber — это число.

❺ myString — это строка.

❻ myEnum — это значение перечисления с двумя вероятными сценариями: «myVal» и

«yourVal».

❼ myBool — это булево значение.

❽ Обязательные поля в карте — это myNumber и myString; прочие поля необязательны.

❾ Мы не разрешаем поля, которые не упомянуты в схеме явно.

Затем Тео переворачивает шпаргалку и обнаруживает, что обратная сторона тоже

заполнена рисунками. В центре листа он читает надпись: «Пример валидных данных».

Листинг 7.25. Пример валидных данных

[

{ ❶

"myNumber": 42,

"myString": "Hello",

"myEnum": "myVal",

"myBool": true

},

{ ❷

"myNumber": 54,

"myString": "Happy"

}

]

❶ Эта карта валидна, потому что все ее поля валидны.

❷ Эта карта валидна, потому что она содержит все обязательные поля.

202

Часть 2. Масштабируемость

Итоги

Принцип ДОП № 4 заключается в разделении схемы данных и представлении

данных.

Границы системы определяются как области, в которых система обменивается

данными.

Примерами валидации данных на границах системы являются валидация кли-ентских запросов и ответов, а также валидация данных, поступающих из внешних источников.

Валидация данных в ДОП означает проверку соответствия фрагмента данных

схеме.

Когда фрагмент данных невалиден, мы получаем информацию о сбоях валидации и отправляем эту информацию клиенту в удобочитаемом формате.

Когда данные на границах системы валидны, повторная валидация данных внутри системы не является необходимой.

JSON-схема — это язык, который позволяет нам отделять валидацию данных от

представления данных.

Синтаксис JSON-схемы может показаться многословным.

Выразительная способность JSON-схемы высока.

JSON-схемы — это просто карты, и поэтому мы можем свободно манипулировать ими, как и любыми другими картами в наших программах.

Мы можем сохранить определение схемы в переменной и использовать эту

переменную в другой схеме.

В JSON-схеме поля карты по умолчанию являются необязательными.

Рекомендуется проверять данные, поступающие из внешнего источника.

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

Ajv — это библиотека схем JSON на JavaScript.

По умолчанию Ajv фиксирует только первый сбой валидации.

О расширенной валидации говорится в главе 12.

Расширенный контроль конкурентности

И никаких взаимоблокировок!

В ЭТОЙ ГЛАВЕ РАССМАТРИВАЮТСЯ

Атомы как альтернатива блокировкам.

Управление потокобезопасным счетчиком и потокобезопасным кешем

в памяти (англ. in-memory cash) с помощью атомов.

Управление состоянием всей системы потокобезопасным

способом с помощью атомов.

Традиционный способ управления конкурентностью в многопоточной среде включает механизмы блокировки, такие как мьютексы. Механизмы блокировки, как

правило, увеличивают сложность системы, потому что не так-то просто убедиться, что система свободна от взаимоблокировок. В ДОП мы используем тот факт, что

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

блокировками, потому что они не блокируются. Как следствие, обычная сложность

блокировок, которые требуются, чтобы избежать взаимоблокировок, не относится

к атомам.

ПРИМЕЧАНИЕ. Эта глава в основном относится к многопоточным средам, таким как Java, C#, Python и Ruby. Это менее актуально для однопоточных сред, таких как JavaScript. Фрагменты кода JavaScript в этой главе написаны так, как если бы JavaScript был многопоточным.

8.1. Сложность блокировок

Этим воскресным днем, проезжая на велосипеде по мосту Золотые Ворота, Тео

с беспокойством думает о проекте Klafim. Он еще не совсем уверен, что стоило

делать ставку на ДОП. Внезапно Тео понимает, что он еще не запланировал следующую сессию с Джо. Он слезает с велосипеда, чтобы позвонить Джо. К сожалению, линия занята.

204

Часть 2. Масштабируемость

Когда Тео возвращается домой, он снова пытается позвонить Джо, но телефон снова занят. После ужина Тео пытается дозвониться Джо еще раз, с тем же результатом: короткие гудки. «Наверное, Джо сегодня очень занят», говорит себе Тео.

Измученный 50-мильной поездкой на велосипеде со средней скоростью 17 миль

в час, он засыпает на диване. Когда Тео просыпается, он с восторгом видит сообщение от Джо: «Встретимся в понедельник утром в 11 утра?». Тео отвечает подня-тым большим пальцем и готовится к следующей рабочей неделе.

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

Они озадаченно смотрят друг на друга, а затем одновременно разражаются смехом, когда осознают, что произошло: по удивительному совпадению они пытались дозвониться друг другу в одно и то же время. Они одновременно рассмеялись: «Взаимоблокировка!»

Далее наши программисты проследовали в офис Тео. Когда они добрались до стола

Тео, Джо объявил, что сегодняшняя сессия будет посвящена контролю конкурентности в многопоточных средах.

Джо: Итак, как же управлять конкурентностью в многопоточной среде?

Тео: Нужно защитить доступ к критическим разделам с помощью механизма блокировки, например мьютекса.

Джо: Когда вы говорите «доступ», вы имеете в виду доступ на запись или доступ

на чтение тоже?

Тео: И то и другое!

Джо: А почему нужно защищать доступ на чтение с помощью блокировки?

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

Джо: Другим вариантом было бы клонировать данные перед их обработкой при

чтении.

Тео: Иногда я клонирую данные; но во многих случаях, когда объем большой, кло-нирование данных слишком затратно.

СОВЕТ. Клонирование данных во избежание блокировок при чтении не масштабируется.

Джо: В ДОП нам не нужно клонировать данные или защищать доступ на чтение.

Тео: Потому что данные неизменяемы?

Джо: Верно. Когда данные неизменяемы, даже если запись происходит в другом

потоке во время чтения, это не сделает чтение непоследовательным, потому что

запись никогда не изменяет считываемые данные.

Тео: Похоже, что чтение всегда работает со снимком (англ. snapshot) данных.

Джо: Точно!

Глава 8. Расширенный контроль конкурентности

205

СОВЕТ. Когда данные неизменяемы, операция чтения всегда безопасна.

Тео: А что насчет доступа на запись? Разве не нужно защищать это блокировками?

Джо: Нет.

Тео: А почему нет?

Джо: Есть более простой механизм под названием «атом».

Тео: Рад слышать, что есть что-то более простое, чем блокировки. Я каждый раз

с трудом интегрирую блокировки в многопоточную систему.

Джо: Я тоже! Я до сих пор помню ошибку, с которой мы столкнулись во время

эксплуатации 10 лет назад. Мы забыли снять блокировку, когда в критической

секции возникло исключение. Получилась ужасная взаимоблокировка.

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

Джо: У меня для вас отличные новости. При использовании атомов взаимоблокировок вообще не бывает!

СОВЕТ. При использовании атомов взаимоблокировок не бывает.

Тео: Звучит здорово. Рассказывайте дальше!

СОВЕТ. Атомы предоставляют способ управления конкурентностью без блокировок.

8.2. Потокобезопасный счетчик с атомами

Джо: Давайте начнем с простого случая: счетчик, используемый потоками совместно.

Тео: Что вы подразумеваете под счетчиком?

Джо: Представьте, что мы хотим подсчитать количество обращений к базе данных

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

Тео: Представил.

Джо: Не напишите ли для нашего многопоточного счетчика JavaScript-код с использованием блокировок?

Тео: Но JavaScript однопоточный!

Джо: Я знаю, но это просто для иллюстрации. Представьте, что JavaScript многопо-точный и что он предоставляет объект мьютекс, который можно блокировать и

разблокировать.

Тео: Это как-то нелепо. Я думаю, выглядеть будет примерно так.

Тео подходит к доске. Он пишет нечто, что, по его мнению, является кодом

JavaScript для многопоточного счетчика с блокировками.

206

Часть 2. Масштабируемость

Листинг 8.1. Потокобезопасный счетчик, защищенный мьютексом

var mutex = new Mutex();

var counter = 0;

function dbAccess() {

mutex.lock();

counter = counter + 1;

mutex.unlock();

// access the database

}

function logCounter() {

mutex.lock();

console.log('Number of database accesses: ' + counter);

mutex.unlock();

}

Джо: Прекрасно. Теперь я покажу вам, как написать тот же самый код с помощью

атомов. Атом предоставляет три метода:

get возвращает текущее значение атома;

set перезаписывает текущее значение атома;

swap получает функцию и обновляет значение атома при помощи результата

функции, вызванной для текущего значения атома.

Джо расстегивает молнию на чехле своего ноутбука и достает листок бумаги. Он

протягивает его Тео. Тео приятно удивлен, поскольку на листе бумаги кратко опи-саны вышеупомянутые методы (табл. 8.1).

Таблица 8.1. Три метода атома

Метод Описание

get

Возвращает текущее значение

set

Перезаписывает текущее значение

swap

Обновляет текущее значение при помощи функции

Тео: Что будет, если мы реализуем потокобезопасный счетчик с помощью атома?

Джо: На самом деле все довольно просто.

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

счетчика в атоме.

Листинг 8.2. Потокобезопасный счетчик, хранящийся в атоме

var counter = new Atom();

counter.set(0);

Глава 8. Расширенный контроль конкурентности

207

function dbAccess() {

counter.swap(function(x) { ❶

return x + 1;

});

// access the database

}

function logCounter() {

console.log('Number of database accesses: ' + counter.get());

}

❶ Аргумент x — это текущее значение атома, такое же, как в counter.get().

Тео: Расскажите-ка мне, что здесь происходит?

Джо: Без проблем! Сначала мы создаем пустой атом. Затем инициализируем значение атома с помощью counter.set(0). В логгере потоков (англ. logger thread) мы

считываем текущее значение атома с помощью counter.get().

Тео: А как нам прирастить счетчик в потоках, которые обращаются к базе данных?

Джо: Нужно вызывать swap с функцией, которая получает x и возвращает x + 1.

Тео: Я не понимаю, как swap может быть потокобезопасным вообще без использования блокировок.

Джо быстро подходит к доске. Он набрасывает схему с рис. 8.1.

Рис. 8.1. Высокоуровневый

алгоритм swap

Джо: Видите ли, swap вычисляет следующее значение атома, и перед изменением

текущего значения атома он проверяет, изменилось ли значение атома во время

вычисления. Если это так, swap повторяет попытку до тех пор, пока во время

вычисления не произойдет никаких изменений.

Тео: Насколько легко реализуется swap?

Джо: Я покажу вам реализацию класса Atom, и вы сами увидите.

208

Часть 2. Масштабируемость

Листинг 8.3. Реализация класса Atom

class Atom {

state;

constructor() {}

get() {

return this.state;

}

set(state) {

this.state = state;

}

swap(f) {

while(true) {

var stateSnapshot = this.state;

var nextState = f(stateSnapshot);

if (!atomicCompareAndSet(this.state,

stateSnapshot,

nextState)) { ❶

continue;

}

return nextState;

}

}

}

❶ Использует специальную потокобезопасную операцию сравнения, поскольку this.state могло измениться в другом потоке во время выполнения функции f.

Тео подходит ближе к доске. Он вносит правку в диаграмму Джо так, чтобы алгоритм swap-операции выглядел более подробным. Получившаяся диаграмма приведена на рис. 8.2. Однако у Тео все еще осталось несколько вопросов.

Тео: Что такое atomicCompareAndSet?

Джо: Это основная работа атома. atomicCompareAndSet атомарно устанавливает для

состояния новое значение тогда и только тогда, когда состояние равно предос-тавленному старому значению. Она возвращает значение true при успехе и false при неудаче.

Тео: Как эта функция может быть атомарной без использования блокировок?

Джо: Хороший вопрос! На самом деле atomicCompareAndSet — это операция сравнения с обменом (англ. compare-and-swap), предоставляемая языком, который полагается на функциональность самого процессора. Например, в Java в пакете

java.util.concurrent.atomic есть универсальный класс AtomicReference, который

предоставляет метод compareAndSet().

Глава 8. Расширенный контроль конкурентности

209

Рис. 8.2. Подробный

высокоуровневый алгоритм swap

ПРИМЕЧАНИЕ. См. http://tutorials.jenkov.com/java-concurrency/compare-and-swap.html для получения общей информации об операциях сравнения с обменом. Реализации для

многопоточных языков приведены в табл. 8.2.

Таблица 8.2. Реализация атомарного сравнения с обменом на различных языках

Язык Ссылка

Java

http://mng.bz/mx0W

JavaScript

Неактуально (однопоточный язык)

Ruby

http://mng.bz/5KG8

Python

https://github.com/maxcountryman/atomos

C#

http://mng.bz/6Zzp

Тео: Кстати о Java: как будет выглядеть реализация атома?

Джо: Да примерно также, за исключением того факта, что класс Atom должен использовать дженерики, а внутреннее состояние должно храниться в AtomicReference.

Джо запускает Java-реализацию класса Atom на своем ноутбуке. Тео просматривает

код.

Листинг 8.4. Реализация класса Atom в Java

class Atom<ValueType> {

private AtomicReference<ValueType> state;

210

Часть 2. Масштабируемость

public Atom() {}

ValueType get() {

return this.state.get();

}

void set(ValueType state) {

this.state.set(state); ❶

}

ValueType swap(UnaryOPerator<ValueType> f) {

while(true) {

ValueType stateSnapshot = this.state.get();

ValueType nextState = f(stateSnapshot);

if (!this.state.compareAndSet(stateSnapshot,

nextState)) {

continue;

}

}

return nextState;

}

}

❶ this.state могло измениться в другом потоке во время выполнения f.

Тео: А что насчет использования атома в Java?

Джо: Смотрите. Это довольно просто.

Листинг 8.5. Использование класса Atom в Java

Atom<Integer> counter = new Atom<Integer>();

counter.set(0);

counter.swap(x -> x + 1);

counter.get();

В течение пары минут Тео размышляет обо всех этих атомах-шматомах и перева-ривает новую информацию. Затем он спрашивает Джо:

Тео: А что если swap никогда не увенчается успехом? Я имею в виду, может ли

цикл while внутри кода для swap оказаться бесконечным циклом?

Джо: Нет! По определению, когда atomicCompareAndSet терпит неудачу с потоком, это означает, что тот же самый атом был изменен в другом потоке во время

выполнения swap. В этом соревновании потоков всегда есть победитель.

Тео: Неужели не может случиться так, что один поток никогда не добивается успеха, потому что он всегда проигрывает в соревновании с другими потоками?

Глава 8. Расширенный контроль конкурентности

211

Джо: Теоретически да, может. Но я никогда не сталкивался с такой ситуацией.

Если у вас в наличии тысячи потоков, которые не занимаются ничем, кроме обмена атомов, это, наверное, может произойти. Но на практике, как только атом

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

к базе данных или операцию ввод-вывод. Это дает возможность другим потокам

успешно обменивать атомы.

ПРИМЕЧАНИЕ. В теории атомы могут вызвать голодание в системе с тысячами потоков, которые не занимаются ничем, кроме обмена атомов. На практике, как только атом заменяется, потоки выполняют реальную работу (например, получают доступ к базе данных), что

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

Тео: Интересно... Действительно, атомами, похоже, гораздо проще управлять, чем

блокировками.

Джо: Теперь позвольте мне показать вам, как использовать атомы с составными

данными.

Тео: А что, есть отличия?

Джо: Обычно работать со составными данными сложнее, чем с примитивными

типами.

Тео: Когда вы уговаривали меня стать адептом ДОП, вы упомянули, что там можно

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

СОВЕТ. В ДОП управление данными осуществляется с той же простотой, что и управление числами.

Джо: Это именно то, что я собираюсь вам показать.

8.3. Потокобезопасный кеш с атомами

Джо: Вы знакомы с понятием кеша в памяти?

Тео: Вы имеете в виду мемоизацию (англ. memoization, memory + optimization)?

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

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

Тео: Да, точно!

Джо: Какую структуру данных вы бы использовали для хранения кеша в памяти?

Тео: Наверное, строковую карту, где ключи — это запросы, а значения — это результаты из базы данных.

СОВЕТ. Довольно часто кеш в памяти представляется в виде строковой карты.

Джо: Превосходно! А теперь можете ли вы написать код для кеширования запросов к базе данных потокобезопасным способом, используя блокировку?

212

Часть 2. Масштабируемость

Тео: Дайте подумать: я буду использовать неизменяемую строковую карту. Следовательно, мне не нужно защищать доступ на чтение блокировкой. Необходимо

защитить только обновление кеша.

Джо: Да вы уже прекрасно разбираетесь!

Тео: Код получится примерно такой.

Листинг 8.6. Потокобезопасный кеш с блокировками

var mutex = new Mutex();

var cache = {};

function dbAccessCached(query) {

var resultFromCache = _.get(cache, query);

if (resultFromCache != nil) {

return resultFromCache;

}

var result = dbAccess(query);

mutex.lock();

cache = _.set(cache, query, result);

mutex.unlock();

return result;

}

Джо: Славно! Теперь позвольте мне показать вам, как написать тот же код, используя атом вместо блокировки. Взгляните на него и дайте мне знать, если что-нибудь непонятно.

Листинг 8.7. Потокобезопасный кеш с атомами

var cache = new Atom();

cache.set({});

function dbAccessCached(query) {

var resultFromCache = _.get(cache.get(), query);

if (resultFromCache != nil) {

return resultFromCache;

}

var result = dbAccess(query);

cache.swap(function(oldCache) {

return _.set(oldCache, query, result);

});

return result;

}

Тео: Я не понимаю функцию, которую вы передаете методу swap.

Глава 8. Расширенный контроль конкурентности

213

Джо: Функция, переданная на swap, получает текущее значение кеша, которое является строковой картой, и возвращает новую версию строковой карты с дополнительной парой «ключ-значение».

Тео: Теперь ясно. Но беспокоит вопрос производительности метода swap в случае

строковой карты. Как работает сравнение? Я имею в виду, что сравнение двух

строковых карт может занять много времени.

Джо: Нет, если вы сравниваете их по ссылке. Как мы уже обсуждали, когда данные

неизменяемы, будет безопасно сравнивать с эталоном, а еще это очень быстро.

СОВЕТ. Когда данные неизменяемы, безопасно (и быстро) сравнивать их с эталоном.

Тео: Круто. Получается, что атомы хорошо подходят для работы с неизменяемыми

данными.

Джо: Абсолютно верно!

8.4. Управление состоянием

с помощью атомов

Джо: Помните, как пару недель назад я показывал вам, как можно разрешать по-тенциальные конфликты между изменяемостями? Вы тогда говорили, что код не

получился потокобезопасным.

Тео: Давайте еще раз посмотрим на тот код.

Тео просматривает код для класса systemData, который он написал некоторое время

назад (повторяется в листинге 8.8). Без логики валидации код будет проще для понимания.

Листинг 8.8. Класс SystemData из части 1

class SystemState {

systemData;

get() {

return this.systemData;

}

set(_systemData) {

this.systemData = _systemData;

}

commit(previous, next) {

this.systemData =

SystemConsistency.reconcile(this.systemData,

previous,

next);

}

}

214

Часть 2. Масштабируемость

Через несколько минут он вспоминает, как работает метод commit. Внезапно у него

появляется желание воскликнуть «Эврика!»

Тео: А ведь этот код не является потокобезопасным, потому что код SystemConsistency.

reconcile внутри метода commit не защищен. Ничего не мешает двум потокам

выполнять этот код одновременно.

Джо: Так точно! Теперь скажите мне, как сделать этот код потокобезопасным?

Тео: С блокировками?

Джо: Да что вы...

Тео: Шучу, шучу. Мы сделаем код потокобезопасным не с помощью блокировки, а

с помощью атома.

Джо: Вы меня разыграли!

Тео: Итак, мне бы следовало хранить системные данные внутри атома. Методы get и set класса systemData возьмут и вызовут методы get и set атома. Нормально?

Листинг 8.9. Класс systemData с атомом (без метода commit)

class SystemState {

systemData;

constructor() {

this.systemData = new Atom();

}

get() {

return this.systemData.get();

}

commit(prev, next) {

this.systemData.set(next);

}

}

Джо: Превосходно. Теперь самое интересное: реализуйте метод commit, вызвав метод swap атома.

Тео: Вместо того чтобы вызывать функцию SystemConsistency.concircate() напрямую, мне нужно обернуть ее в вызов swap. Вот так нормально?

Листинг 8.10. Реализация systemData.commit с помощью атома

SystemData.commit = function(previous, next) {

this.systemData.swap(function(current) {

return SystemConsistency.reconcile(current,

previous,

next);

});

};

Глава 8. Расширенный контроль конкурентности

215

Джо: Мне нечего добавить!

Тео: Из-за всей этой истории с атомом я снова вспоминаю о том, что случилось

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

Джо: Что вы имеете в виду?

Тео: Не знаю, но у меня сложилось впечатление, что мьютексы похожи на теле-фонные звонки, а атомы — на текстовые сообщения.

Джо улыбается Тео, но не раскрывает значения своей улыбки. После вчерашней

телефонной взаимоблокировки Тео почти уверен, что они с Джо на одной волне.

Итоги

Управлять конкурентностью при помощи атомов намного проще, чем при помощи блокировок, потому что отсутствуют риски возникновения взаимоблокировок.

Клонирование данных во избежание блокировок чтения не масштабируется.

Когда данные неизменяемы, чтение всегда безопасно.

Атомы предоставляют способ управления конкурентностью без блокировок.

С атомами взаимоблокировок не бывает никогда.

Использование атомов для потокобезопасного счетчика тривиально, поскольку

состояние счетчика представлено примитивным типом (целым числом).

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

с помощью атомов.

Высокомасштабируемый подход к управлению состоянием из части 1 можно

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

Довольно часто кеш в памяти представляется в виде строковой карты.

Когда данные неизменяемы, безопасно (и быстро) сравнивать с эталоном.

В теории атомы могут вызвать голодание в системе с тысячами потоков, которые не занимаются ничем, кроме обмена атомов.

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

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

216

Часть 2. Масштабируемость

Персистентные структуры данных

Стоя на плечах у гигантов

В ЭТОЙ ГЛАВЕ РАССМАТРИВАЮТСЯ

Внутренние подробности о персистентных структурах данных.

Эффективность персистентных структур данных с точки зрения

времени и памяти.

Использование персистентных структур данных в приложении.

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

использования. В этой главе мы представляем более безопасный и масштабируемый способ сохранения неизменяемости данных: представление данных с помощью так называемых персистентных структур данных. Эффективные имплементации персистентных структур данных с помощью сторонних библиотек существуют для большинства языков программирования.

9.1. Потребность

в персистентных структурах данных

На этот раз Тео встречается с Джо в университете. Тео спрашивает, является ли

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

Фил Бэгвелл1.

1 Бэгвелл Ф. Идеальные хеш-деревья (№ REP_WORK), 2001. Статья доступна по ссылке: https://lampwww.epfl.ch/papers/idealhashtrees.pdf.

218

Часть 2. Масштабируемость

В 2007 году Рич Хикки, создатель Clojure, использовал это открытие в качестве основы для персистентных структур данных в этом языке программирования. Джо

решил раскрыть Тео секреты этих структур данных в университетской аудитории, чтобы почтить память Фила Бэгвелла, который, к сожалению, скончался в 2012 го-ду. Когда они добрались до нужной аудитории, Джо начал разговор с вопроса.

Джо: Ну как, вы привыкаете к запрету ДОП на изменение данных на месте с созданием вместо этого новых версий?

Тео: Я думаю, что да, но две вещи беспокоят меня в концепции структурного совместного использования, которую вы мне показали.

Джо: Что вас беспокоит, друг мой?

Тео: Безопасность и производительность.

Джо: Что вы подразумеваете под безопасностью?

Тео: Я говорю о том, что использование неизменяемых функций для манипулирования данными не предотвращает случайные изменения в них.

Джо: Это правда! Какой способ справиться с неизменяемостью вам показать: простой до безобразия или реальный?

Тео: Каковы плюсы и минусы каждого из способов?

Джо: Простой до безобразия способ легок в применении, но неэффективен, а

реальный способ эффективен, но нелегок.

Тео: Тогда давайте начнем с простого до безобразия.

Джо: Каждый язык программирования предоставляет свой собственный способ защиты данных от изменения.

Тео: Как это сделать, например, на Java?

Джо: Java предоставляет неизменяемые коллекции и способ преобразовать список

или карту в неизменяемый список или неизменяемую карту.

ПРИМЕЧАНИЕ. Неизменяемые коллекции — это не то же самое, что персистентные

структуры данных.

Джо открывает свой ноутбук и включает его. Он показывает два примера кода: один для неизменяемых списков и один для неизменяемых карт.

Листинг 9.1. Преобразование изменяемого списка в неизменяемый список в Java var myList = new ArrayList<Integer>();

myList.add(1);

myList.add(2);

myList.add(3);

var myImmutableList = List.of(myList.toArray());

Глава 9. Персистентные структуры данных

219

Листинг 9.2. Преобразование изменяемой карты в неизменяемую карту в Java var myMap = new HashMap<String, Object>();

myMap.put("name", "Isaac");

myMap.put("age", 42);

var myImmutableMap = Collections.unmodifiableMap(myMap);

Тео: Что происходит, когда мы пытаемся изменить неизменяемую коллекцию?

Джо: Java выдает исключение UnsupportedOperationException.

Тео: А в JavaScript?

Джо: JavaScript предоставляет функцию Object.freeze(), которая предотвращает

изменение данных. Она работает как с массивами JavaScript, так и с объектами.

В течение минуты Джо ищет что-то на своем ноутбуке. Когда он находит то, что

искал, он показывает Тео код.

Листинг 9.3. Создание неизменяемого объекта в JavaScript

var a = [1, 2, 3];

Object.freeze(a);

var b = {foo: 1};

Object.freeze(b);

Тео: Что происходит, когда мы пытаемся изменить «замороженный» объект?

Джо: Это зависит от обстоятельств. В строгом режиме JavaScript выдается исключение TypeError, а в нестрогом режиме изменение замороженного объекта завершается тихим сбоем.

ПРИМЕЧАНИЕ. Строгий режим JavaScript — это способ выбрать ограниченный вариант

JavaScript, который превращает некоторые тихие ошибки в ошибки, которые выдаются.

Тео: А если говорить о вложенных коллекциях, будут ли такие коллекции также

замороженными?

Джо: Нет, но в JavaScript можно написать функцию DeepFreeze(), которая рекурсивно замораживает объект. Вот еще один пример.

Листинг 9.4. Рекурсивное замораживание объекта в JavaScript

function deepFreeze(object) {

// Retrieve the property names defined on object

const propNames = Object.getOwnPropertyNames(object);

// Freeze properties before freezing self

for (const name of propNames) {

const value = object[name];

220

Часть 2. Масштабируемость

if (value && typeof value === "object") {

deepFreeze(value);

}

}

return Object.freeze(object);

}

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

СОВЕТ. Можно и вручную убедиться, что данные не изменяются, но этот способ очень

громоздкий.

Джо: Слушаю.

Тео: Если я правильно понял, основная идея структурного совместного использования заключается в том, что наибольшая часть данных используется совместно

двумя версиями.

Джо: Верно.

Тео: Держа это в уме, можно создавать новые версии коллекций с использованием

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

Джо: Точно!

Тео: Итак, вот что меня беспокоит. Если у нас есть коллекция с большим количеством записей, поверхностная копия может оказаться дорогостоящей.

Джо: Не могли бы вы привести пример коллекции с большим количеством записей?

Тео: Допустим, каталог со 100 000 книг.

Джо: На моем компьютере создание неглубокой копии коллекции из 100 000 записей занимает не более 50 миллисекунд.

Тео: Иногда даже 50 миллисекунд на обновление — это неприемлемо.

Джо: Я с вами полностью согласен. Когда неизменяемость данных требуется

в масштабе, до безобразия простое структурное совместное использование не

подходит.

Тео: А еще неглубокое копирование массива из 100 000 элементов при каждом обновлении увеличит объем памяти программы на 100 КБ.

Джо: Действительно, в масштабе у нас есть проблема как с памятью, так и с вычис-лениями.

СОВЕТ. До безобразия простое структурное совместное использование в масштабе

приводит к снижению производительности, как с точки зрения памяти, так и вычислений.

Тео: Нет ли решения получше?

Глава 9. Персистентные структуры данных

221

Джо: Есть! Для этого вам нужно изучить реальный способ обращения с неизменяемостью. Он называется персистентными структурами данных.

9.2. Эффективность

персистентных структур данных

Тео: В каком смысле эти структуры данных являются персистентными?

Джо: Персистентные структуры данных названы так потому, что они всегда сохраняют свои предыдущие версии.

СОВЕТ. Персистентные структуры данных всегда сохраняют предыдущую версию самих

себя при изменении.

Джо: Персистентные структуры данных устраняют две основные проблемы простого до безобразия структурного совместного использования: проблемы безопасности и производительности.

Тео: Давайте начнем с безопасности. Как персистентные структуры данных пре-дотвращают случайное изменение данных?

Джо: В таком языке, как Java они реализуют методы изменения интерфейсов коллекции, вызывая исключение времени выполнения UnsupportedOperationException.

Тео: А в таком языке, как JavaScript?

Джо: В JavaScript персистентные структуры данных предоставляют свои собственные методы для доступа к данным, и ни один из этих методов не изменяет данные.

Тео: Означает ли это, что мы не можем использовать точечную нотацию для доступа к полям?

Джо: Да, означает. Доступ к полям персистентных структур данных осуществляется через определенный API.

Тео: А как насчет эффективности? Как персистентные структуры данных позволяют эффективно создать новую версию огромной коллекции?

Джо: Персистентные структуры данных организуют данные таким образом, что

становится возможным использование структурного совместного использования

на уровне структуры данных.

Тео: Не могли бы вы это объяснить?

Джо: Конечно. Давайте начнем с самой простой структуры данных: связанного

списка. Представьте, что у вас есть связанный список из 100 000 элементов.

Тео: Хорошо.

Джо: Что нужно сделать, чтобы добавить элемент в начало списка?

Тео: Вы имеете в виду создать новую версию списка с дополнительным элементом?

Джо: Ага!

222

Часть 2. Масштабируемость

Тео: Ну, можно скопировать список, а затем добавить элемент в начало списка, но

этот метод довольно дорогостоящий.

Джо: А что если я скажу вам, что исходный связанный список — гарантированно

неизменяемый?

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

Тео подходит к классной доске. Он берет кусок мела и рисует схему, показанную

на рис. 9.1.

Рис. 9.1. Структурное совместное использование со связанными списками

Джо: Будет ли эффективность этой операции зависеть от размера списка?

Тео: Нет, операция будет эффективна независимо от размера списка.

Джо: Это то, что я подразумеваю под структурным совместным использованием на

уровне самой структуры данных. Этот способ основан на простом, но могущест-венном знании: когда данные неизменяемы, ими можно безопасно пользоваться

совместно.

СОВЕТ. Когда данные неизменяемы, ими можно безопасно пользоваться совместно.

Тео: Я понял, как работает структурное совместное использование на уровне

структуры данных для связанных списков и операций добавления в начало списка, но как оно будет работать с такими операциями, как добавление элемента

или изменение элемента в списке?

Джо: Для этой цели нам нужно действовать хитрее и представить наш список в виде

дерева.

Тео: А как это поможет?

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

Тео: Я в полном замешательстве.

Джо: Представьте, что вы взяли список из 100 000 элементов и разделили его на

два списка по 50 000 элементов в каждом: элементы от 0 до 49 999 — в списке 1

и элементы от 50 000 до 99 999 — в списке 2. Сколько операций вам потребуется, чтобы создать новую версию списка, в которой изменен один элемент, допустим, элемент с индексом 75 100?

Тео затрудняется мысленно представить себе нечто подобное. Он возвращается

к доске и рисует диаграмму (рис. 9.2). Как только Тео взглянул на получившуюся

у него диаграмму, он смог с легкостью ответить на вопрос Джо.

Глава 9. Персистентные структуры данных

223

Рис. 9.2. Структурное совместное использование при разделении списка из 100 000 элементов

Тео: Список 1 может быть совместно использован с помощью одной операции.

Мне нужно будет создать новую версию списка 2, где изменен элемент 75 100.

Это займет 50 000 операций, так что всего получается одна операция доступа

к совместному использованию и одна операция копирования 50 000 элементов.

В целом у нас будет 50 001 операция.

Джо: Верно. Как видите, разделив наш исходный список на два списка, мы можем

создать новую версию списка при помощи ряда операций в количестве, равном

размеру списка, разделенному на 2.

Тео: Я согласен, но 50 000 — это все еще большая цифра.

Джо: Действительно, но никто не мешает нам снова применить тот же трюк, разделив список 1 и список 2 еще на два списка каждый.

Тео: Как именно?

Джо: Мы можем составить список 1.1 с элементами от 0 до 24 999, затем список 1.2

с элементами от 25 000 до 49 999, далее список 2.1 с элементами от 50 000 до

74 999 и список 2.2 с элементами от 75 000 до 99 999.

Тео: Вы можете нарисовать это на доске?

Джо: Конечно.

Теперь к доске подходит Джо. Он рисует диаграмму, как на рис. 9.3.

Рис. 9.3. Структурное совместное использование

при двукратном разделении списка из 100 000 элементов

224

Часть 2. Масштабируемость

Тео: Дайте-ка я подсчитаю количество операций для обновления одного элемента.

Требуется две операции доступа к совместному использованию и одна операция

копирования 25 000 элементов. В целом для создания новой версии списка требуется 25 002 операции.

Джо: Все верно!

Тео: Тогда давайте разделим список еще раз!

Джо: Обязательно. На самом деле мы можем разбивать список снова и снова, пока

размер списков не станет не более 2. Можете ли вы догадаться, какова тогда

будет сложность создания новой версии?

Тео: Я бы сказал, около log2 N операций.

Джо: Я вижу, вы хорошо помните школьный курс математики. Сможете ли вы

представить себе, чему будет равен log2 N, когда N равно 100 000?

Тео: Дайте-ка подумать... 2 в степени 10 — это около 1000, а 2 в степени 7 — это

128. Таким образом, ответ должен быть немного меньше 17.

Джо: Ответ будет 16,6, если быть точным. Это означает, что, для того чтобы обновить элемент в персистентном списке из 100 000 элементов, нам потребуется

около 17 операций. То же самое касается доступа к элементам.

Тео: Неплохо, но 17 — это такое значение, которым все же нельзя пренебречь.

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

Тео: Что вы имеете в виду?

Джо: Вместо того, чтобы делить на 2 на каждом уровне, мы можем делить на 32.

Тео: Но время выполнения нашего алгоритма все равно будет расти с логарифмом

числа N.

Джо: Вы правы. С теоретической точки зрения это одно и то же. Однако с практи-ческой точки зрения разница будет велика.

Тео: Почему?

Джо: Потому что логарифм числа N по основанию 32 в 5 раз меньше, чем логарифм N по основанию 2.

Тео: Это верно: 2 в степени 5 равно 32.

Джо: Возвращаясь к нашему списку из 100 000 элементов, не могли бы вы сказать

мне, сколько операций требуется для доступа к элементу, если коэффициент

ветвления равен 32?

Тео: С коэффициентом ветвления 2 ответ был равен 16,6. Если я разделю 16,6 на 5, то получу 3,3.

Джо: Правильно!

СОВЕТ. Используя коэффициент ветвления 32, мы повышаем эффективность доступа

к элементам в персистентных списках.

Глава 9. Персистентные структуры данных

225

Тео: А улучшает ли этот трюк также и производительность обновления элемента

в списке?

Джо: Да, еще как улучшает.

Тео: А как именно? Нам придется копировать 32 элемента на каждом уровне вместо 2 элементов. Это 16-кратный прирост производительности, который не компенсируется тем фактом, что глубина дерева уменьшена в 5 раз!

Джо: Я вижу, вы неплохо считаете! Есть еще одна вещь, которую следует принять

во внимание при практическом анализе производительности: архитектура современного процессора.

Тео: Интересно. Чем больше вы рассказываете мне о персистентных структурах

данных, тем больше я понимаю, почему вы захотели провести эту встречу

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

Джо: Да. Итак, продолжим. Современные процессоры считывают и записывают

данные из основной памяти и в нее единицами строк кеша часто длиной в 32 или

64 байта.

Тео: И как это влияет на производительность?

Джо: Приятным следствием этого шаблона доступа к данным является то, что копирование одного массива размером в 32 байта выполняется намного быстрее, чем копирование 16 массивов размером в 2 байта, принадлежащих разным уровням дерева.

Тео: А почему так?

Джо: Причина в том, что копирование массива размером в 32 байта может быть

выполнено за одну пару обращений к кешу: одно для чтения и одно для записи.

А вот для массивов, принадлежащих разным уровням дерева, каждому массиву

требуется своя собственная пара обращений к кешу, даже если в массиве всего

2 элемента.

Тео: Другими словами, производительность обновления персистентного списка

в большой степени зависит от глубины дерева.

СОВЕТ. В архитектурах современных процессоров производительность обновления

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

Джо: Это верно до некоторой степени. Использование коэффициента ветвления 64

при современных процессорах на самом деле снизит производительность операций обновления.

Тео: Понятно.

Джо: Теперь я сделаю еще одно интересное утверждение, которое не является точным с теоретической точки зрения, но будет точным на практике.

Тео: Что за утверждение?

Джо: Количество операций, необходимых для получения или обновления элемента

в персистентном списке с коэффициентом ветвления 32, является постоянным.

226

Часть 2. Масштабируемость

Тео: Как такое может быть? Вы ведь только что сказали, что количество операций

равно логарифму числа N по основанию 32.

Джо: Имейте терпение, друг мой. Каково наибольшее количество элементов, которое может включать в себя список на практике?

Тео: Я не знаю. Никогда об этом не думал.

Джо: Давайте предположим, что для хранения одного элемента в списке требуется

4 байта.

Тео: ОК.

Джо: А теперь скажите, пожалуйста, сколько памяти потребуется для хранения

списка из 10 миллиардов элементов?

Тео: Вы имеете в виду число в виде единицы с 10 нулями?

Джо: Да.

Тео: Каждый элемент занимает 4 байта, так что получится около 40 ГБ!

Джо: Верно. Согласны ли вы с тем, что не имеет смысла хранить список, который

занимает 40 ГБ памяти?

Тео: Согласен.

Джо: Итак, давайте возьмем 10 миллиардов в качестве верхней границы количества

элементов в списке. Чему будет равен логарифм 10 миллиардов по основанию 2?

Тео снова использует классную доску, чтобы прояснить свои мысли. Так он быстро

находит ответ.

Тео: Один миллиард — это примерно 230. Следовательно, 10 миллиардов — это

примерно 233. Это означает, что логарифм 10 миллиардов по основанию 2 равен 33, значит, логарифм 10 миллиардов по основанию 32 должен быть примерно 33/5, что немного меньше 7.

Джо: Я снова впечатлен вашими математическими способностями. Если быть точным, логарифм 10 миллиардов по основанию 32 равен 6,64.

Тео (улыбаясь): Так точно я считать не стал.

Джо: Убедил ли я вас в том, что на практике доступ к элементу в персистентном

списке или его обновление по существу являются постоянными?

Тео: Да, и это просто потрясающе!

СОВЕТ. Персистентными списками можно манипулировать за время, приближенное к по-стоянному.

Джо: Я тоже так думаю.

Тео: А что насчет персистентных карт?

Джо: Будет очень похоже, но я думаю, что у нас сейчас нет времени это обсуждать.

Внезапно Тео посмотрел на свои часы. Сегодняшняя утренняя встреча пролетела

очень быстро. Он заметил, что пора возвращаться в офис и обедать.

Глава 9. Персистентные структуры данных

227

9.3. Библиотеки

персистентных структур данных

По пути в офис Тео и Джо почти совсем не разговаривают. Мысли Тео возвращают

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

уважением к Филу Бэгвеллу, который обнаружил, как можно эффективно манипулировать персистентными структурами данных, и к Ричу Хикки, который создал

язык программирования, включивший это открытие в качестве основной функции и

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

данных в каком-нибудь языке программирования.

Тео: Доступны ли персистентные структуры данных на всех языках программирования?

Джо: Несколько языков программирования, таких как Clojure, Scala и C#, предоставляют их как часть языка. Однако в большинстве языков вам понадобится сторонняя библиотека.

Тео: Не могли бы вы дать рекомендации?

Джо: Конечно.

Используя ноутбук Тео, Джо добавляет в закладки несколько сайтов. Он точно знает, по каким ссылкам нужно переходить. Затем, пока Тео просматривает эти сайты, Джо подходит к доске и записывает информацию о библиотеках в табл. 9.1.

Immutable.js для JavaScript по ссылке https://immutable-js.com/.

Paguro для Java по ссылке https://github.com/GlenKPeterson/Paguro.

Immutable Collections для C# по ссылке http://mng.bz/QW51.

Pyrsistent для Python по ссылке https://github.com/tobgu/pyrsistent.

Hamster для Ruby по ссылке https://github.com/hamstergem/hamster.

Таблица 9.1. Библиотеки персистентных структур данных

Язык Библиотека

JavaScript Immutable.js

Java Paguro

C# Предоставляется

языком

Python Pyrsistent

Ruby Hamster

Тео: Что требуется для интеграции персистентных структур данных, предоставляемых сторонней библиотекой, в наш код?

228

Часть 2. Масштабируемость

9.3.1. Персистентные структуры данных в Java

Джо: В объектно-ориентированном языке, таком как Java, довольно просто интегрировать в программу персистентные структуры данных, потому что такие

структуры данных реализуют интерфейсы коллекций, помимо частей интерфейса, которые изменяются на месте.

Тео: Что вы имеете в виду?

Джо: Возьмем, к примеру, библиотеку Paguro для Java. Персистентные карты Paguro реализуют доступные только для чтения методы java.util.Map, такие как get() и

containsKey(), но не такие методы, как put() и remove(). С другой стороны, векторы Paguro реализуют доступные только для чтения методы java.util.List, такие как get() и size(), но не set().

Тео: Что произойдет, когда мы вызовем put() или remove() на карте Paguro?

Джо: Выдается исключение UnSupportedOperationException.

Тео: А что насчет итерации элементов коллекции Paguro с помощью forEach()?

Джо: Это работает так же, как и в любой коллекции Java. Позвольте-ка мне показать вам пример.

Листинг 9.5. Итерация по вектору Paguro

var myVec = PersistentVector.ofIter(

List.of(10, 2, 3)); ❶

for (Integer i : myVec) {

System.out.println(i);

}

❶ Создает вектор Paguro из списка Java.

Тео: А как насчет потоков Java?

Джо: Коллекции Paguro — это коллекции Java, поэтому они поддерживают интерфейс потоков Java. Взгляните на этот код.

Листинг 9.6. Потоковая передача вектора Paguro

var myVec = PersistentVector.ofIter(List.of(10, 2, 3));

vec1.stream().sorted().map(x -> x + 1);

СОВЕТ. Коллекции Paguro реализуют доступные только для чтения части интерфейсов

коллекций Java. Следовательно, они могут быть переданы любым методам, которые ожидают получения коллекции Java без ее изменения.

Тео: Итак, вы рассказали мне, как использовать коллекции Paguro в качестве коллекций Java, доступных только для чтения. А как вносить изменения в персистентные структуры данных Paguro?

Глава 9. Персистентные структуры данных

229

Джо: Способом, аналогичным функции _.set() из Lodash FP, о которой мы говорили ранее. Вместо того чтобы мутировать на месте, создается новая версия.

Тео: Какие методы предоставляет Paguro для создания новых версий структуры

данных?

Джо: Для векторов используется replace(), а для карт используется assoc().

Листинг 9.7. Создание модифицированной версии вектора Paguro

var myVec = PersistentVector.ofIter(List.of(10, 2, 3));

var myNextVec = myVec.replace(0, 42);

Листинг 9.8. Создание модифицированной версии карты Paguro

var myMap = PersistentHashMap.of(Map.of("aa", 1, "bb", 2)

.entrySet()); ❶

var myNextMap = myMap.assoc("aa", 42);

❶ Создает карту Paguro из набора записей карты Java.

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

в Java, но как насчет JavaScript?

9.3.2. Персистентные структуры данных

в JavaScript

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

Тео: Как же так?

Джо: Дело в том, что объекты и массивы JavaScript не предоставляют интерфейса.

Тео: Облом.

Джо: Это не так ужасно, как кажется, потому что коллекции Immutable.js предоставляют свой собственный набор функций для манипулирования структурами

данных.

Тео: Что вы имеете в виду?

Джо: Сейчас скажу. Но сначала позвольте мне показать вам, как инициировать

персистентные структуры данных в Immutable.js.

Тео: Ладно!

Джо: Immutable.js предоставляет удобную функцию, которая рекурсивно конвертирует нативный объект данных в неизменяемый. Она называется Immutable.

fromJS().

230

Часть 2. Масштабируемость

Тео: Что вы подразумеваете под рекурсивным конвертированием?

Джо: Представьте себе карту, в которой хранятся библиотечные данные из нашей

Системы управления библиотекой: у такой карты есть значения, которые сами

по себе являются картами. Функция Immutable.fromJS() конвертирует вложенные

карты в неизменяемые карты.

Тео: Покажите, пожалуйста, код.

Джо: Безусловно. Взгляните на этот код JavaScript для библиотечных данных.

Листинг 9.9. Конвертирование в неизменяемые данные

var libraryData = Immutable.fromJS({

"catalog": {

"booksByIsbn": {

"978-1779501127": {

"isbn": "978-1779501127",

"title": "Watchmen",

"publicationYear": 1987,

"authorIds": ["alan-moore",

"dave-gibbons"]

}

},

"authorsById": {

"alan-moore": {

"name": "Alan Moore",}

"bookIsbns": ["978-1779501127"]

},

"dave-gibbons": {

"name": "Dave Gibbons",

"bookIsbns": ["978-1779501127"]

}

}

}

});

Тео: Вы имеете в виду, что значение catalog в карте libraryData само по себе является неизменяемой картой?

Джо: Да, и то же самое является правдой для booksByIsbn, authorIds и т. д.

Тео: Круто! Итак, как же получить доступ к полю внутри неизменяемой карты?

Джо: Как я уже говорил, Immutable.js предоставляет свой собственный API для

доступа к данным. Например, чтобы получить доступ к полю внутри неизменяемой карты, нужно использовать Immutable.get() или Immutable.getIn(), как

показано ниже (листинг 9.10).

Глава 9. Персистентные структуры данных

231

Листинг 9.10. Доступ к полю и вложенному полю в неизменяемой карте

Immutable.get(libraryData, "catalog");

Immutable.getIn(libraryData,

["catalog", "booksByIsbn", "978-1779501127", "title"]);

// → "Watchmen"

Тео: А как внести изменения в карту?

Джо: Аналогично тому, что мы делали с Lodash FP: нужно использовать карту

Immutable.set() или Immutable.setIn() для создания новой версии карты, в которой изменено поле. И вот как это делается.

Листинг 9.11. Создание новой версии карты, в которой изменено поле

Immutable.setIn(libraryData,

["catalog", "booksByIsbn",

"978-1779501127", "publicationYear"],

1988);

Тео: Что произойдет, если попытаться получить доступ к полю в карте, используя

точки или скобки — условные обозначения из JavaScript?

Джо: Вы получите доступ к внутреннему представлению карты вместо доступа

к полю карты.

Тео: Означает ли это, что невозможно передать данные из Immutable.js в Lodash для манипулирования ими?

Джо: Да, но довольно легко преобразовать любую неизменяемую коллекцию в нативный объект JavaScript и обратно.

Тео: Как?

Джо: Immutable.js предоставляет метод toJS() для преобразования произвольной

глубоко вложенной неизменяемой коллекции в объект JavaScript.

Тео: Но если у меня огромная коллекция, на ее преобразование может уйти много

времени, верно?

Джо: Точно. Нам нужно решение получше. Надеюсь, Immutable.js предоставляет

свой собственный набор функций для манипулирования данными, таких как

map(), filter() и reduce().

Тео: А что если мне понадобится еще больше возможностей манипулирования

данными, вроде, например, _.groupBy() из Lodash?

Джо: Тогда можно написать свои собственные функции для манипулирования данными, которые работают с коллекциями Immutable.js, или использовать библиотеку вроде mudash, которая предоставляет возможность переноса из Lodash в Immutable.js.

ПРИМЕЧАНИЕ. Вы можете получить доступ к библиотеке mudash по адресу

https://github.com/brianneisler/mudash.

232

Часть 2. Масштабируемость

Тео: А что бы вы посоветовали?

Джо: Выпить чашку кофе, а после я покажу вам, как перенести функции из Lodash в Immutable.js и как адаптировать код из вашей Системы управления библиотекой. Вы сможете выбрать тот подход, который лучше всего подходит для вашего

текущего проекта.

9.4. Персистентные структуры данных

в действии

Джо: Давайте начнем с поискового запроса. Не могли бы вы взглянуть на текущий

код и рассказать мне о функциях Lodash, которые мы использовали для реализации поискового запроса?

Тео: Включая код для модульных тестов?

Джо: Конечно!

ПРИМЕЧАНИЕ. Модульный тест поискового запроса приведен в главе 6.

9.4.1. Написание запросов с персистентными

структурами данных

Тео: Функциями Lodash, которые мы использовали, были get, map, filter и isEqual.

Джо: Вот пример переноса этих четырех функций из Lodash в Immutable.js.

Листинг 9.12. Перенос некоторых функций из Lodash в Immutable.js

Immutable.map = function(coll, f) {

return coll.map(f);

};

Immutable.filter = function(coll, f) {

if(Immutable.isMap(coll)) {

return coll.valueSeq().filter(f);

}

return coll.filter(f);

};

Immutable.isEqual = Immutable.is;

Тео: Код выглядит довольно простым. Но все же не могли бы вы объяснить его

мне, функция за функцией?

Джо: Конечно. Давайте начнем с get. Для доступа к полю на карте Immutable.js предоставляет две функции: get для прямых полей и getIn для вложенных полей.

В этом заключается отличие от Lodash, где _.get работает как с прямыми, так и

с вложенными полями.

Глава 9. Персистентные структуры данных

233

Тео: А что насчет map?

Джо: Immutable.js предоставляет свою собственную функцию map. Единственное

отличие заключается в том, что это метод коллекции, но его можно легко адаптировать.

Тео: А что насчет filter? Как сделать так, чтобы эта функция работала как для

массивов, так и для карт, таких как filter из Lodash?

Джо: Immutable.js предоставляет метод valueSeq, который возвращает значения карты.

Тео: Круто. А что насчет isEqual для сравнения двух коллекций?

Джо: Это очень просто. Immutable.js предоставляет функцию под названием is, которая работает точно так же, как isEqual.

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

поискового запроса работать с Immutable.js?

Джо: Нужно просто заменить каждый из символов подчеркивания «_» на слово

«Immutable»; _.map становится Immutable.map, _.filter становится Immutable.filter, и _.isEqual становится Immutable.isEqual.

Тео: Поверить не могу, что это так просто!

Джо: А вы сами попробуйте, и все увидите. Иногда код может получиться громоздким, потому что нужно преобразовывать объекты JavaScript в объекты

Immutable.js, используя Immutable.fromJS.

Тео копирует и вставляет фрагменты кода и модульные тесты для поискового запроса. Затем он использует свою IDE, чтобы заменить символ «_» на слово

«Immutable». Когда Тео выполняет тесты, и они проходят успешно, он удивлен, но

доволен. Джо улыбается.

Листинг 9.13. Реализация поиска книг

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

class Catalog {

static authorNames(catalogData, authorIds) {

return Immutable.map(authorIds, function(authorId) {

return Immutable.getIn(

catalogData,

["authorsById", authorId, "name"]);

});

}

static bookInfo(catalogData, book) {

var bookInfo = Immutable.Map({

"title": Immutable.get(book, "title"),

"isbn": Immutable.get(book, "isbn"),

"authorNames": Catalog.authorNames(

catalogData,

Immutable.get(book, "authorIds"))

});

234

Часть 2. Масштабируемость

return bookInfo;

}

static searchBooksByTitle(catalogData, query) {

var allBooks = Immutable.get(catalogData, "booksByIsbn"); var queryLowerCased = query.toLowerCase();

var matchingBooks = Immutable.filter(allBooks,

function(book) {

return Immutable.get(book, "title").

toLowerCase().

Includes(queryLowerCased);

});

var bookInfos = Immutable.map(matchingBooks, function(book) {

return Catalog.bookInfo(catalogData, book);

});

return bookInfos;

}

}

Листинг 9.14. Тестирование поиска книг

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

var catalogData = Immutable.fromJS({

"booksByIsbn": {

"978-1779501127": {

"isbn": "978-1779501127",

"title": "Watchmen",

"publicationYear": 1987,

"authorIds": ["alan-moore",

"dave-gibbons"]

}

},

"authorsById": {

"alan-moore": {

"name": "Alan Moore",

"bookIsbns": ["978-1779501127"]

},

"dave-gibbons": {

"name": "Dave Gibbons",

"bookIsbns": ["978-1779501127"]

}

}

});

var bookInfo = Immutable.fromJS({

"isbn": "978-1779501127",

"title": "Watchmen",

Глава 9. Персистентные структуры данных

235

"authorNames": ["Alan Moore",

"Dave Gibbons"]

});

Immutable.isEqual(

Catalog.searchBooksByTitle(catalogData, "Watchmen"),

Immutable.fromJS([bookInfo]));

// → true

Immutable.isEqual(

Catalog.searchBooksByTitle(catalogData, "Batman"),

Immutable.fromJS([]));

// → true

9.4.2. Операции изменения

при работе с персистентными структурами данных

Тео: Давайте пойдем дальше и перенесем изменение для добавления читателя библиотеки.

Джо: Конечно. Чтобы перенести изменение для добавления читателя библиотеки из

Lodash в Immutable.js, требуется всего лишь снова заменить символ подчеркивания «_» на слово «Immutable». Давайте взглянем на фрагмент кода.

Листинг 9.15. Реализация добавления читателей библиотеки

с помощью персистентных структур данных

UserManagement.addMember = function(userManagement, member) {

var email = Immutable.get(member, "email");

var infoPath = ["membersByEmail", email];

if(Immutable.hasIn(userManagement, infoPath)) {

throw "Member already exists.";

}

var nextUserManagement = Immutable.setIn(userManagement,

infoPath,

member);

return nextUserManagement;

};

Тео: Итак, для тестов нужно будет преобразовать объекты JavaScript в объекты

Immutable.js, используя Immutable.fromJS. Нормально получается?

Листинг 9.16. Тестирование добавления нового читателя библиотеки

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

var jessie = Immutable.fromJS({

"email": "[email protected]",

"password": "my-secret"

});

236

Часть 2. Масштабируемость

var franck = Immutable.fromJS({

"email": "[email protected]",

"password": "my-top-secret"

});

var userManagementStateBefore = Immutable.fromJS({

"membersByEmail": {

"[email protected]": {

"email": "[email protected]",

"password": "my-top-secret"

}

}

});

var expectedUserManagementStateAfter = Immutable.fromJS({

"membersByEmail": {

"[email protected]": {

"email": "[email protected]",

"password": "my-secret"

},

"[email protected]": {

"email": "[email protected]",

"password": "my-top-secret"

}

}

});

var result = UserManagement.addMember(userManagementStateBefore, jessie); Immutable.isEqual(result, expectedUserManagementStateAfter);

// → true

Джо: Великолепно!

9.4.3. Сериализация и десериализация

Тео: Поддерживает ли Immutable.js также сериализацию и десериализацию из JSON?

Джо: Эта библиотека поддерживает сериализацию «из коробки». Что касается десериализации, придется написать нашу собственную функцию.

Тео: Предоставляет ли Immutable.js функцию Immutable.stringify()?

Джо: В этом нет необходимости, потому что нативная функция JSON.stringify() работает с объектами Immutable.js. Вот еще один пример.

Листинг 9.17. Сериализация в формате JSON для коллекции Immutable.js var bookInfo = Immutable.fromJS({

"isbn": "978-1779501127",

"title": "Watchmen",

Глава 9. Персистентные структуры данных

237

"authorNames": ["Alan Moore",

"Dave Gibbons"]

});

JSON.stringify(bookInfo);

// → {\"isbn\":\"978-1779501127\",\"title\":\"Watchmen\",

// → \"authorNames\":[\"Alan Moore\",\"Dave Gibbons\"]}

Тео: Откуда функция JSON.stringify() знает, как обрабатывать коллекцию

Immutable.js?

Джо: Как разработчика в сфере объектно-ориентированного программирования, вас не должно это удивлять.

Тео: Хм... Дайте-ка мне немного подумать. Так, вот мое предположение. Это происходит потому, что JSON.stringify() вызывает какой-то метод на свой аргумент?

Джо: Точно! Если объект, переданный функции JSON.stringify(), имеет метод

.toJSON(), он вызывается при помощи JSON.stringify().

Тео: Неплохо. Как насчет десериализации JSON?

Джо: Это делается в два этапа. Сначала вы преобразуете строку JSON в объект

JavaScript, а затем в неизменяемую коллекцию.

Тео: Что-то вроде этого фрагмента кода?

Листинг 9.18. Преобразование строки JSON в неизменяемую коллекцию

Immutable.parseJSON = function(jsonString) {

return Immutable.fromJS(JSON.parse(jsonString));

};

Джо: Точно.

9.4.4. Структурная разница

Тео: Итак, мы уже переносили фрагменты кода, которые содержали простые манипуляции с данными. Интересно посмотреть, как происходит перенос в сложных

случаях манипулирования данными, когда код вычисляет структурную разницу

между двумя картами.

ПРИМЕЧАНИЕ. В главе 5 вводится понятие структурной разницы.

Джо: Здесь все тоже сработает гладко, но придется перенести еще восемь функций.

Листинг 9.19. Перенос функций Lodash,

участвующих в вычислении структурной разницы

Immutable.reduce = function(coll, reducer, initialReduction) {

return coll.reduce(reducer, initialReduction);

};

238

Часть 2. Масштабируемость

Immutable.isEmpty = function(coll) {

return coll.isEmpty();

};

Immutable.keys = function(coll) {

return coll.keySeq();

};

Immutable.isObject = function(coll) {

return Immutable.Map.isMap(coll);

};

Immutable.isArray = Immutable.isIndexed;

Immutable.union = function() {

return Immutable.Set.union(arguments);

};

Тео: Все выглядит безумно просто, за одним исключением: использование аргументов в Immutable.union.

Джо: В JavaScript arguments — это неявный объект, подобный массиву, который

содержит значения аргументов функции.

Тео: Понятно. И снова пример магии JavaScript!

Джо: Ага. Нам нужно использовать объект arguments, потому что в Lodash и

Immutable.js немного отличаются сигнатуры функции union. Функция Immutable.

Set.union получает массив списков, тогда как в Lodash функция_.union получает

несколько массивов.

Тео: Логично. Позвольте мне попробовать.

Подув на пальцы, как опытный взломщик сейфов (сначала на одну руку, а потом на

другую), Тео начинает печатать. И снова он с удивлением обнаруживает, что после

замены символа подчеркивания «_» на слово «Immutable» в листинге 9.20 тесты

в листинге 9.21 проходят успешно.

Листинг 9.20. Реализация структурной разницы

с персистентными структурами данных

function diffObjects(data1, data2) {

var emptyObject = Immutable.isArray(data1) ?

Immutable.fromJS([]) :

Immutable.fromJS({});

if(data1 == data2) {

return emptyObject;

}

Глава 9. Персистентные структуры данных

239

var keys = Immutable.union(Immutable.keys(data1),

return Immutable.reduce(keys,

function (acc, k) {

var res = diff(Immutable.get(data1, k),

Immutable.get(data2, k));

if((Immutable.isObject(res) &&

Immutable.isEmpty(res)) ||

(res == "data-diff:no-diff")) {

return acc;

}

return Immutable.set(acc, k, res);

},

emptyObject);

}

function diff(data1, data2) {

if(Immutable.isObject(data1) && Immutable.isObject(data2)) {

return diffObjects(data1, data2);

}

if(data1 !== data2) {

return data2;

}

return "data-diff:no-diff";

}

Листинг 9.21. Тестирование структурной разницы

с персистентными структурами данных

var data1 = Immutable.fromJS({

g: {

c: 3

},

x: 2,

y: {

z: 1

},

w: [5]

});

var data2 = Immutable.fromJS({

g: {

c:3

},

x: 2,

y: {

z: 2

},

w: [4]

});

240

Часть 2. Масштабируемость

Immutable.isEqual(diff(data1, data2),

Immutable.fromJS({

"w": [

4

],

"y": {

"z": 2

}

}));

Джо: И что вы обо всем этом думаете, друг мой?

Тео: Я думаю, что использовать персистентные коллекции данных с библиотекой, подобной Immutable.js, намного проще, чем понять внутренние свойства персистентных структур данных. Но я все же доволен, что знаю, как там все работает

«под капотом».

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

урока о ДОП.

Дейв: Чему тебя сегодня научил Джо?

Тео: Он отвез меня в университет и научил основам персистентных структур данных для работы с неизменяемостью в масштабе.

Дейв: А что не так со структурным совместным использованием, которое я реализовал пару месяцев назад?

Тео: Когда количество элементов в коллекции достаточно велико, простое до безобразия структурное совместное использование приводит к проблемам с производительностью.

Дейв: Понятно. Расскажи-ка подробнее.

Тео: Я бы с удовольствием, но после такого интересного, но утомительного дня

мой мозг отказывается нормально работать. Очень скоро я тебе все расскажу, обещаю.

Дейв: Годится. Приятного тебе вечера, Тео.

Тео: И тебе, Дейв.

Итоги

Можно вручную убедиться, что данные не изменяются, но это громоздко.

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

Простое до безобразия структурное совместное использование не предотвращает случайные изменения в структурах данных.

Неизменяемые коллекции — это не то же самое, что персистентные структуры

данных.

Глава 9. Персистентные структуры данных

241

Неизменяемые коллекции не предоставляют эффективного способа создания

новых версий коллекций.

Отправить