Возможные изменения в OSM xml, API

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

Как поменять OSM XML.

  1. OSM XML - замечательный формат и, наверное, единственный замечательный формат. Он любому новому человеку позволяет понять “что-такое” OSM, просто взяв и открыв файл, и при некоторой сторонней помощи (wiki или человек) можно понять, что и как обозначается. Благо сущностей в нем всего 4: node, way, relation/members, tags. Дальше можно провести аналогию с частью большого и сказать, что это маленький кусочек OSM, а вот OpenStreetMap - это planet.osm.bz2 (50 GB).
    Этот формат отличный, он позволяет начать программировать (скриптовать-автоматизировать) на любом языке с минимумом документацией, библиотеками и с максимумом пониманием. К сожалению, достаточно быстро возникают очевидные проблемы.
    Многие могут подумать, что формат для человека и для машины это 2 абсолютно разных формата. На самом деле это не так, главное преимущество OSM, в том, что программисты тоже люди и когда они приходят им нужно разбираться, чтобы написать программу. Сила crowdsource, не в том что у нас есть 2-3 opensource тула, а в том, что в любой момент к нам могут присоединиться новые авторы-программисты и вывести проект на другой уровень. Присоединиться к существующему opensource проекту гораздо сложнее, чем кажется. Поэтому простота и мощь формата обеспечивает обучаемость человека, решаемость повседневных задач простыми средствами. Большинство из наших OSM-авторов умеет пользоваться скриптами, сложными редакторами (vi например), главная проблема кто-то знает python, кто-то perl, bash поэтому формат данных должен быть просто понятен. Я попытаюсь описать основные пункты улучшения формата и объяснить, чем они могут понять разным людям.
  • Ввести понятие quad-tree в формат. Для любого человека проблема найти что-то в более-менее большом osm.xml файле, в большинстве случаев остается только один вариант, зайти на OSM.org и скачать маленький кусочек того, что тебе нужно. Что делает не практичным возиться с большими файлами, к сожалению такая задача часто возникает при отладке. Имеется osm.xml и надо посмотреть, что в нем, но вопрос упирается, что невозможно эффективно вырезать из него кусок, используя текстовый редактор. В данном случае нужно использовать специальные тулы osmconvert. Если подумать, то эти тулы тоже решают сложную задачу, которая могла быть решена самим форматом. Ведь для того, чтобы вырезать надо посчитать bbox, а если прямо в файле по некоторому id или имени можно найти и вырезать, то, несомненно это упростило бы жизнь.

  • Как ни странно это звучит, но надо поменять геометрию и сортировку. Сейчас для того, чтобы вырезать некоторый кусок постоянно приходится читать или 2 раза или строить кеш из всех nodes. Основная проблема, что невозможно написать streamline алгоритм почти для любой практической задачи. Потому что, существует 2 типа запросов по карте (bbox упрощенно) и по типам объектов и для любого из этого запросов необходимо делать join node-way. Для решения этой задачи нужно прописать геометрию внутри объекта с тегами. Несомненно мы можем получить некоторую дубликацию данных, но это незначительный объем. По поводу сортировки, то необходимо, сначала писать relation, а затем объекты с геометрией. Тогда можно достаточно просто при проходе профильтровать по тегам, а затем объединить с геометрией. Обычно количество relation во много раз меньше, чем геометрии, поэтому можно безопасно хранить в памяти. Можно отсортировать relation, чтобы сверху были relation, которые используют другие relation, а внизу, которые не используют

  1. Расширение OSM XML дополнительными файлами.
    На самом деле если предположить, что мы хотим оставить существующие форматы как есть, то можно попытаться не менять osm.xml, а сделать новый формат osm.xml.zip. И построить quad-tree индекс, например, внутри zip.
  • Как это могло бы выглядеть.
    osm.zip - содержит список osm.gz raw-файлы , которого являются quad-tree по алгоритму shortlink (ссылка на osm shortlink, т.е. AFAF.osm.gz покрывает AFAFBB, AFAFCC и т.п. квадраты). Каждый файл, содержит строго объекты внутри, объекты выходящии за рамки квадрата идут на уровень выше и т.п., для того, чтобы не разделять геометрию на границе quad-tree обычно строятся с некоторым наложением, что является некоторым неудобством, но вполне приемлимым решением. Вполне возможно допустить дубликацию данных на соседних тайлах.
  • Можно также построить tag_info.txt файлы для каждого quad-tree тайла, чтобы упростить поиск объекта. Вполне возможно его строить динамически для всей планеты, количество тегов является ограниченным числом и индекс со ссылкой на квадрат, в котором содержатся объекты является достаточно емкой, но удобной информацией, так же можно указать число объектов с этим тегом.
    Для value можно построить 3-буквенный индекс или больше букв, в зависимости от размера тайла. Для маленьких тайлов это вполне может быть словарный индекс, любое архивирование osm и индекса вместе, сможет прекрасно вычленить дубликаты.

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

  1. Таким образом мы подходим к вопросу, как же получить этот формат и поддерживать. Главное, что необходимо в решение задач нового формата, чтобы его обслуживания было простым и понятным. Преимущество “многофайлового” формата, что с ним можно работать распределенно. Можно так же обновлять частично, т.е. разные файлы. Правда совместно с этим приходят и проблемы. Самая главная задача, которую как мне кажется невозможно решать “без центрального сервера” нацеленного на этот формат, это provider “улучшенных” osmc. К сожалению сегодня osmc не содержат достаточно геометрия, без этого невозможно распределенно или частично обновлять существующие тайлы, по крайней мере не сканируя их всех. В принципе это замедляет весь процесс обновления! обновить планету даже на маленький osmc требует 20 минут, просто потому что весь файл перечитывается и переписывается. В новом формате этого можно избежать, и чтения и записи! Если можно сделать osmc api, то единственное, что необходимо и это можно сделать в backward compatible manner, что сущ-ие программы не сломаются.

  2. Описанные изменения ведут к немного большему, чем просто изменение формата. Хочется поменять какие объекты мы имеем в OSM API, добавить multipolygon, но от этого настоятельно стоит воздержаться, если мы не научимся строить backward compatible изменения в API (то есть не меняя его вообще), скорость изменения API будет падать, пока не достигнет 0. Необходимо найти возможность сосуществовать с текущим API и пользоваться преимуществами нового.

Однако мы не должны думать о новых объектах иначе мы не найдем золотую середину.

К примеру, вот некоторые идеи, описанные отдельно. В распределенном по тайлам формате необходимо отказаться от связок через id.

  1. Отказ от node id в way
    Недостатки:
    Теряется связь между way и node (сейчас можно проверять, что node имеет тот же id что и в way) или невозможно понять что 2 way пересекаются (для решения см. 3).
    Преимущества:
    Возможность редактировать каждый way отдельно. Возможность без join найти полноценный геометрический объект и найти его координаты.
  2. Отказаться в relation от использования member id. Member должны определяться, через теги.
    Недостатки:
    - в объекте relation невозможно, просмотреть список объектов. Его и сейчас невозможно просмотреть, кроме id, остальное надо мерджить.
    Преимущества:
    - на member объектах отображается достаточно информации обо всех relation. К примеру на остановке, будет подписано какие автобусы на ней останавливаются. Пример тег: bus:62=
  3. Ввести специальный объект для описания взаимоотношений между геометрическими объектами.
    Примеры:
    • Объект 1 содержится в объекте 2 (валидация)
    • Объект 1 пересекается с объектом 2 в точке. Теги допустимы для описания запрещенных маневров к примеру.
    • Объект 1 следует за объектом 2. (Автобусные остановки)
      — Взаимоотношение между геометрией не ограничено конкретным списком, а является free style editing.
      — Взаимоотношения в отличие от сущ-х relation являются локальными для одного файла, соответственно нельзя описать через “геометрические отношения” выразить admin_level=2.

Послесловие: суммируя все изменения, вырисовывается одна простая и понятная цель, неообходимо придумать такой текстовый формат, который будет удобно читать, искать, редактировать, обновлять и иметь у себя под рукой (в смысле объема на PC, хотя бы интересующей части). Как ни странно, если что-то будет удобно делать руками, автоматизация тоже получится простой и понятной.
Текст map editing кажется crazy, но, кажется, это дает интересные результаты.

Вот что типы данных надо разделить, меня давно посещали такие мысли. И zip вполне подходит, ведь живут же новые офисные файлы с такими тараканами.
Индексы тоже хорошо, но скорей всего их придётся делать у себя локально. Т.е. один раз проиндексировал у себя планету, долго. Потом индексируешь прилетевшие дифы, их уже быстро. В итоге мерж получится тоже быстро.
А вот с последней частью я не согласен. Это вообще сломает всё старое к чёрту, а большого бонуса не даёт. Понимается с трудом.

В основные дампе не нужно, уже есть отдельный инструмент: overpass-turbo.eu

обновляйте, переводите
http://wiki.openstreetmap.org/wiki/Overpass_turbo
http://wiki.openstreetmap.org/wiki/Overpass_turbo/Examples
http://wiki.openstreetmap.org/wiki/Overpass_turbo/Wizard

Большинство запросов сводится к материализованным индексам (вроде "tag_info.txt файлы для каждого quad-tree тайла, чтобы упростить поиск объекта).

Напоминаю что https://ru.wikipedia.org/wiki/Когерентность_кэша это одна из самых сложных задач. Не делайте материализацию индексов вручную.

Для postgres человеко-читаемых форматов хранения бинлога и индексов я не встречал.

Понятно для чего это, но не выйдет:

  1. для дорожного графа обязательны “общие точки”
  2. что делать с лежачими полицейскими, блоками и прочим? у них есть теги и они участники линий

Не нужно делать на упор в хранение .txt файлов. Лучше прикрутить виртуальную файловую систему которая всё будет представлять в виде “файлов” или псевдо-git: https://en.wikipedia.org/wiki/Virtual_file_system

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

Не должно быть такого чтобы сделать какую-то правку нужно знать как 3-6 индексов ещё обновлять кроме самих данных-изменений

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

  1. Человекочитаемые и человекоредактируемые форматы необходимы! Postgresql - не является crowdsource проектом. Такие форматы облегчают жизнь и разработку новых тулов “непрофессионалами”, они поощряют исследования. Для работы с бинарными форматами уже нужен хороший язык программирования и библиотеки и самое главное техническим людям непрограммистам придется очень непросто.
  2. Если человек захочет написать любой полезный сервис на скрипте, ему надо потратить “много часов” на импорт OSM API. Если представить, что человек ограничит себя выбором только одной страны, то рано или поздно перед ним встанет вопрос масштабирования, который осуществить будет сложно. И это не считая, что сервис или утилиту придется писать используя БД. Никто не говорит, что БД это плохо, но много людей предпочитают работать с файлами, для это можно сравнить сколько идет загрузок с geofabrik, а сколько подымают локальные БД.

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

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

Mapnik - это преобразовать osm.xml → image. Да это не куча запросов к БД, это просто стриминг, с очень эффективным кешем. Главное преимущество, не в том, что результат выглядит по другому, а в том, что разработка существенно проще.

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

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

OSM полностью заточен на центральные сервера, хотя distributed technologies развиваются стремительно.

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

По существу: в OSM существует только геометрия точек! Странным образом точки имеют теги. Т.е. получается, что из физической геометрии линии, мультиполигоны, полигоны, …, только точки имеют теги. Линии не имеют геометрия она вся произведена точками! Плохо получилось с полигонами, потому что они приравнялись к линиям (плохо потому что документация различает линии и полигоны, а вот картографирование нет), а с мультиполигонами вообще плохо получилось их вывели даже не через точки, а через линии.
Что плохого, что точки имеют теги? Плохо то, что работать с точками легко и просто, надобавлял точек прописал и готово. И понять легко и работать просто, хоть с текстовым файлом.
Из-за этого большинство тулов и картографов тоже, начинают использовать точки не так как хотелось бы, например, проставлять номера домов не на домах, проставлять подъезды не на домах, а внутри и т.п. Что усложняет работу другим тулам, а это значит тормозит развитие OSM в целом. Если какая-то фича трудная и ее не получается сделать хорошо в >20% продуктах, она вообще не будет картографироваться нормально!

Вернемся к геометрии точек. В принципе, это естественно, но хватает ли нам ее? Если бы геометрия нам позволяла иметь линию, точку и полигон, много задач упростилось, но возникли описанные сложности. Во-первых мультилиния, мультиполигон - по-прежнему недоступны, во-вторых непонятно как делать интеграцию между точками и линиями, как справедливо, замечено для графа дорог.

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

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

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

Понятно для чего это всё предлагается. Коротко прокомментирую один момент

Некорректное сравнение, я не случайно привёл ссылку на виртуальную файловую систему.

“файл” это абстрация ВФС/ФС. ВФС/ФС обычно опетирует на блочных устройствах или на “крутом” железе с нестандартной/заточеной архитектурой.

Вопрос “как хранить” это к блочным устройствам и “сегодняшним” ограничениям HDD/SSD/RAM и даже кешей проца.

Ничто не мешает написать файловую систему/API который будет представлять байтики в виде XML/TXT/GEOJSON/GIT дерева.

Просто один пример и про высказывание (“Postgresql - не является crowdsource проектом”). MYSQL не является crowdsource проектом. Wikipedia/Wikidata использует её до сих пор(?) как бекенд.

Почему mysql/postgresql?

  • потому что индексы не велосипедить. Особенно PostGIS (гео-индексы это ой не простая тема, т.к. численная стабильность, топология и все дела) https://en.wikipedia.org/wiki/PostGIS#Users - не критерий для выбора бекэнда, но всё же
  • потому что десятки лет тестировалось в продакшене, большими компаниями и исследователями в БД (у “монгодб” такие исследования начинаются с “обнаружена ещё одна уязвимость 0day …”).

Абсолютно верно замечено что масштабировать не просто. В отличие от той же Википедии и Wikidata они не работают с гео-данными (читай проблемы чуть выше)

Для общего развития, обзорное видео про историю разработки Neo4j: https://www.youtube.com/watch?v=Vfz–5hX5qs Neo4j Spatial - Craig Taverner

PS. на русском субтитров нет (пока)

Я вообще хочу избежать классических индексов, за счет того, что разбиение на тайлы 15 зума не предполагает их, то есть можно спокойно прочитать весь osm.gz, чтобы найти 3-буквенные анаграммы и используемые теги, на высших уровнях мы можем агрегировать низшие.
Смотрю видео про neo-4j, Quad-tree дерево решает проблему древовидного поиска, мы сразу знаем в каком тайле надо искать.

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

Не хочу занижать успехи Neo4j Spatial, но заявления O(1) крайне голословны когда идёт речь о IO интенсивных операциях. У жёстких дисков не бывает ответов за O(1) в принципе, у них всё в миллисекундах, в количестве операций и гарантированном времени доступа.

  • нужно тестировать на реальных osm-workload (последняя неделя/месяц ченджсетов из OSM), причём кто быстрее: старый стек или новый
  • нужно смотреть производительность в ms
  • нужно смотреть полностью ли утилизируется железо

Да, решает. По крайней мере, в теории это всё красиво и просто. Лично мне этот вариант симпатичен, но большой вопрос подойдёт ли новая структура для всех/большинства пользователей(редакторов).

Прямо сейчас я не знаю много ли лишнего в https://github.com/neo4j-contrib/spatial и стоит ли присоединяться либо просто использовать только их разработки вместо собственных и помогать им.

Всеравно нужен индекс id <=> тайл, (osc которые генерят для планеты покамест никто не переделывал, там вроде есть BBOX но он не всегда поможет, т.к. есть правки которые покрывают сразу весь мир). Дальше надо эти индексы (quad-tree и id <=> тайл) синхронизовать.

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

Человекопонятность не нужна - нужен досконально документированный формат, а для ленивых библиотеки :slight_smile:

Он был и есть прямо сейчас в OSM:

WAL лог для хранения правок
http://www.postgresql.org/docs/9.5/static/wal-reliability.html
http://www.postgresql.org/docs/9.5/static/wal-configuration.html
http://www.postgresql.org/docs/9.5/static/wal-internals.html

https://www.pgcon.org/2012/schedule/attachments/258_212_Internals%20Of%20PostgreSQL%20Wal.pdf

Для ленивых - PostgreSQL, SQL.

Будете изобретать свои структуры - потеряете репликацию и будете велосипедить WAL (минутные правки это редкая мерзость и велосипедизм).

Разница postgresql подхода и OSM подхода, у нас нет скачек PSQL базы данных. Дампы базы разрезать на тайлы еще та сложность. Если мы говорим про distributed database, то они все построены на принципе, что подключение равнозначное и точно не read-only. Самый близкий проект, как ни странно, это Bitcoin - blockchain, распределенная БД платежей. Любой качает дамп, подключается и он в строю и получает мгновенные обновления + любой “доверенный” может контрибутить обратно. Я не говорю, что это perfect match, тут явно не хватает, чтобы можно было скачать дамп некоторого региона, а не всей планеты

https://blockchain.info/charts/blocks-size - не в сжатом 43GB? как посчитать количество элементов/“правок” там?

вообще идея сумасшедшая, но четыре тайлика можно составить в биткоиновских структрурах?

Если кто-то им деньги доверяет хранить + всю историю, то почему бы там OSM не хранить? другое дело как там Quad-tree организовать?

Какие там гарантии получения полной “базы”? Если с HTTP протоколом ожидания по времени можно предсказать, то как ведёт себя blockchain?

Ну тут возможно извращение с функциональными индексами

Посмотри формат mapsforge там насколько я помню тайлы играют важную роль

Saint_Byte дак там они (тайлы) уже нарезаны. Индекс id-tile прежде всего нужен при построении геометрии линий. Потом запрсы дай мне что-то по id уже не шибко нужны…

В основном это для просмотра комментариев в истории/просмотра тегов которые у объекта сейчас. Т.е. можно кешировать до какой-то разумной степени.

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

С другой стороны комментарии можно сделать к тайлам?! Но тогда потеряется связь объектами которые комментируют. Это важно при правке скажем админ-границ, чтобы в истории линий добавлялись нужные комментарии.

Я не рассчитываю что такой способ хранения заменит механизм на котором основан API, в лучшем случае я расчитываю поднять реплику планеты, с данными организованными в такую структуру. Соответсвенно история и коментарии мне не нужны. Для получения истории и объекта по id у нас сервисы есть. А вот данных в формате удобном для дальнейшей бработки - нету.

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