Поиск ближайшего или самого дальнего местоположения очень прост благодаря DynamoDB и небольшому пакету геокодирования NPM
Многие наборы данных теперь включают геопространственную информацию, особенно если вы работаете с мобильными приложениями или Google Maps. Геопространственные данные - это причудливый способ описания элементов, содержащих широту и долготу, но обрабатывающих запросы на основе ближайшего, самого дальнего или в пределах определенного расстояния имеет некоторую сложность.
Почему это сложно? Представьте, что у вас есть 10 розничных магазинов, и покупатель хочет знать, где они находятся. Очевидный способ - определить местонахождение покупателя, а затем рассчитать расстояние между этим местом и каждым из магазинов. В чем проблема?
Что ж, есть две проблемы: первая заключается в том, что предыдущий расчет предполагает, что две точки находятся на плоской поверхности, а мир не плоский (на самом деле, это не так). Вы должны учитывать округлость камня, на котором мы живем, что подводит нас к формуле Хаверсина.
В то время как первая проблема приведет к ошибкам вычислений, вторая проблема гораздо более проблематична. По мере увеличения количества розничных магазинов скорость поиска замедляется - ужасное O (n) - потому что вы должны сравнивать местоположение пользователя с каждым магазином. А что, если пользователь перемещается, поэтому исходное местоположение часто обновляется?
Если вы расширите задачу до «найти ближайшую кофейню», наше первое решение потребует от нас сравнения местоположения пользователя с каждой кофейней на планете. Так что нам нужен гораздо лучший способ решения вопроса, и желательно такой, который может управлять глобальным масштабом. По сути, примерно так, как это делает Google Maps.
Сила Geohash
Геохеши немного сложны, но главное, что нужно знать, это то, что они делят мир на несколько квадратов в сетке. Таким образом мы можем заранее удалить большую часть данных и сосредоточиться только на той области, в которой находятся наши потенциальные цели. Это довольно элегантное решение.
- Длина хэша составляет до 12 символов - чем длиннее хеш, тем меньше квадрат, на который он ссылается.
- Первый символ хеша обозначает одну из 32 ячеек в сетке размером примерно 5000 x 5000 км на планете.
- Второй символ идентифицирует один из 32 квадратов в первой ячейке, поэтому разрешение двух вместе взятых символов теперь составляет 1250 км x 1250 км.
- Это продолжается до двенадцатого символа, который может определить площадь всего в пару квадратных дюймов на Земле.
Если вы используете слишком длинный хеш - другими словами, квадраты слишком маленькие - вы в конечном итоге будете искать результаты в большем количестве квадратов. Если вы используете слишком короткий хэш, вы вернете слишком много элементов в квадрате, и ваш поиск будет не очень быстрым. Поэтому вам нужно знать разрешение вашего поиска, прежде чем выбирать длину хеша.
Это может показаться трудным, но это проще, чем вы думаете. В нашем примере поиска розничных магазинов и кафе необязательно иметь двухдюймовую сетку с изображением планеты. Мы можем разрешить поиск на 1–10 километров с помощью 5–7 символов.
Библиотека гео для Amazon DynamoDB
В 2013 году есть сообщение в блоге AWS, в котором подробно рассказывается о библиотеке Geo, но это решение для Java, которому требуется сервер. Совсем недавно появился пакет NPM, который переносит эту работу на Node и может использоваться в бессерверной архитектуре.
Чтобы проверить это, я нашел список всех локаций Starbucks в США, а затем обнаружил ссылку, по которой кто-то превратил это в JSON. Следуя документации в пакете NPM, я собрал этот скрипт для настройки таблицы DynamoDB и загрузки в нее данных.
Позвольте мне рассказать вам об основных моментах.
Во-первых, давайте создадим таблицу, которая раскроет новую таблицу DynamoDB с ключом partitionKey и индексами, необходимыми для работы поиска.
const ddbGeo = require('dynamodb-geo')
const config = new ddbGeo.GeoDataManagerConfiguration(ddb, 'yourTableName')
config.hashKeyLength = 5
const myGeoTableManager = new ddbGeo.GeoDataManager(config)
const setupTable = () => {
const createTableInput = ddbGeo.GeoTableUtil.getCreateTableRequest(config)
createTableInput.ProvisionedThroughput.ReadCapacityUnits = 5
console.dir(createTableInput, { depth: null })
ddb.createTable(createTableInput).promise()
.then(function () { return ddb.waitFor('tableExists', { TableName: config.tableName }).promise() })
.then(function () { console.log('Table created and ready!') })
}
Затем загружаем данные:
const loadTable = () => {
const data = require('../data/starbucks_us_locations')
const putPointInputs = data.map(function (location) {
return {
RangeKeyValue: { S: uuid.v4() }
GeoPoint: {
latitude: location.position.lat,
longitude: location.position.lng
},
PutItemInput: {
Item: {
name: { S: location.name },
address: { S: location.address }
}
}
}
})
const BATCH_SIZE = 25
const WAIT_BETWEEN_BATCHES_MS = 1000
let currentBatch = 1
function resumeWriting() {
if (putPointInputs.length === 0) return Promise.resolve()
const thisBatch = []
for (let i = 0, itemToAdd = null; i < BATCH_SIZE && (itemToAdd = putPointInputs.shift()); i++) {
thisBatch.push(itemToAdd)
}
console.log('Writing batch ' + (currentBatch++) + '/' + Math.ceil(data.length / BATCH_SIZE))
return myGeoTableManager.batchWritePoints(thisBatch).promise()
.then(function () {
return new Promise(function (resolve) {
setInterval(resolve,WAIT_BETWEEN_BATCHES_MS)
})
})
.then(function () {
return resumeWriting()
})
}
return resumeWriting().catch(function (error) {
console.warn(error)
})
}
Это загружает местоположения Starbucks из файла json, создает массив элементов для вставки в таблицы и загружает в DynamoDB партиями по 25 элементов. Между каждым пакетом вводится задержка, чтобы замедлить процесс вставки и уменьшить сжигание единиц емкости записи (WCU).
После загрузки вы можете увидеть все местоположения вместе с их значениями геохеша и хеш-ключами, которые были автоматически рассчитаны библиотекой:
Когда данные загружены, запросы просты - мы просто указываем широту и долготу места поиска вместе с радиусом области поиска:
const AWS = require('aws-sdk')
AWS.config.update({region: 'us-east-1'})
const ddb = new AWS.DynamoDB()
const ddbGeo = require('dynamodb-geo')
const config = new ddbGeo.GeoDataManagerConfiguration(ddb, 'yourTableName')
config.hashKeyLength = 5
const myGeoTableManager = new ddbGeo.GeoDataManager(config)
myGeoTableManager.queryRadius({
RadiusInMeter: 1000,
CenterPoint: {
latitude: 40.7769099,
longitude: -73.9822532
}
})
.then((locations) => console.log(locations))
Давай попробуем!
Я построил простой интерфейс, который использует список данных Starbucks, чтобы показать ближайший Starbucks в пределах 1 километра - по умолчанию это Нью-Йорк, поскольку это выглядит как наиболее плотно заполненное место для их магазинов.
Если вы щелкнете по карте, он получит список из DynamoDB на основе нового центра карты:
В целом преимущество использования DynamoDB для этого решения заключается в чрезвычайно стабильной работе под нагрузкой. Благодаря тому, что DynamoDB теперь предоставляет ресурсы по требованию, он может обрабатывать пиковый трафик без необходимости управлять выделенной пропускной способностью.
Дайте мне знать, что вы думаете, в комментариях ниже!
