2017-11-12

Об ИИ

Что-то в последнее время меня «покусали» роботы. Немножко пополнил своё представление о нашем с вами ближайшем будущем.
За последние месяцы:
Neurons
Джеф Хокинс (не путать со Стивеном Хокингом) — это чувак, который сделал Palm Pilot, придумал рукописный ввод Graffiti, основал Palm Computing и Handspring. Он делал планшеты ещё тогда, когда они назывались наладонниками. Но, если верить книге, он с детства мечтал разобраться в том, как работает человеческий мозг. Поэтому, заработав достаточно денег в IT сфере, в начале двухтысячных он публикует эту книгу и основывает институт по изучению мозга.
Хокинс критикует существующие направления исследований за то, что они не пытаются создать единую теорию функционирования мозга (точнее его интересует в первую очередь неокортекс). Нейрофизиологи могут сказать, какая часть мозга возбуждается, когда мы видим определённые образы, ощущаем определённые эмоции или думаем о чём-то определённом, но не могут сказать, что это означает. Психологи и психиатры могут сказать, как определённые переживания в прошлом могут сказаться на нашем поведении в будущем, и как избавиться от ненужных переживаний, но не имеют понятия о том, какие физические процессы при этом происходят в мозгу.
Хокинс предлагает объединить усилия и излагает свою теорию функционирования неокортекса. Делает это он из айтишных побуждений, чтобы создать действительно мыслящие машины. Он и направления искусственного интеллекта в связи с этим критикует.
Дело в том, что даже нейронные сети, которые вроде как повторяют структуру мозга, работают не так, как мозг. Нейронные сети сначала обучаются, а потом работают. А мозг постоянно обрабатывает сигналы, и постоянно обучается. Это непрерывный процесс.
По Хокинсу неокортекс — это иерархическая машина узнавания паттернов во входных сигналах и прогнозирования (этих сигналов). Входные сигналы — это сигналы от органов чувств. Ответная реакция мозга — это в первую очередь движения, причём движения глаз, включая саккады, и движения языка и гортани при речи — это всё тоже ответы мозга.
Интересна иерархия. На нижних уровнях распознаются простые вещи: для зрения — линии разных направлений, для слуха — тона звуков. Несколькими уровнями выше распознаются уже целые образы: лица, мелодии. Ещё выше распознаются абстрактные понятия вроде людей, кошек, собак вообще. Где-то на этом уровне появляется то, что мы воспринимаем как наше создание, то есть умение оперировать абстракциями.
Все эти уровни работают одинаково, узнают и предсказывают. Только чем выше по иерархии, тем более абстрактны понятия, которые они узнают и предсказывают. И чем выше по иерархии, тем больше мозготоплива (буквально) требуется для принятия решения и реакции на окружающие взаимодействия, потому что буквально задействовано больше нейронов. Слоёв этих, похоже, что около сотни (исходя из типичного времени реации и типичной скорости распространения нервных импульсов).
Обучение как раз и заключается в том, чтобы перенести возможность принятия решения на более низкие уровни. Довести до автоматизма, выработать привычку. На низком уровне решение принимается быстрее и дешевле. Но работает оно только на заученных паттернах. Если встречается что-то незаученное, приходится задействовать более высокие уровни иерархии, «включать сознание».
Самые нижние слои имеются у всех млекопитающих. Где-то там мы подобны мышкам и ёжикам. У обезьян слоёв побольше. Но человек может оперировать более абстракными понятиями и делать более долгосрочные прогнозы, чем обезьяна. Наверху есть вершины осознания, доступные только человеку.
Что касается достижений концепции Хокинса в сфере искуственного интеллекта, то их наработки вполне доступны. Смотрите numenta.com.
Бодрствование
Иван Пигарёв — физиолог. Занимается исследованием сна. Развивает висцеральную теорию сна.
Ставили опыты. Не давали мышкам спать. И мышки умирали через несколько дней. Умирали от множественных повреждений внутренних органов. А мозги были целёхоньки. То есть сон нужен не мозгу, а внутренним органам.
Терия в том, что во время сна мозг (кора мозга) отключается от сигналов внешней среды, а подключается к сигналам от внутренных органов. Этих сигналов весьма и весьма много. И наши суперумные мозги занимаются их обработкой. Хотя сознание тут не задействовано. И без этой обработки и регулировки, на автономном обеспечении, внутренние органы просуществуют недолго.
Выглядит очень и очень странно. Каким образом те нейроны, которые в бодрствующем состоянии натренированы на распознование зрительных образов, во сне обрабатывают сигналы от кишечника? Впрочем, тут подсказывают, что свёрточные нейронные сети, натренированные на распознавании изображений, можно успешно использовать и в других областях, если им отрезать и заменить входные и выходные слои. Возможно, что-то подобное происходит и в мозге. Меняем внешние слои обработки сигналов и выходных воздействий со слоёв приёма и выдачи внешних сигналов на слои приёма и выдачи внутренних сигналов, и вовсю задействуем крутую натренированную нейросеть глубинных слоёв.
Кстати, сон — это не привилегия высших животных. Мухи тоже спят. Похоже, это забавный эволюционный механизм. Если уж у нас появились такие сложные внутренности, почему бы не воспользоваться нашей крутой центральной нервной системой, чтобы порулить внутренностями? Во сне.
Но куда опять потерялось сознание? В базальных ганглиях, которые неактивны во сне? Впрочем, боюсь, что в структуре мозга может быть много нелогичного. И сознание может не быть где-то конкретно. Не инженер же проектировал. Но, по Хокинсу, сознание должно быть где-то в самой глубине свёрточной сети, оперируя максимальными абстракциями. Как можно отключить внутренности свёрточной сети? Или сознание — это действительно что-то особенное и сбокут.е.?
Персональный вывод: надо спать. Сон важнее, чем первая пара. Хочется спать — надо спать. А то всякие язвы желудка и всё такое...
А роботам спать не надо. У них же нет внутренних органов. Ну или для самодиагностики можно выделить дополнительную нейросеть, попроще. А вот где сознание? Неужели, если мы разберёмся в работе неокортекса и скопируем его, то получим умные, но совершенно бессознательные машины? Может, это и хорошо?
Взрывной рост ИИ
Тим Урбан — один из основателей сайта Wait But Why. Оттуда, и с разрешения Тима, Макс Дорофеев взял обезьяну и рационального типа, сосуществующих у нас в голове, для своих джедайских техник.
Про ИИ Тим Урбан пишет подробно. Рассматривает оптимистичные прогнозы Рэймонда Курцвейла. И опасения Илона Маска и компании, в лице Института будущего человечества, по поводу сверхинтеллекта.
Никто не сомневается, что рано или поздно, так или иначе, интеллект, подобный человеческому, и даже значительно его превосходящий, будет создан. Вопрос: чем (или кем) будет этот сверхинтеллект? И какое отношение у него будет к человеку?
Курцвейл чрезвычайно оптимистичен. Он считает, что человечество и созданный им сверхинтеллект — это будет одно и то же (привет, киборги!). А значит, всем будет хорошо.
И понятно, чем обеспокоены Маск и Гейтс. Искусственный сверхинтеллект не будет человеческим. И не будет животным. Ему будут совершенно неведомы эволюционные мотивы выживания и сосуществования. Он не будет проходить путь многолетнего воспитания. И он будет весьма могущественным. Настолько могущественным, что человек сдержать его не сможет. И как он отнесётся к человеку? Трансгуманизм по всей красе.
Азимову было хорошо. Три закона роботехники являлись неотъемлемой частью позитронного мозга. Мозга человеческого раба. Были его моралью. Но как привить мораль искусственному интеллекту, который мы сейчас можем построить, никто не знает. Да что там, мы не знаем даже, что такое человеческая мораль. Да и не факт, что сверхинтеллект не сможет обойти собственные моральные ограничения.
Her
В этом смысле фильм «Она» («Her», «Её»?) очень оптимистичен. ИИ родился, научился у человека любить, развился и умотал куда-то, оставив человечество в полнейшем недоумении. Ну прям как «Волны гасят ветер» у Стругацких. Но будут ли у настоящего сверхинтеллекта столь тёплые чувства по отношению к человечеству? Отсутствие ответа на этот вопрос как раз и пугает.
Впрочем, ныняшняя «умная операционка», в лице Алисы от Яндекса, хоть и весьма неплохо умеет гонять речь в текст и текст в речь, весьма тупа. И всякие домашние роботы, в большинстве своём игрушки, от Aibo до Cozmo, и даже вполне серьёзные роботы-ассистенты, тоже тупые. Ну не производят они впечатление умного (или хотя бы живого) существа. Даже до котёнка нормального не дотягивают.
Так что, надеюсь, ещё лет десять-пятнадцать у нас ещё есть. У человеков. Ещё лет десять-пятнадцать не бояться того, что появится кто-то умнее нас. А за это время, глядишь, и свыкнемся с этой мыслью. Или сами себя уничтожим, вместе с ростками потенциального сверхинтеллекта. Уничтожим по глупости, конечно. Ибо отказываться от прогресса вообще, и сверхинтеллекта в частности, никто даже не собирается. К Батлерианскому джихаду мы пока явно не готовы.

2017-10-30

Об Apache Spark

А вот вам заметки полного нуба об Apache Spark.
Apache Spark Logo
Именно Apache Spark™. А то есть ещё какой-то веб-фреймворк Spark. Не говоря уже о Twilight Sparkle. Плохое название. Гуглите осторожнее.
Apache Spark — это такая штука для распределённых вычислений. Эту всякую бигдату обрабатывать. Причём это не платформа для распределённых вычислений, типа Hadoop, а скорее фреймворк для распределённых вычислений. На нём можно писать эти распределённые вычисления. На Scala, Java, Python или R. Примерно однотипно на всех языках. А выполнять эти распределённые вычисления уже на кластере в Hadoop (точнее YARN) или в Apache Mesos. (Господи, всюду Апач.)
Чертовски привлекательно, что можно обойтись и без кластера, а запустить Спарк в локальной JVM. При этом, если у вас достаточно мощная машинка, и HDFS вы всё равно не используете, а значит, локальность данных вас особо не волнует, даже в таком локальном запуске можно сожрать изрядно оперативы и ядер ЦПУ, и перемолоть изрядную кучку данных.
Как-то так:
$ $SPARK_HOME/bin/spark-submit \
    --class "my.runners.App" \
    --master local[4] \
    target/scala-2.11/my-assembly-0.1.jar \
    --data-mongo-uri mongodb://... \
    --target-mongo-uri mongodb://...
Вот так локально мы и перемалываем несколько десятков гигабайт недельных данных за пару десятков минут, чтобы найти некоторые аномалии...
R я не знаю. Python в Spark не пробовал. А Spark изначально запилен на Scala. Пришлось немного освоить Scala.
Согласно последней политике продвижения Scala, все Scala продукты должны иметь хороший Java API. И у Спарка он есть. Так и написано в жалком подобии явадоков: вот этот метод для Скалы, а вот этот для Явы.
На Яве получается заметно многословнее, чем на Скале. Нет имплиситов, поэтому тот же Encoder везде надо явно втыкать. Encoder — это такая штука, которая описывает "схему" обрабатываемых данных. Данные же нужно гонять между узлами кластера, и для этого надо понимать, какой они "формы". Примитивные типы, case классы Scala, некоторые коллекции поддерживаются из коробки. Для Java ещё java beans тоже энкодятся. Как правило, этого достаточно.
Но я ведь попробовал пописать на Kotlin. Осторожно, spark-kotlin — это для веб-фреймворка, а не для Apache Spark. И на Котлине мне не понравилось. Уж лучше слегка научиться Скале.
Имплиситов в Котлине нет. Энкодеры надо прописывать явно. Data классы Котлина поддерживаются при этом не в Kotlin-way.
Вот такой data class работать не будет:
data class KotlinDataClass(
    val a: String
)
Потому что это не java bean. Тут конструктор не умолчательный. И сеттеров нет.
Нужно сделать java bean:
data class JavaBean(
    var a: String? = null
)
Вот теперь будет работать в Спарке. Хотя выглядит чудовищно с точки зрения Котлина.
Пользоваться приходится API для Java, JavaSparkContext и JavaRDD. Потому что скаловых коллекций Котлин не умеет (слава богу).
Бывает, что Котлин видит пару методов с разными сигнатурами. Один принимает скаловую функцию. Другой принимает какой-нибудь org.apache.spark.api.java.function.MapFunction. Второй метод явно добавили для Java API. Но Котлин эти сигнатуры не различает. Приходится явно функциональный литерал Котлина приводить к типу Function. Уродливо.
import org.apache.spark.api.java.function.MapFunction

//...

return df.map(
    MapFunction { o: MyObject ->
        //...
    },
    MySchema.myEncoder
)

//...
Через пару дней мучений, я всё же решил: Скала, так Скала.
Spark Bricks
Всё в Спарке крутится вокруг трёх штук, которые являются развитием одной и той же идеи. Это RDD (Resilient Distributed Datasets), DataFrame и Dataset. Их можно прочитать, из файлов (в том числе и HDFS) или из БД. Их можно записать, в файлы (в том числе и HDFS) или в БД. Над ними можно делать операции. Примерно те же операции, что и над Stream, что в Java 8: map(), flatMap(), filter(), reduce(), groupBy(), вот это всё. Только вот весь бигдатный набор данных будет побит на партиции, и каждая партиция будет обработана на воркере в кластере, а результат будет собран в кучку на том узле, который инициировал вычисления и называется Driver.
Разница между RDD, DataFrame и Dataset в типизации. RDD исторически был первым API Спарка. И он умеет работать только с кортежами (которые tuple). Т.е. все вот эти мапы и прочее вы будете делать с кортежами.
Dataset (и DataFrame) — это более новый API Спарка. В DataFrame вы имеете дело со схемой данных. Известны имена и типы столбцов. Соответственно, по именам можно стобцы извлекать, удалять из набора данных, и всё такое. Можно об этом думать как об очень длинной SQL таблице. Даже некоторые операции можно выражать на подмножестве SQL.
В Dataset вы имеете дело с объектами. Типа ORM. Очень удобно для таких объектов использовать case классы Скалы. На самом деле, технически DataFrame не существует, это Dataset[Row]. Но в работе гораздо удобнее более типизированный Dataset[MyCaseClass]. Вы задаёте класс при загрузке данных, и сразу получаете датасет нужных объектов. По ходу манипуляций у вас получатся другие объекты, и их снова можно сохранить в какую-нибудь коллекцию какой-нибудь БД.
Схема (т.е. набор и типы колонок) вполне успешно самостоятельно выводится из набора полей класса. Но есть возможность указать её самостоятельно. Это полезно, если у вас в какой-нибудь Mongo коллекции завалялись документы разных форм. Тогда указание схемы позволит выбрать только документы нужной формы, пригодные для обработки.
Читать/загружать наши датасеты можно из файлов, из любой реляционной БД через JDBC, из MongoDB. Если читаем из HDFS, вовсю работает локальность данных. Т.е. воркерам достанется на обработку та партиция, которая расположена на том же узле. Если читаем из реляционной БД, на локальность данных всем насрать, как я понимаю. Если читаем из MongoDB, может учитываться расположение шардов, если они у вас есть. Разбиение на партиции — это обязанность коннектора к БД. Для Монги есть свой коннектор, который понимает шарды. Для JDBC есть один общий коннектор, который может работать с любыми JDBC драйверами.
Это бигдата. Читать в датасет вам придётся всю таблицу или коллекцию. Целиком. Впрочем, в MongoDB есть возможность задать шаг aggregate, который будет вставлен в самом начале. Очень имеет смысл добавить туда $match, который выберет только то, что нужно.
Коннектор к MongoDB читает очень странно. На мой взгляд. Сначала делается большой aggregate(), в котором выполняется $sample, выбираются только _id порядка 10% всех документов. А потом уже выбираются все документы, с разбиением по диапазонам (от и до) _id. Вообще-то _id не образуют континуум, совпадающий с запрошенными данными, хоть они и упорядочены. В результате, как минимум, некоторые документы бывают пропущены, ибо их _id не попали в первоначальный $sample. Может в Big Data так принято, но мне такой алгоритм кажется странным.
В бигдате много странного и непривычного. Спарк не умеет обновлять данные. Он легко может создать новую таблицу или коллекцию и выгрузить туда весь датасет, который получился в результате вычислений. Но дальше уже ваша забота, куда эту таблицу засунуть. Как правило, её нужно как-то смержить с имеющимися данными. Например, как-то так:
INSERT IGNORE INTO existing_data (...)
SELECT ... FROM spark_result;
В случае с MongoDB можно попробовать сделать апдейт и в Spark. Опять таки, всё зависит от коннектора. Коннектор MongoDB умеет обращать внимание на _id документа. И если в датасете есть _id, будет сделан upsert, а не insert. Таким образом, можно загрузить датасет оригинальной коллекции и сджойнить с результатами обработки, обновить объекты. А потом обновлённый результат выгрузить в оригинальную коллекцию, обновить документы. Это всё работает, но только если вы вызовете правильный метод MongoSpark.save[D](dataset: Dataset[D], writeConfig: WriteConfig). Другие методы сохранения в MongoDB плевать хотели на _id.
Ну и лучше так не делать. Во-первых, вам придётся грузить в Спарк на одну коллекцию больше. Во-вторых, joinWith() — не самая лёгкая операция для Спарка. В-третьих, вы полностью перепишете оригинальную коллекцию, и все изменения, внесённые в неё третьей стороной с момента загрузки в Спарк, до момента выгрузки из Спарка, будут потеряны. Проще выгрузить из Спарка результат вычислений в отдельную коллекцию, а потом смержить уже средствами Монги. Это небыстро, но надёжно.
db.spark_result.find().forEach(
    function(doc) { db.existing_data.update(
        { ...update key... },
        { $set: { ...update operation... } },
        { upsert: true, multi: true })
    })
Apache Spark — типичный инструмент Big Data. Всё что вы можете: загрузить громадный объем данных, обработать его по кусочками, в параллель на узлах кластера, и выгрузить результат снова одним большим куском данных. Никакой модификации имеющихся данных, только создание новых. И при этом ещё могут быть погрешности в чтении :)
А иногда надо разветвиться. Подсчитать на исходных данных какую-нибудь тяжёлую статистику. А потом, по этой статистике, родить несколько разных результатов. Теоретически, для каждого результата нужен свой конвейер. Но тогда придётся для каждого конвейера заново вычитывать исходные данные и считать статистику. Скучно и неоптимально.
Поэтому в Спарке есть кэш. Метод persist(). Любой шаг конвейера можно сохранить в кэш. И начать новый конвейер с этого кэша. Будет быстро. Главное, чтобы памяти хватило. А не хватит памяти, можно использовать диск. На воркерах. Будет медленее, но это всё равно быстрее, чем вычитывать всё заново из внешней БД. Тем более, что Спарк хранит в кэше объекты, сериализованные с помощью Kryo. Главное, всё правильно подтюнить.
Похоже, в тех случаях, когда всё равно нужно перелопатить добрые сотни миллионов записей, чтобы получить какие-то результаты, Apache Spark является отличной альтернативой попытке перелопатить это средствами самой БД. Выйдет быстрее (потому что обработка будет делаться на других узлах, а не в БД) и значительно гибче (потому что это всё же код на Scala, где можно делать почти всё, что угодно). Вот только хочется нормального API и для Kotlin :)
Twilight Sparkle

2017-10-15

Об играх

В игры я почти не играю. Раньше играл. А сейчас почти не играю.
Нет, я, конечно, снова прошёл весь Carmageddon, когда он вышел под Android. И с удовольствием резался в Plague Inc.. И даже где-то у меня есть аккаунт в Steam, где пылится честно купленная на распродаже за нуль рублей Portal.
Carmageddon
Но я сейчас о другом. Я, оказывается, ни разу не задумывался, как делаются современные игры. А это прям отдельная Вселенная.
В студенческие годы, я, конечно, писал игрушки. Под DOS, на C и C++. Развлекался с трёхмерной графикой, освещением и текстурами в режиме 320х200 c 256 цветами. Трёхмерные крестики-нолики делал. А ещё в текстовом режиме были «Быки и коровы» и «Жизнь».
Чуть позже я немного развлекался с Borland C++ Builder (именно ещё от Borland). И наклепал для Windows тетрис (любой уважающий себя программист должен написать тетрис), решалку японских кроссвордов и даже симулятор MK-61 (ну как бы уже не совсем игра).
С тех пор игр не писал. А зачем? Какой от них толк? Интереснее сделать что-нибудь полезное. Для себя.
Ludum Dare
Но случайно таки оказался недавно на омском Ludum Dare. И там я узнал, что игры пишутся совсем не так, как пишутся обычные сетевые приложения, или как обычные гуёвые приложения.
Как работает обычный сервер? Он ждёт запросов. Пока запросов нет, он ничего не делает. Когда приходит запрос, он его обрабатывает. Запускает ли он для этого другой процесс, или другой поток, или всё делает в общем (для кучи соединений) потоке-воркере (то, что называется асинхронным) — не важно. Важно, что всегда есть запрос-ответ. Нет запроса — ничего не происходит (как правило).
Запросы создаёт клиент. Именно он является инициатором всего этого безобразия. Нет клиентов — нет запросов — ничего не происходит.
Аналогично в GUI. У нас есть события: движения мышки, нажатия кнопок и клавиш. Когда событие происходит, оно должно быть обработано. Графическим элементом, над которым оно произошло, окном и т.д. И тут, кстати, не придумали особо изящного способа обработки всех этих событий, кроме как одного, в одном потоке, бесконечного (но блокирующегося) цикла. Да, это тоже асинхронщина.
Пока вы двигаете мышкой из одного угла экрана в другой, происходят тысячи событий, в десятках разных приложений. Но если вы взялись ковырять в носу, и убрали руки с мыши и клавиатуры, то событий не будет. И снова ничего не будет происходить. Ну разве что курсор будет мигать. На старых терминалах мигание вообще делалось аппаратно.
Общее тут то, что пока нет события или запроса, ничего не делается. А когда события и запросы пошли, их все нужно успеть обработать. В современных GUI это не всегда тривиально. Но оно так и работает.
Java GUI Event Loop
В играх всё по-другому.
Даже роли клиента и сервера отличаются. Да, клиент по-прежнему подключается к серверу. Но дальше идут не запрос-ответ, а отправка сообщений. В обе стороны. Клиент сообщает о действиях игрока. Сервер сообщает о состоянии игры (изменённое действиями и этого, и других игроков). Существенное правило безопасности: сервер знает всё, а вот клиент должен знать только то, что ему положено знать. Нарушение этого правила порождает интересные возможности для тех, кого называют читерами (к примеру, в World of Tanks это вообще весело).
В играх игрок тоже жмёт кнопки и елозит мышкой. И это тоже может порождать события. Но эти события никого особо не интересуют. События не порождают немедленных действий по их обработке. Да, координата мышки, или номер нажатой кнопки могут быть где-то запомнены, чтобы знать, что кнопка нажималась. Но и всё.
Потому что в играх — постоянный polling. В бесконечных циклах. С задежкой. Это, конечно, не обязательно должны быть while (true) в отдельных потоках со sleep() внутри. Можно всё сделать хитрее, на таймерах и всё такое. Но сути дела это не меняет.
Есть цикл для отрисовки. Который даёт те самые fps. Тут всё просто. Берётся состояние игры, с точки зрения игрока. И отрисовывается. Столько раз в секунду, сколько надо. Само состояние может меняться реже или чаще.
Есть цикл опроса действий игрока. Тут как раз мы выясняем, какие кнопочки нажаты, где находится мышка. И, либо прямо модифицируем состояние игры, в случае сингл плеера. Либо передаём намерения игрока на сервер, в случае сетевого мультиплеера.
На сервере намерения игроков накапливаются. А потом происходит тик игры. Это самый главный цикл, где изменяется глобальное состояние игры. Раз и навсегда. Тут просчитываются всякие перемещения, уроны, жизни и т.п. И тут очень важным параметром является время, прошедшее с предыдущего тика. Как правило это время не может быть в точности постоянным. И это надо учитывать, дабы персонажи, как минимум, перемещались равномерно. И изменённое состояние игры рассылается всем игрокам.
Из-за ограничений в скорости сети, эти рассылки идут значительно реже, чем fps. Что порождает некоторые особенности. Все эти опросы, просчёты, отрисовки происходят каждый в своём цикле. И они в общем случае не синхронизированы. Нужны какие-то правила синхронизации.
Например, что делать, если игрок упорно движется в определённом направлении, а с сервера обновлённого состояния, где произошло перемещение в данном направлении, ещё не пришло? Клиент может взять на себя смелость и изменить местоположение игрока, чтобы при прорисовке перемещение происходило плавно. Это называется интерполяцией. Если прогнозы клиента, и обновлённое состояние с сервера совпали — всё хорошо. А вот если выяснится, что игрока по пути кто-то убил, придётся как-то выкручиваться и дорисовывать, что сначала мы дошли туда, а потом, метром ранее, умерли.
Пересылка сообщений. Циклы опроса. Асинхронная пересылка сообщений. Синхронизация состояний. Безопасность и доверие. Вот это вот всё — игры.
Может, я рассматриваю лишь частный случай игродельной индустрии. Но мы на Людуме клепали так.
Game Loop
Почему же классические клиент-серверные архитектуры, а так же GUI, построены по-другому? Дело в экономии ресурсов? Выгодно ничего не делать, пока нет событий? В играх ведь все циклы: отрисовки, опроса, просчёта следующего состояния игры — колбасят всегда, независимо от действия или бездействия игрока. CPU и сеть никто особо не жалеет.
С другой стороны, где-то циклы с постоянными опросами всё же встречаются? Уж не в ядрах ли ОС? Тот самый поллинг сетевой карты вместо прерываний. Нет? А в RTOS, случайно, не осуществляется такой же тотальный контроль над временем выполнения задач? Ну не успел выстрел игрока попасть в вычисления данного состояния игры, значит выстрела на данном шаге не будет.
Какая-то другая Вселенная — эти игры. Где бы это применить, не начиная писать игры? :)

2017-10-01

О сэре Максе из Ехо

Наконец-то дочитал «Лабиринты Ехо» и «Хроники Ехо». Думаю, теперь можно написать про Макса Фрая. Точнее про сэра Макса из Ехо. В надежде, что кто-нибудь тоже захочет прочитать эти прекрасные книги.
Ехо
Рукописи в издательство носили, конечно же, обычные люди: Светлана Мартынчик (ага, женщина) и Игорь Стёпин. Но автором значится некто Макс Фрай. Или Max Frei, если латиницей. Максимально свободный. Или без Макса. И вовсе никогда не Максим.
Вот Макс Фрай и пишет автобиографические очерки. О том, как он был сэром Максом в Ехо. И как туда попал. И как туда вернулся. Где его всегда называли только по имени. Что там ещё было с Максом Фраем кроме Ехо, этого я ещё не читал.
Порядок чтения очень важен. Это же Кастанеда для маленьких. Не прочтёте предыдущие книжки, не поймёте, на что ссылаются и объявляют ложным последующие книжки. Ну ладно, Макс Фрай ничто не объявляет ложным, чем запутывает и себя, и читателя ещё больше.
Сначала «Лабиринты Ехо», потом «Хроники Ехо», потом, видимо, «Сновидения Ехо». За точным порядком можете консультироваться у Википедии. Кстати, последние книжки «Сновидений Ехо» вышли в этом (2017) году, так что история продолжается.
Жанр? Определённо фэнтэзи. Или как там называется это всё, с волшебством, эльфами (хотя тут эльфы весьма странные) и всем прочим? Определённо детектив. Потому что почти всегда имеется преступление и расследование. А ещё мистика, ужасы, комедия, мелодрама. Да всё, что угодно. Поэтому я нарекаю жанр историй сэра Макса из Ехо «сериалом».
Это действительно сериал. Длинный и увлекательный. С громадным количеством длинных нескучных диалогов. С несильно большим количеством действия. Впрочем, после каждого действия офигевать приходится и читателям, и сэру Максу. Сэра Макса мог бы сыграть, к примеру, Егор Бероев. А вот сэра Джуффина Халли конечно же должен бы играть Рутгер Хауэр, как он выглядел, к примеру, в «Десятом королевстве».
Карта Мира
Слово «Ехо» надо читать именно как «Е́хо», а не «Ёхо» или «Эхо». Ехо — это столица Соединённого Королевства, крупнейшего государства, расположенного на материке Хонхона в Мире Стержня. Ехо построен вокруг Сердца Мира. Сердце Мира — это то место, где выходит один из концов Стержня, на котором и держится этот Мир.
У Сердца Мира отлично работает Очевидная (или бытовая) магия, и чёрная, и белая. Именно потому Ехо построили здесь. Чтобы магистрам многочисленных магических орденов было веселее сражаться друг с другом. Впрочем, оказалось, что злоупотребления Очевидной магией разрушают основу Мира. В результате, ради спасения Мира, все магические ордены были упразднены или побеждены, а у власти Соединённого Королевства остались, собственно, король, Гури́г VII, а также Орден Семилистника, Благостный и Единственный. Впрочем, это всё произошло более чем за сто лет до описываемых событий.
Зато, помимо Очевидной есть ещё и Истинная магия. В которой большинство героев вполне сведущи и более уважают. А ещё есть... А фиг его знает, что там ещё есть.
Макс попал в Ехо, то есть в Мир Стержня, из Мира Паука. По указанию Джу́ффина Ха́лли он сел на трамвай на улице, где трамваи отродясь не ходили. Это самая первая версия появления сэра Макса в Ехо. Есть ещё и другие. Более мистичные, прагматичные и циничные. Но все они вполне истинны. Ибо иначе и быть не может.
Трамвай между мирами
Мир Паука — это наш с вами мир, дорогие читатели. Паука, потому что мы, как пауки, любим оплетать окружающую действительность «паутиной», привязывая к себе вещи и людей. И привязываясь к ним сами.
А ещё в нашем мире дофига Вершителей. Вершитель — это существо, чьи желания исполняются всегда, рано или поздно, так или иначе.
Вы никогда за собой не ощущали, что вы — Вершитель? А не замечали Вершителей вокруг? Не забывайте про «рано или поздно, так или иначе», что повышает пикантность ситуации. Так что Вершители — вовсе не счастливые или удачливые люди. А теперь представьте, что Вершителей набралось миллиарды. Как в нашем мире. Бардак вполне ожидаем, не так ли?
А вот в Мире Стержня последним Вершителем был легендарный король Мёнин. И очень понадобился ещё один. И им стал сэр Макс. От короля Мёнина сэр Макс натерпелся немало шуточек (или серьёзностей) сомнительной доброты. Даже как-то таскал в собственной груди его меч, дада, воткнутый насквозь.
Кроме Мира Стержня и Мира Паука существует бесчисленное множество других миров. И одно из призваний практикующего Истинную магию (а также почти всех призраков) — путешествовать между мирами. Или по Тёмной стороне Мира. Или по Изнанке Тёмной стороны. Или по Сновидениям. Настоящий колдун всегда найдёт, где поразвлечься.
А некоторые, особо сильные колдуны, вполне могут создавать новые миры, или разрушать целые миры. Сэр Макс, кстати, между делом создал несколько миров в самом начале своих приключений. За что потом понадобилось нести ответственность.
Итак.
Игрушечный Макс
Сэр Макс. Ночное Лицо Почтеннейшего Начальника Малого Тайного Сыскного Войска города Ехо. Сидит по ночам в кабинете сэра Джуффина, на всякий случай, замещает. Смерть на королевской службе, носит Мантию Смерти. Ибо может плеваться ядом. Владыка Фангахра, властитель народа Хенха из Пустых Земель. Оказался в центре политических игр, в результате которых Пустые Земли присоединились к Соединённому Королевству. Вершитель. Его Смертный Шар не убивает, а подчиняет. Человек Тёмной Стороны. Сновидец. Может творить множество самых удивительных чудес, но сам не понимает, как это у него получается. Балагур, душа компании.
Джуффин
Сэр Джу́ффин Ха́лли. Почтеннейший Начальник Малого Тайного Сыскного Войска города Ехо. В прошлом Кеттари́йский Охотник, Кеттари́ец, Чи́ффа, известный и опытный наёмный убийца. Старый опытный колдун, специализирующийся на Истинной магии, и радеющий о судьбе Мира. Человек Тёмной Стороны. Сновидец. Основал Тайный Сыск, дабы творить всякие магические непотребства, когда всем остальным это запрещено Кодексом Хре́мбера. Начальник и учитель сэра Макса.
Мелифаро
Сэр Мелифа́ро. Дневное Лицо Почтеннейшего Начальника Малого Тайного Сыскного Войска города Ехо, то есть заместитель сэра Джуффина в дневное время. Страж (границы Тёмной стороны). Лучший сыщик, применяет дедуктивные и прочие методы, как и положено детективу. Сын автора «Энциклопедии Мира» сэра Ма́нги Мелифа́ро. Не имеет имени, ибо, когда он родился, отец как раз путешествовал, собирал материал для экциклопедии, и не нашёл времени выбрать сыну хоть какое-нибудь имя. Модник. Балагур. Постоянный оппонент сэра Макса в колкостях и остротах.
Шурф Лонли-Локли
Сэр Шу́рф Ло́нли-Ло́кли. Мастер Пресекающий Ненужные Жизни, штатный убийца Тайного Сыска. Владеет Перчатками Смерти, ими, собственно, и убивает, когда нужно. Человек Тёмной Стороны. В прошлом Безумный Рыбник, известный исторический персонаж конца Эпохи Орденов. Состоял в Ордене Дырявой Чаши, в результате имеет привилегию пить из дырявой посуды, и это у него прекрасно получается. В силу необходимости вынужден быть Истиной, точно соблюдать правила и предписания и требовать подобное от других. Невозмутимый педант. Любитель и знаток поэзии и литературы. Лучший друг сэра Макса, вместе они попадали в совершенно странные истории и неоднократно спасали жизнь друг другу.
Меламори
Леди Меламо́ри Бли́мм. Мастер Преследования Затаившихся и Бегущих. Встаёт на их след, и никуда они не денутся, леди притащит их в Тайный Сыск, как бы они ни сопротивлялись. Первая (и долгое время единственная) леди Тайного Сыска. Первая и последняя девушка сэра Макса в Ехо. Уезжала на далёкий и таинственный материк Арваро́х. Вернулась весьма необычным для уроженки Угула́нда способом: превратилась в буривуха и прилетела. Что свидетельствует о недюженном таланте к фиг знает какому виду магии.
Кофа Йох
Сэр Ко́фа Йо́х. Мастер Слышащий. Или Кушающий-Слушающий, по едкому замечанию сэра Мелифаро. Меняет внешность (кардинально, магическим образом) и шляется по трактирам Ехо, узнавая все свежие слухи. Старый и опытный колдун, специалист в Очевидной магии. На Тёмную сторону попасть не может. Снов не видит. В прошлом — Генерал Полиции Правого Берега. Гонялся в те времена за Кеттарийским Охотником, пару раз даже почти поймал. Сын Хумхи Йоха, одного из семи легендарных «Отцов Основателей» Ордена Семилистника.
Сэр Нуммино́рих Ку́та. Штатный Нюхач Тайного Сыска. Очень чутко различает запахи. По запаху может сказать, где бывал и чем питался человек последние несколько дней. Талантливый сновидец. Ученик сэра Макса.
Теххи
Леди Теххи Шекк. Девушка сэра Макса, между леди Меламори и леди Меламори. Дочка Лойсо Пондохвы, в результате — не вполне человек, а скорее сильное наваждение. Зеркало, подстраивается под собеседника, чем вызывает неодолимую симпатию.
Лойсо Пондохва
Ло́йсо Пондо́хва. Основатель и Великий Магистр Ордена Водяной Вороны. Один из величайших колдунов своего времени. Тяготеет к разрушениям, в результате стал героем многочисленных поговорок вроде: «Сам Лойсо Пондохва ногу сломает». Его именем пугают маленьких детей. Стёр с лица земли родной город сэра Джуффина Халли Кетта́ри. Был пойман Джуффином Халли (ещё Кеттарийским Охотником), при содействии Шурфа Лонли-Локли (ещё немного Безумным Рыбником). Был освобождён сэром Максом. Был спасён сэром Максом от жажды разрушений. Друг и тайный собеседник сэра Макса.
Ну вы поняли. Куча новых слов, географических названий, странных имён. С фиг поймёшь какими ударениями. Много магии. Разной магии. Странной магии. Много разных чудес, разной степени чудесатости. А главное, почти на каждой странице найдётся настолько милая фразочка, что уже устаёшь дёргать их на цитаты.
Пока писал всё это, глянул, о чём там «Сновидения Ехо». Да, это продолжение. Сэр Макс снова возвращается в Ехо.
Как будто прочитать как будто волшебным несуществующим увидительным пережитые написанные изданные как будто о настоящем волшебном многозначном удивительном как будто радостные и полезные узнать и полюбить.
Мелифаро и Шурф

2017-09-17

О MongoDB

После долгого перерыва я снова столкнулся с MongoDB. Не по своей воле.
В этом перерыве я тыкал разное. InfluxDB, чтобы понять, что Graphite, точнее Whisper, нифига не устарел, и вполне имеет право на жизнь. ClickHouse, чтобы окончательно решить, что для такого рода данных, когда нужно хранить разовые события, привязанные ко времени, а потом делать по ним разную хитрую аналитику, я буду использовать только ClickHouse. Но больше всего возился со старым добрым PostgreSQL, интенсивно заюзывая его модный jsonb.
MongoDB logo
А вот теперь пришлось снова тыкать MongoDB. В которую пришлось складывать эти самые разовые события, привязанные ко времени, и делать аналитику.
Историческими судьбами в этой Монге сложилась странная схема данных. Есть три коллекции. В одну события складываются как есть, но живут они там только четыре часа. Появилась в Монге такая возможность, индексы с TTL, что сильно удобнее старых capped collections.
В другую коллекцию складываются типа агрегированные данные, сгруппированные по одному из измерений, и собранные за пять минут. На каждые пять минут, на каждое уникальное значение этого измерения — создаётся новый документ. А в нём массив, который пополняется новыми событиями, которые в течение этих пяти минут возникнут.
В третью коллекцию складываются типа агрегированные данные, сгруппированные по другому измерению. Но собранные за неделю. Так же, в массиве. Почему за неделю, неизвестно. Видимо, потому, что размера монгодокумента хватает, чтобы хранить события за всю неделю для каждого уникального значения измерения.
В Монге по-прежнему искусственно ограничен размер документа. И это по-прежнему 16 мегабайт. Помните, зачем? Потому что операции над документами атомарны. И при передаче по сети шестнадцати мегабайт ещё можно сделать вид, что это происходит «атомарно».
Я сразу забраковал эту схему, потому что она подразумевает постоянные апдейты документов. А старый движок Монги, который теперь называют MMAPv1, модифицировал документы «на месте». Если было место, дописывал на месте. Если не было места, ему приходилось копировать документ в конец коллекции и дописывать там. А чтобы место было, он отводил для документа на диске место с запасом. Поэтому этот движок был чудовищно жаден до диска. И очень не любил, когда документы не просто модифицировались, а ещё и увеличивались в размере. Ну прям наш случай.
Над этим движком смеялись все кому не лень. Все разработчики настоящих баз данных. Ибо это были просто memory mapped файлы. В плане скорости это давало некоторые преимущества. Ибо на диске это BSONы, ОС маппит эти BSONы в память, а движку БД остаётся только кидать BSONы из памяти в сокеты и обратно. Но в плане надёжности сохранения данных это было никак. Там, конечно, прикрутили потом журнал. Но это не особо помогло.
И вот теперь, уже вполне солидно, официально и по дефолту у Монги работает другой движок — WiredTiger. Он уже вполне похож на настоящую БД. Он — версионник, MVCC. Это значит, что он никогда не апдейтит «на месте», для него, что insert, что update — одна фигня. Он жмёт данные на диске. Очень хорошо жмёт, кстати. У него есть свой самостоятельный кэш, а не только дисковый кэш ОС.
У WiredTiger тоже есть журнал. Впрочем, журнал всё равно сбрасывается на диск по таймеру. И если в операции записи вы выражаете желание дождаться записи в журнал, ваш запрос действительно будет ждать следующего тика скидывания журнала на диск, и только потом завершится.
«Связанный тигр» — существенный прогресс MongoDB как настоящей базы данных. Рекомендую, если приходится иметь дело с Монгой.
WiredTiger advantages
BSON. Продолжаю восхищаться этим изобретением ребят из 10gen. Все разработчики БД, которые, на волне хайпа по NoSQL, добавляют поддержку JSON. Не надо, прошу вас. Добавляйте поддержку BSON.
JSON — это текстовая фигня с сомнительной эффективностью хранения и парсинга, и совсем никакой поддержкой нормального набора типов данных. Там нет целых чисел, и тем более long. Там совсем-совсем невозможно нормально хранить бинарные данные. А бинарные данные у вас всегда будут. Оно вам надо, каждый раз эту фигню парсить и сериализовывать на входе и на выходе, даже если у вас внутри это как-то мегоэффективно хранится, как в jsonb?
BSON — это нормальный эффективный бинарный формат. Тут для каждого значения хранится длина, а значит, можно эффективно пробежаться по документу и извлечь только то, что надо. Тут есть нормальные int и long, и массивы байтов, и timestamp. Как правильно замечает Википедия, какой-нибудь ProtoBuf может быть эффективнее. Но в ProtoBuf нужна схема. А BSON гибок как JSON.
BSON example
Кажется, Монга научилась использовать несколько индексов одновременно. Но, похоже, предпочитает по старинке брать лишь один индекс для выполнения данного запроса. Дело в том, что индексы, точнее планы запросов, по-прежнему выбираются методом честного соревнования. Если Монга не помнит, какой план запроса был лучшим, она гоняет все возможные планы, и выбирает самый быстрый, и запоминает его на будущее. Просто. Тупо. Эффективно?
Aggregation framework возмужал. Когда-то это была лишь упрощённая и ограниченная замена map-reduce. Но теперь это довольно мощная штука. Заметно мощнее обычных запросов, но почти такая же эффективная. Судя по тому, с какой скоростью в новых версиях Монги добавляют сюда новые возможности, скоро с aggregation framework можно будет делать всё.
Чаще всего aggregation pipeline собирается из $match, $project и $group.
$match — это аналог where. Здесь можно задать условия выборки документов из коллекции. Тут работают индексы, если они есть.
$project — это аналог выражений после select, проекция. Тут всё значительно мощнее, чем в проекции обычного find(). Можно не только включать и исключать поля. Можно высчитывать любые выражения по содержимому документа. Например, можно взять, и сделать $filter и даже $map по содержимому массива в документе.
$group — это аналог group by. По данному ключу (а в частности, по ключу null, т.е. для всех документов) можно собрать агрегацию: сумму, минимум, максимум, всё такое.
Есть и другие интересные операторы. $unwind позволяет развернуть массив в виде последовательности документов. Примерно так, как это может делать PostgreSQL со своими массивами. $lookup позволяет вытащить из другой коллекции целый документ и воткнуть сюда. По сути, это join.
Все эти милые операторы собираются именно что в pipeline. Выхлоп предыдущего шага является входом следующего шага. Можно строить длинные цепочки преобразований, чтобы в конце получить лишь одно число, как оно часто и нужно в этих агрегациях :)
Всё это достаточно мощно, что люди всерьёз пишут конверторы из SQL в монговские aggregation pipeline.
Aggreration pipeline
Схема данных, как всегда, имеет значение. Не обольщайтесь schemaless, это вовсе не thoughtless для разработчика. В данном случае засада оказалась в количестве «горячих» документов.
С коллекцией номер раз всё понятно. Мы туда просто инсертим, и всё. Никакие документы не модифицируются.
С коллекцией номер два сложнее. Здесь в течение пяти минут интенсивно обновляются одни и те же документы. Сколько их, определяется мощностью множества значений того измерения, по которому происходит группировка. В данном случае — сотни. Практические замеры показали, что за пару часов модифицируются лишь тысячи документов. Несмотря на относительно большой размер этих документов — десятки килобайт — они все прекрасно помещаются в кэш размером меньше полугигабайта. Поэтому проблем с апсертами в эту коллекцию не было.
Проблемы случились с коллекцией номер три. Агрегаты за неделю, по второму измерению. Средний размер документа тут маленький — килобайты. Хотя встречаются документы, вплотную приближающиеся к заветным 16 мегабайтам. Но вот мощность множества значений этого второго измерения — миллионы. Миллионы «горячих» документов, килобайтного размера. Это, по-хорошему, уже нужен кэш в несколько гигабайт.
Памяти добавили, ядер добавили, IOPS добавили. А не помогало.
Оказалось, что я избаловался акторами и прочими прелестями асинхронной обработки. Даже наша фиговина, которая должна была в эту самую Монгу пихать события, хоть и принимала эти события через один сокет в одном потоке, потом вовсю юзала ThreadPoolExecutor, раcпихивала задания по очередям, а потом выполняла в столько потоков, в сколько нужно.
А вот MongoDB, как, впрочем, и большинство других баз данных, включая PostgreSQL, — не такая. Она — синхронная. Одно подключение — один поток, который выполняет все запросы в этом подключении строго последовательно.
И оказалось, что апдейты этой третьей коллекции по неизвестной причине (возможно из-за необходимости распаковывать и запаковывать документы) очень жрут CPU на сервере. Вставляем через одну коннекцию — упираемся в один поток на сервере, который выжирает лишь одно ядро CPU. И всё медленно.
Ок. Сделаем четыре потока на нашей клиентской стороне, нам же всё равно, у нас же ExecutorService. Получаем четыре коннекции к Монге. А там — четыре потока на четырёх ядрах CPU, которые занимаются тем, чем они хотят заниматься. Работает? Работает. Проблема решена. Тупой подход: «Тормозит? Добавь потоков!» — сработал.
Ну, конечно, есть нюансы, которые решились по ходу дела. По-хорошему, нужно не давать разным потокам на Монге лезть в одни и те же документы. Чтобы не порождать конфликтов и блокировок. Делается это переупорядочиванием входящих событий и грамотным созданием заданий в ExecutorService.
ClickHouse logo
И всё-таки, для этой задачи я бы взял ClickHouse. Прям руки чешутся. Зачем нужны все эти предварительные агрегации? Зачем хранить данные в трёх экземплярах? Если можно за приемлемое время быстренько прогрепать всё, что было за указанный период.
Для сравнения, те же самые события мы, ради Истории, решили записывать в логи и складывать в архив. CPU совсем прохлаждается, памяти не нужно, IOPSов тоже не нужно, ибо последовательная запись в один поток. Нужно место на диске. И тут по компактности WiredTiger побеждает gzip :) Подозреваю, ClickHouse уделает обоих. А извлекать данные будет сильно удобнее, чем с помощью zgrep.

2017-09-03

О JWT

А как вы ограничиваете доступ к вашему API?
Понятно, что в нашей аутсорсной разработке, когда это приватное API какого-то сервиса внутри конторы заказчика, можно понаставить огненных заборов, и вообще сделать API доступным только из приватной сети.
А если это публичное, да и к тому же многопользовательское API? Как вы аутентифицируете и авторизуете пользователей? Это ведь API, тут нет формы логина.
API
Тупой, но вполне для начала работающий способ: Basic Authentication. Можно даже взгромоздить проверку паролей на тот же Nginx.
Но, простите, о каких пользователях идёт речь? Это же API. Это не пользователи. Это некие программные агенты стучатся к вам в интересах пользователя.
Поэтому, чтобы не смущать себя эфемерными пользователями и их паролями, клиентам API выдают некие токены. Токен, в данном случае, некая строка, идентифицирующая данного клиента, а иногда и права, выданные клиенту.
Login form
Вопрос первый: где и как получать токены?
На эту тему сломано немало копий. Но, похоже, в случае веб-сервисов, побеждают разные варианты OAuth.
В OAuth для выдачи токена требуются явное участие и согласие юзера, в интересах которого агент будет действовать. Для этого задействуется веб-браузер, а пользователя явно просят в этом браузере по-человечески авторизоваться на сервисе, который будет предоставлять API. Т.е. на вашем сервисе.
Веб-браузер — хорошо. Для агентов, которые сами являются веб-сервисами. Для агентов, которые локальные приложения, вызов веб-браузера выглядит странно, особенно для консольных приложений, но вполне работает.
Если у вас не публичный веб-сервис, а просто бэкенд какого-то вебдванольного приложения, можно, конечно, поступить проще. Просто сделайте метод, который за логин-пароль юзера будет выдавать токен.
OAuth 2.0
Вопрос второй: как передавать токен?
HTTP предоставляет уйму способов. Есть заголовки запроса. Есть параметры запроса. Есть тело запроса (в тот же JSON самого запроса токен добавить). Все варианты имеют место быть.
Более-менее стандартным таки является заголовок Authorization. Причём у него есть тип.
Authorization: <type> <credentials>
Для базовой аутентификации тип — это «Basic». Для передачи токенов в OAuth 2.0 тип — это «Bearer». Ничто не мешает придумать свой «тип», только сначала напишите для этого RFC.
Понятно, что в любом случае токен передаётся открытым текстом. И тот, кто перехватит токен, сможет им воспользоваться, выдав себя за чужого агента. Поэтому, только HTTPS. Шифруемся.
Если у вас не HTTP/HTTPS или не только HTTP/HTTPS, то ничего другого не остаётся, кроме как включить токен одним из параметров запроса (то бишь, в тело запроса). Почему бы и нет.
Authorized
Вопрос третий: где хранить и как проверять токены?
На клиентской стороне, если это браузер, уверенно побеждает LocalStorage. Храните токены там, подсовывайте в запросы к API, и будет вам счастье.
Интереснее, что происходит на серверной стороне. Что API делает с токенами?
Очевидный подход. Пусть токен — это просто случайная строка достаточной длины. Сохраним токен в таблицу (или коллекцию) БД, запишем дату его выдачи (или дату окончания действия), и свяжем с нужными правами нужного пользователя. Всё. Работает. Просто, понятно.
Но на больших масштабах у этого подхода проявляются недостатки. На каждый запрос к API, требующий авторизации, независимо от сути самого запроса, требуется просмотр этой таблицы БД на предмет поиска и проверки токена. Если разных API у нас несколько, и сами API горизонтально отмасштабированы на кучу серверов, обеспечить для всех них актуальный доступ к одной таблице становится не очень простой задачей. К тому же, при миллионах пользователей, токенов может быть ещё больше. Сама таблица может получиться очень не маленькой.
Можно обойтись без всего этого. Пусть сам токен хранит в себе всё, что нужно для идентификации пользователя, выяснения и проверки его прав. Тогда большая таблица не понадобится. Не нужно будет делать в неё запрос. А каждый сервер с API может проверить токен самостоятельно.
А чтобы хитрый пользователь не подделал токен, мы будем его подписывать. В криптографическом смысле. Ключом, известным только серверу (серверам).
JWT and friends
Слава богу, ничего на этом поприще изобретать не надо. Ибо есть стандарт JWT — JSON Web Tokens.
JSON, потому что всякие служебные данные и сведения о пользователе представлены в виде JSON.
Типичный JWT токен выглядит так:
eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJzdWIiOiIxMjM0NTY3ODkwIiwibmFtZSI6IkpvaG4gRG9lIiwiYWRtaW4iOnRydWV9.TJVA95OrM7E2cBab30RMHrHDcEfxjoYZgeFONFh7HgQ
Расшифровать можете на упомянутом jwt.io.
Это три «слова» в base64 кодировке, разделённые точкой.
Первое «слово» — заголовок. Описывает, какие алгоритмы мы используем для подписи и какого типа содержимое токена используем.
$ echo "eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9" | base64 -d
{"alg":"HS256","typ":"JWT"}
В данном случае «HS256» означает HMAC SHA256, алгоритм подписи такой. А «JWT» означает, что тело токена — действительно JSON в понятиях JWT.
Второе «слово» — тело токена.
$ echo "eyJzdWIiOiIxMjM0NTY3ODkwIiwibmFtZSI6IkpvaG4gRG9lIiwiYWRtaW4iOnRydWV9" | base64 -d
{"sub":"1234567890","name":"John Doe","admin":true}
Это JSON, который содержит некоторые свойства, которые в JWT называют claims, т.е. утверждения.
Некоторые claims определены стандартом JWT. Они, для компактности, трёхбуквенные. iss, issuer — идентификатор того, кто выдал токен. sub, subject — кому выдан токен, например, это идентификатор пользователя. exp, expiration time — время жизни токена, в виде unix timestamp в секундах. iat, issued at — момент выдачи токена, в виде unix timestamp в секундах.
Остальные claims зависят от данного API. Можно их зарегистрировать, чтобы ни с кем не пересечься. А можно просто набросать любых слов или uri.
Третье «слово» — подпись, в формировании которой используется некоторый секрет.
$ openssl dgst -sha256 -mac HMAC -macopt key:secret -binary \
  <( echo -n "eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJzdWIiOiIxMjM0NTY3ODkwIiwibmFtZSI6IkpvaG4gRG9lIiwiYWRtaW4iOnRydWV9"; ) \
  | base64
TJVA95OrM7E2cBab30RMHrHDcEfxjoYZgeFONFh7HgQ=
Надо же, openssl умеет.
JWS token structure
В мире Java с JWT токенами можно работать, например, с помощью jjwt.
Генерировать токен можно примерно так.
fun generateToken(username: String): String {
    return Jwts.builder()
            .setSubject(username)
            .setExpiration(Date(System.currentTimeMillis() + EXPIRATION_TIME))
            .signWith(SignatureAlgorithm.HS512, SECRET)
            .compact()
}
Поместите это в какой-нибудь контроллер, который отвечает за логин и выдачу токенов. Можно добавить и любые другие Claims при необходимости.
Проверять токены можно с помощью Spring Security, который нужно соответствующим образом сконфигурить.
@Configuration
@EnableWebSecurity
open class WebSecurityConfig : WebSecurityConfigurerAdapter() {

    override fun configure(http: HttpSecurity) {
        http.csrf().disable()
                .authorizeRequests()
                .antMatchers("/login").permitAll()
                .anyRequest().authenticated()
                .and()
                // And filter other requests to check the presence of JWT in header
                .addFilterBefore(JWTAuthenticationFilter(),
                        UsernamePasswordAuthenticationFilter::class.java)
    }

}
Проверять заголовок «Authorization» будет соответствующий фильтр.
class JWTAuthenticationFilter: GenericFilterBean() {

    private val SECRET = "secret"

    override fun doFilter(request: ServletRequest,
                          response: ServletResponse,
                          filterChain: FilterChain) {
        val authentication = getAuthentication(request as HttpServletRequest)

        SecurityContextHolder.getContext().authentication = authentication
        filterChain.doFilter(request, response)
    }

    private fun getAuthentication(request: HttpServletRequest): Authentication? {
        val token = request.getHeader("Authorization")
        if (token != null) {
            val user = Jwts.parser()
                    .setSigningKey(SECRET)
                    .parseClaimsJws(token.replace("Bearer ", ""))
                    .body
                    .subject

            return if (user != null)
                UsernamePasswordAuthenticationToken(user, null, listOf())
            else
                null
        }
        return null
    }

}
Ну а добраться до аутентифицированного пользователя можно стандартными для Spring Security средствами.
@RestController
open class UserController {

    @RequestMapping("/user")
    fun user(): UserResponse {
        val authentication = SecurityContextHolder.getContext().authentication
        val username = (authentication.principal as? UserDetails)?.username ?: authentication.principal.toString()
        return UserResponse(username)
    }

}
Проверяем.
$ curl http://localhost:8080/user
{"timestamp":1504417496948,"status":403,"error":"Forbidden","message":"Access Denied","path":"/user"}

$ curl http://localhost:8080/login
{"token":"eyJhbGciOiJIUzUxMiJ9.eyJzdWIiOiJhZG1pbiIsImV4cCI6MTUwNDQyNDcxNn0.a9P1SroxiSTUraFdhYwUMjY0tFdhehIRa-R3oOfuW5Ov0INjKH0bS3b57PLF8rhj3uEYXzcPtplID-ncJkWJZg"}

$ curl http://localhost:8080/user \
    -H 'Authorization: Bearer eyJhbGciOiJIUzUxMiJ9.eyJzdWIiOiJhZG1pbiIsImV4cCI6MTUwNDQyNDcxNn0.a9P1SroxiSTUraFdhYwUMjY0tFdhehIRa-R3oOfuW5Ov0INjKH0bS3b57PLF8rhj3uEYXzcPtplID-ncJkWJZg'
{"usename":"admin"}
Больше примеров и кода можно найти тут и здесь.
Spring
Spring Security, конечно же, уродлив. С нормальным middleware всё выглядит значительно красивее (потому что больше магии).
from flask_jwt import JWT

app = Flask(__name__)

app.config['JWT_AUTH_URL_RULE'] = '/api/v1/auth'
app.config['JWT_EXPIRATION_DELTA'] = timedelta(hours=2)

from app.models import User

def authenticate(username, password):
    # тут отрабатывается /api/v1/auth, по логину паролю извлекаем юзера
    user = User.query.filter(User.username == username).first()
    if user and check_password_hash(user.password, password):
        return user

def load_user(payload):
    # тут извлекаем юзера по телу токена
    user = User.query.get(payload['identity'])
    # тут конечно плохо, что за юзером лезем в базу, лучше его всего в токен засунуть
    return user

jwt = JWT(app, authenticate, load_user)


from flask_jwt import jwt_required, current_identity as user

@app.route('/users/get_user_info')
@jwt_required()
def get_user_info():
    # тут магическим образом юзер (точнее current_identity) стали доступны
    return jsonify(
        user_name=user.username,
        user_id=user.id
    )
Flask
Обратите внимание, что JWT токен не зашифрован. Он только подписан. Такие токены называют JWS — JSON Web Signature. Владелец токена, т.е. сам юзер, вполне может прочитать, что вы там про него храните.
Если вы не хотите лишний раз смущать пользователя, или же хотите уменьшить последствия компроментации токена (одно дело, получить доступ к API и узнать ID данного пользователя, другое дело, узнать email пользователя или даже пароли от других сервисов), то можно и зашифровать тело токена. Такие токены называют JWE — JSON Web Encryption.
Скучные подробности можно почитать тут.
JWE token structure
jjwt не умеет JWE. А вот какой-нибудь сишарпный Jose — умеет.
private string EncodeToken(User user)
{
    var payload = new TokenData
    {
        Id = user.Id,
        Email = user.Email,
        Name = user.DisplayName,
        exp = NowTimestamp() + _tokenTtl
    };
    return Jose.JWT.Encode(payload, _tokenEncryptSecret,
        JweAlgorithm.PBES2_HS512_A256KW, JweEncryption.A256CBC_HS512, JweCompression.DEF);
}

private User DecodeToken(string token)
{
    var payload = Jose.JWT.Decode<TokenData>(token, _tokenEncryptSecret);
    if (payload.exp < NowTimestamp())
    {
        throw new Jose.IntegrityException("Token expired");
    }
    return new User
    {
        Id = payload.Id,
        Email = payload.Email,
        DisplayName = payload.Name
    };
}
Явисты, не расстраивайтесь. Для Явы тоже всё есть, просто другая библиотека.
JOSE — это Javascript Object Signing and Encryption. Общий термин, объединяющий JWT, JWS, JWE, а также JWK (JSON Web Key). Сначала добавляли буковку S — Simple, потом X — eXtensible, теперь, похоже, наступила мода на J.
JWT is JWS and JWE
Ещё раз. JWT — это самодостаточные токены, которые не требуют обращения к какой-либо БД, чтобы удостовериться, что этот токен был выдан определённому пользователю. Соответственно, их самих нет нужды хранить в какой-либо БД и делать по ним поиск.
Из этого проистекает недостаток: JWT токены почти невозможно отозвать. Ведь нет БД, с которой можно сверяться по вопросам валидности.
Конечно, есть тяжёлая артиллерия. Достаточно сменить ключ, которым подписываются и проверяются токены, на всех серверах. И все имеющиеся в ходу токены автоматически станут невалидными. В крайних случаях можно (и, пожалуй, нужно) поступать именно так.
А для уменьшения последствий компроментации в обычной жизни JWT токены нужно делать короткоживущими. Несколько часов, максимум дней.
Короткоживущие токены — это неудобно. Ведь юзеру придётся при протухании токена перелогиниваться.
Поэтому в OAuth используют два токена. Основной access token, короткоживущий, который может быть JWT, сам в себе содержит нужные данные и может быть проверен без доступа к БД. И refresh token, долгоживущий, может храниться и проверяться в БД, используется для обновления и выдачи нового access token.
Получается, мы можем получить все преимущества самодостаточности JWT, аутентифицируя тысячи запросов без лишнего обращения к БД, и при этом получить долгую, удобную для юзеров, сессию, с временем жизни refresh токена. Если, конечно, обновлять токены будем автоматически.