Это пример простейшего способа реализации MVCC, который указанным недостатком страдает. Пример нужен для понимания общего приципа, чтобы сходу не рассказывать о списках транзакций и куче системных полей. Далее следует описание того, как MVCC реализован в Postgres, и способ обхода проблем с блокировками.
Вы ошибаетесь, версионники тоже используют блокировки, так как невозможно в двух параллельных транзакциях обновить одну и ту же запись: одна из транзакций должна ожидать завершения другой (в данном случае минимально необходимым является row-level lock, который будет блокировать только писателей этой же записи). Вот описание блокировок Postgres. Вот описание блокировок Oracle
Согласен, «валидный» лучше заменить на «видимый», тогда это уточнение не потребуется, в момент написания статьи не нашел более подходящего термина. В целом в статье достаточно много допущений, сделанных с целью сокращения объема: уровни изоляции транзакций, блокировки, распределенные транзакции — каждая из этих тем достойна отдельной статьи
К Open Source аналогам Dremel относят Cloudera Impala, Apache Drill, Parquet (Twitter)
Parquet — это формат хранения данных. Он поколоночный, но ничего общего с иерархической организацией данных не имеет. С таким же успехом аналогом Dremel можно назвать любую СУБД, поддерживающую поколоночную организацию данных
Impala — решение класса SQL-on-Hadoop и в большей степени является аналогом Google F1, нежели Dremel, так как иерархическую организацию данных опять же не поддерживает
Зачем нужно синхронизировать critical state? Два кластера Colossus просто не знают о существовании друг друга, и знать им об этом не нужно. Посмотрите, например, на архитектуру Spanner (источник). Информация о местоположении находится на уровне location proxies и управляет ей placement driver, то есть это приложениезнает о том, в каком из датацентров находятся какие данные, а не файловая система
Про синхронизацию внутри пула мастер-серверов не скажу, но для этой задачи вполне подойдет шардинг метаданных по хэшу пути и синхронная master-slave репликация, хотя тут могут быть нюансы
Согласно официальной информации:
1. «The Spanner servers in each datacenter in turn retrieve their data from the Colossus File System (CFS) [14] in the same datacenter. Unlike Spanner, CFS is not a globally replicated service and therefore Spanner servers will never communicate with remote CFS instances» (источник)
2. «Storage Software: Colossus… Client-driven replication, ...» (источник)
Итого разумно предположить, что сам по себе Colossus:
а. Не поддерживает репликацию между несколькими датацентрами (маловероятно)
б. Поддерживает асинхронную репликацию в расположенные недалеко друг от друга датацентры с целью DR и не интерактивной аналитики
То есть вторая часть статьи неточна
И то, и другое — x86 сервера, на которых запускается Apache Hadoop и прочие компоненты экосистемы Hadoop (Hive, HBase, Pig, etc.). В случае IBM это их собственная сборка, в случае Oracle — это Cloudera Hadoop. Отличаются от дистрибутива Apache они дополнительным функционалом в контексте мониторинга кластера и прочих мелких автоматизаций вроде упрощения процесса внесения изменения в параметры Hadoop через веб-морду.
У каждого из вендоров обязательная фишка — он интегрируется с другими продуктами того же вендора. То есть если у вас есть DB2 или Netezza — очевидным решением будет IBM, если есть Oracle или Exadata — стоит брать Oracle.
Конечно, это всё платформы для крупного энтерпрайза (и железо, и софт поддерживается одним вендором, что очень любят банки и телеком), готового платить за open-source софт сотни тысяч долларов в год, чтобы иметь возможность получить поддержку в случае проблем. Про качество же поддержки open-source продуктов и в частности Hadoop можно почитать в статье Mail.ru о их приключениях с CDH
Судя по исходному коду, эта штука просто использует существовавшие и до этого параметры сессии: enable_seqscan, enable_indexscan, enable_bitmapscan, enable_tidscan и т.д., просто оборачивает их в подобие oracle hints
Если gpfdist смотрит на RAM-диск и Greenplum подключен по 10GbE, то использование writable external table даст скорость записи в 10Gbit/sec, реально около 1100 MB/sec. Дальше задача SAS по чтению результата из delimited-файла, но в итоге среднюю скорость в ~200MB/sec получить можно
Использование большего числа gpfdist должно подкрепляться архитектурой сети, иначе будут те же 10 Gbit/sec, хоть 1 gpfdist, хоть 10
>Передача данных из Greenplum в SAS всегда идет через master node и ограничена скоростью работы драйвера
На самом деле, в Greenplum есть Writable External Tables, то есть выгружать данные из Greenplum можно с той же скоростью, что и загружать. Вопрос в том, что SAS/Access for Greenplum пока не умеет их использовать, но обертку написать вполне можно
Если рассматривать оценку на шкале от 1 до 5 звездочек и считать оценку 5 за «отлично», а 1 за «ужасно», то перед использованием косинусной меры можно произвести нормализацию оценок, вычтя из оценки мат. ожидание. Если принять мат. ожидание за 3.0 и не обращать внимание на проблему с нулевым вектором предпочтений для человека, который всем продуктам ставит 3.0, то мы получим следующий код:
def distCosine (vecA, vecB):
def dotProduct (x, y):
d = 0.0
for dim in x:
if dim in y:
d += (x[dim]-3.0)*(y[dim]-3.0)
return d
return dotProduct (vecA, vecB) / math.sqrt(dotProduct(vecA,vecA)) / math.sqrt(dotProduct(vecB,vecB))
Он показывает схожесть Ивана с Алексом 0.3651, а с Дэвидом 0.3333
В то же время нужно понимать, что рекомендательные системы могут строиться на основании разных данных, и если в одной задаче мы оперируем с оценками «от 1 до 5 звездочек», то в другой задаче это может быть «1 для просмотра и 2 для покупки», в третьей — «количество фактов оказания услуги». В каждой из таких систем должен быть свой подход к подготовке данных и выбору меры сходства
Это более корректно, так как (1, 1, 0) и (0, 0, 1) вообще не имеют общих оценок. Допустим, один человек посмотрел фильмы «Аватар» и «Бэтмен» и поставил им оценку «1», а другой — фильм «Начало» и поставил ему «1». И первому порекомендуют посмотреть фильм «Начало» на основании данных второго пользователя, хотя они смотрят совсем разные фильмы и вкусы из скорее всего расходятся
В данном случае под «0» понимается не какая-либо оценка, а отсутствие оценки — это допущение, которое необходимо для работы косинусной меры и евклидова расстояния. Если при вычислении расстояния использовать только совпадающие оценки, не будет учитываться общее количество оценок, и пользователь с оценками (1, 0, 0, 0, 0, 0, 0) будет одинаково похож как на (1, 1, 0, 0, 0, 0, 0), так и на (1, 1, 1, 1, 1, 1, 1)
В целом, косинусная мера — это именно косинус угла между векторами, а для вычисления его используется полная длина векторов, а не только длина по совпадающим измерениям
Вопрос выбора метрики нетривиален, его я хочу описать в отдельной статье. Это, действительно, один из недостатков косинусной меры. Вместо неё можно использовать тот же коэффициент корреляции Пирсона, но и он не идеален: так как боб поставил всего две оценки и обе они являются пятерками, то дисперсия его оценок равна нулю и коэффициент корреляции не определен, так что в формулу вычисления коэффициента корреляции придется добавлять сглаживающие коэффициенты.
Также можно произвести бинаризацию оценок: оценки больше или равные мат. ожиданию оценки данного пользователя заменяются на «1», а меньшие на «0». После этого можно будет применить одну из следующих мер: Жаккарда, Танимото и т.д.
В целом, выбор меры зависит от конкретной задачи, а корректность выбранной меры можно проверить тем же k-Fold + RMSE. Иногда оказывается полезно использовать линейную комбинацию нескольких мер + средний рейтинг продукта, коэффициенты можно подобрать при помощи линейной регрессии
Интересно, что решение, выигравшее миллион долларов, так и не было внедрено в production, подробнее в статье: «If you followed the Prize competition, you might be wondering what happened with the final Grand Prize ensemble that won the $1M two years later. This is a truly impressive compilation and culmination of years of work, blending hundreds of predictive models to finally cross the finish line. We evaluated some of the new methods offline but the additional accuracy gains that we measured did not seem to justify the engineering effort needed to bring them into a production environment. Also, our focus on improving Netflix personalization had shifted to the next level by then. In the remainder of this post we will explain how and why it has shifted.»
Там ошибка. Косинусная метрика — это косинус угла между векторами, и в знаменателе должны стоять полные длины
По поводу использования метрик: предположим, у нас есть три вектора (10, 10, 1), (1, 1, 0) и (0, 0, 1). Согласно евклидовому расстоянию наиболее близки вектора 2 и 3, а по косинусной метрике — 1 и 2, что более корректно.
Выбор метрики обусловлен конкретной задачей
ваш код при вычислении длины вектора учитывает только те компоненты, которые являются общими для векторов userA и userB
Как оптимизация для расчета, длину векторов можно вычислить заранее, так как меняется она только при совершении покупки (или просмотра, в зависимости от того, как работает ваша система)
Чаще всего в рекомендательных системах используется алгоритм коллаборативной фильтрации, я рекомендую для начала ознакомиться с ним (википедия). В качестве меры сходства можно начать с косинусной меры:
В данном случае kNN — это просто способ отфильтровать k пользователей с наиболее похожими вкусами, чтобы применять алгоритм коллаборативной фильтрации только к ним
k-Means в данном случае может быть использован для предварительного сегментирования пользователей, в том случае, если производительность системы не позволяет для каждой из рекомендаций рассчитывать меру сходства со всеми пользователями: можно будет ограничиться одним кластером
Итого, ваш алгоритм может выглядеть следующим образом: регулярно (раз в день / N дней) производится кластеризация пользователей. При необходимости вычисления рекомендации производится вычисление косинусной меры сходства только с пользователями, находящимися в том же кластере, что и рассматриваемый. Из получившихся мер сходства выбирается k лучших, для них и применяется коллаборативная фильтрация.
При такой реализации нужно обратить внимание на количество кластеров и размер k — эти параметры отвечают за баланс между скоростью работы и точностью рекомендации.
Также можно хранить предрасчитанные стандартные рекомендации для новых пользователей, а для пользователей, которые уже имеют покупки, но не участвовали в кластеризации, можно расчитать сначала меру сходства с центроидами, полученными в ходе k-means, таким образом определив их кластер
За примерами стоит обратиться к книге из п.5 списка литературы к статье
Вы ошибаетесь, версионники тоже используют блокировки, так как невозможно в двух параллельных транзакциях обновить одну и ту же запись: одна из транзакций должна ожидать завершения другой (в данном случае минимально необходимым является row-level lock, который будет блокировать только писателей этой же записи). Вот описание блокировок Postgres. Вот описание блокировок Oracle
12345678910 = 1*(104)2 + 2345*(104)1 + 6789*(104)0
Parquet — это формат хранения данных. Он поколоночный, но ничего общего с иерархической организацией данных не имеет. С таким же успехом аналогом Dremel можно назвать любую СУБД, поддерживающую поколоночную организацию данных
Impala — решение класса SQL-on-Hadoop и в большей степени является аналогом Google F1, нежели Dremel, так как иерархическую организацию данных опять же не поддерживает
Про синхронизацию внутри пула мастер-серверов не скажу, но для этой задачи вполне подойдет шардинг метаданных по хэшу пути и синхронная master-slave репликация, хотя тут могут быть нюансы
1. «The Spanner servers in each datacenter in turn retrieve their data from the Colossus File System (CFS) [14] in the same datacenter. Unlike Spanner, CFS is not a globally replicated service and therefore Spanner servers will never communicate with remote CFS instances» (источник)
2. «Storage Software: Colossus… Client-driven replication, ...» (источник)
Итого разумно предположить, что сам по себе Colossus:
а. Не поддерживает репликацию между несколькими датацентрами (маловероятно)
б. Поддерживает асинхронную репликацию в расположенные недалеко друг от друга датацентры с целью DR и не интерактивной аналитики
То есть вторая часть статьи неточна
Работает под Oracle Unbreakable Linux, что по сути RHEL
У каждого из вендоров обязательная фишка — он интегрируется с другими продуктами того же вендора. То есть если у вас есть DB2 или Netezza — очевидным решением будет IBM, если есть Oracle или Exadata — стоит брать Oracle.
Конечно, это всё платформы для крупного энтерпрайза (и железо, и софт поддерживается одним вендором, что очень любят банки и телеком), готового платить за open-source софт сотни тысяч долларов в год, чтобы иметь возможность получить поддержку в случае проблем. Про качество же поддержки open-source продуктов и в частности Hadoop можно почитать в статье Mail.ru о их приключениях с CDH
Использование большего числа gpfdist должно подкрепляться архитектурой сети, иначе будут те же 10 Gbit/sec, хоть 1 gpfdist, хоть 10
На самом деле, в Greenplum есть Writable External Tables, то есть выгружать данные из Greenplum можно с той же скоростью, что и загружать. Вопрос в том, что SAS/Access for Greenplum пока не умеет их использовать, но обертку написать вполне можно
Он показывает схожесть Ивана с Алексом 0.3651, а с Дэвидом 0.3333
В то же время нужно понимать, что рекомендательные системы могут строиться на основании разных данных, и если в одной задаче мы оперируем с оценками «от 1 до 5 звездочек», то в другой задаче это может быть «1 для просмотра и 2 для покупки», в третьей — «количество фактов оказания услуги». В каждой из таких систем должен быть свой подход к подготовке данных и выбору меры сходства
В данном случае под «0» понимается не какая-либо оценка, а отсутствие оценки — это допущение, которое необходимо для работы косинусной меры и евклидова расстояния. Если при вычислении расстояния использовать только совпадающие оценки, не будет учитываться общее количество оценок, и пользователь с оценками (1, 0, 0, 0, 0, 0, 0) будет одинаково похож как на (1, 1, 0, 0, 0, 0, 0), так и на (1, 1, 1, 1, 1, 1, 1)
Вопрос выбора метрики нетривиален, его я хочу описать в отдельной статье. Это, действительно, один из недостатков косинусной меры. Вместо неё можно использовать тот же коэффициент корреляции Пирсона, но и он не идеален: так как боб поставил всего две оценки и обе они являются пятерками, то дисперсия его оценок равна нулю и коэффициент корреляции не определен, так что в формулу вычисления коэффициента корреляции придется добавлять сглаживающие коэффициенты.
Также можно произвести бинаризацию оценок: оценки больше или равные мат. ожиданию оценки данного пользователя заменяются на «1», а меньшие на «0». После этого можно будет применить одну из следующих мер: Жаккарда, Танимото и т.д.
В целом, выбор меры зависит от конкретной задачи, а корректность выбранной меры можно проверить тем же k-Fold + RMSE. Иногда оказывается полезно использовать линейную комбинацию нескольких мер + средний рейтинг продукта, коэффициенты можно подобрать при помощи линейной регрессии
«If you followed the Prize competition, you might be wondering what happened with the final Grand Prize ensemble that won the $1M two years later. This is a truly impressive compilation and culmination of years of work, blending hundreds of predictive models to finally cross the finish line. We evaluated some of the new methods offline but the additional accuracy gains that we measured did not seem to justify the engineering effort needed to bring them into a production environment. Also, our focus on improving Netflix personalization had shifted to the next level by then. In the remainder of this post we will explain how and why it has shifted.»
По поводу использования метрик: предположим, у нас есть три вектора (10, 10, 1), (1, 1, 0) и (0, 0, 1). Согласно евклидовому расстоянию наиболее близки вектора 2 и 3, а по косинусной метрике — 1 и 2, что более корректно.
Выбор метрики обусловлен конкретной задачей
Как оптимизация для расчета, длину векторов можно вычислить заранее, так как меняется она только при совершении покупки (или просмотра, в зависимости от того, как работает ваша система)
В данном случае kNN — это просто способ отфильтровать k пользователей с наиболее похожими вкусами, чтобы применять алгоритм коллаборативной фильтрации только к ним
k-Means в данном случае может быть использован для предварительного сегментирования пользователей, в том случае, если производительность системы не позволяет для каждой из рекомендаций рассчитывать меру сходства со всеми пользователями: можно будет ограничиться одним кластером
Итого, ваш алгоритм может выглядеть следующим образом: регулярно (раз в день / N дней) производится кластеризация пользователей. При необходимости вычисления рекомендации производится вычисление косинусной меры сходства только с пользователями, находящимися в том же кластере, что и рассматриваемый. Из получившихся мер сходства выбирается k лучших, для них и применяется коллаборативная фильтрация.
При такой реализации нужно обратить внимание на количество кластеров и размер k — эти параметры отвечают за баланс между скоростью работы и точностью рекомендации.
Также можно хранить предрасчитанные стандартные рекомендации для новых пользователей, а для пользователей, которые уже имеют покупки, но не участвовали в кластеризации, можно расчитать сначала меру сходства с центроидами, полученными в ходе k-means, таким образом определив их кластер
За примерами стоит обратиться к книге из п.5 списка литературы к статье