Первый шаг — сбалансировать выдачу. Если вы показываете 10 позиций и запросу пользователя отвечают 5 категорий, показать по 2 товара из каждой категории (условно)
Второй шаг — собрать информацию по показам и кликам. На каждый запрос запоминать к какой категории относились товары, которые были показаны пользователю и товары, на которые пользователь кликал. Это будет вашей обучающей выборкой
Затем по обучающей выборке натренировать классификатор. Входные данные — текст запроса, категория и количество кликов. На выходе будет классификатор, который по тексту запроса будет выдавать наиболее вероятные категории для этого запроса. По обработке текста запроса стандартно: токенизация, исправление опечаток, опционально синонимизация и стемминг, затем tf-idf. Затем либо классификатор, работающий с разреженными данными (например, RandomForestClassifier из sklearn 0.16+) или же TruncatedSVD, а затем классификатор (пойдут те же SVG, XGBoost, RanddomForest)
Вы не правы. Потерянное обновление — это если бы команда была «update test set a = a + 1;» в обоих транзакциях, и действительно от неё защищают все уровни изоляции транзакций. Тут вопрос в том, что новое значение для a вычислено во внешней системе, и мой пример выполнится везде, кроме PostgreSQL в режиме serializable, вы можете проверить
CAP не причем, я ответил на комментарий касающийся параграфа статьи, в котором содержится утверждение, что базы данных не линерализованны. И это действительно так, я показал пример
Представьте таблицу «table» с одним полем «a», значение которого «1». И такую последовательность действий:
Транзакция1 — начало
Транзакция1 — select a from table
Транзакция2 — начало
Транзакция2 — select a from table
Транзакция1 — update table set a = 2 (значение посчитано во внешней системе как результат select'а + 1)
Транзакция1 — commit
Транзакция2 — update table set a = 2 (значение посчитано во внешней системе как результат select'а + 1)
Транзакция2 — commit
Есть разные уровни изоляции транзакций, и разные модели консистентности (на видео выше их указано 16). Даже если вы выберете serializable, в том же mysql это serializable* (то есть не совсем serializable) и от проблемы указанного выше примера не защитит. В Oracle есть serializable*, который по сути RR, а совсем не serializable. В MS SQL ситуация аналогична, и их serializable* от проблемы в моем примере не защитит. В postgresql есть честный serializable, но эта честность не бесплатна — вторая транзакция при попытке commit упадет с ошибкой, и рестартовать её уже проблема вашего приложения. Также есть разница между serializability, lineralizability и strict serializability (см. здесь и здесь). Если просто, то serializability гарантирует, что «существует» порядок последовательного выполнения транзакций, выполняемых параллельно. Lineralizability же также гарантирует, то этот порядок соответствует порядку инициации транзакций (раньше стартовала — раньше выполнена).
Не совсем согласен с термином «база данных», скорее теорема все-таки говорит о системах обработки данных в общем. Тот же Zookeeper базой данных можно назвать с большой натяжкой.
Сам автор статьи говорит, что он не знает, что лучше использовать для классификации систем обработки данных. С моей точки зрения CAP теорема тем не менее в этом смысле очень хороша, если её правильно использовать. Не «наша система является AP» или «наша система является CP», а «проблема консистентности в нашей системе решается так ...», «проблема доступности в нашей системе решается так ...» — как общее направление рассуждений о характере распределенной системы. Сам автор теоремы убеждает избегать категоричности в классификации систем
Статья поднимает правильные вопросы, но формулировка идеи чересчур широка. «Забудьте САР теорему как более не актуальную» — сразу же вспоминается институт, где фраза «забудьте всё, чему вас учили в школе» была расхожей, а также первые дни на работе, где часто можно было слышать «забудьте все, чему вас учили раньше».
Это неправильно, и CAP теорема в своё время послужила основанием для обширных исследований и подтолкнула развитие распределенных систем обработки данных. Также введенная ей концепция BASE стала основой для многих реальных систем.
То, что CAP-теорема кем-то неверно трактуется еще не значит, что она более не актуальна. Это равносильно высказыванию «теорема Пифагора более не актуальна» после появления неевклидовой геометрии
Мне кажется всё намного проще. В качестве ключа в redis используем ID пользователя, в качестве значения храним пару — timestamp последнего обращения и приблизительное количество запросов пользователя за последний час. Пересчитываем так:
Спасибо, посмеялся. На самом деле она будет хорошей иллюстрацией к следующей статье, где я хочу показать практическую применимость алгоритма Paxos и способы решения проблемы с количеством пересылаемых сообщений
Задача из примера 5 решается динамикой по профилю, если кому-то еще актуально:
void solve( )
{
int N = 0;
while (true) {
cin >> N;
if (N == -1) return;
ll a[32][8];
for (int i = 0; i < 8; ++i) a[0][i] = 0;
a[0][0b00000111] = 1;
for (int i = 1; i <= N+1; ++i) {
a[i][0b00000001] = a[i-1][0b00000110];
a[i][0b00000011] = a[i-1][0b00000100] + a[i-1][0b00000111];
a[i][0b00000100] = a[i-1][0b00000011];
a[i][0b00000110] = a[i-1][0b00000001] + a[i-1][0b00000111];
a[i][0b00000111] = a[i-1][0b00000011] + a[i-1][0b00000110];
if (i >= 2)
a[i][7] += a[i-2][7];
}
if (N%2==0)
cout << a[N][7] << endl;
else
cout << 0 << endl;
}
}
Аналогично решается задача «замостить доминошками поле N*M», только там все допустимые переходы нужно уже генерировать, а не просчитывать вручную как сделал я. Описание есть здесь
СУБД Greenplum. MPP субд, которая фактически состоит из набора независимых инстансов Postgres, разнесенных по разным физическим машинам, данные между которыми шардятся по хэшу и каждый из них реплицируется на другой хост через WAL для отказоустойчивости, а всей этой системой управляет т.н. Master-сервер (отвечает за построение плана выполнения запроса, координация процесса выполнения, клиентские подключения и иногда за обработку данных)
Спасибо, очень интересные документы.
Но в целом подхода к MVCC в Postgres это не изменило (по крайней мере в рамках описанного в статье). Был сделан новый менеджер блокировок, который для каждой транзакции сохраняет информацию о всех изменивших прочитанные ей записи транзакциях, а при коммите анализирует получившийся граф на наличие циклов, и если таковые есть делает rollback транзакции с сообщением об ошибке. Задумка очень интересная, не сталкивался с ней так как работаю с более ранним форком Postgresql (8.2.15), так что спасибо за ссылки
«Теоретически» относилось к утверждению с поколоночной организацией данных
В описываемом вами случае речь идет не о честном или нечестном MVCC, а о optimistic locking, который напрямую не относится к MVCC: он может работать как с оптимистичными, так и с пессимистичными блокировками
В оригинальной формулировке было: «Скорее всего просто создастся новая версия текущей записи (или даже не полноценная запись, а лишь дельта к текущей)»
и я говорил о варианте с хранением измененной дельты вместо полной измененной записи
В рабочих вариантах хранится не дельта изменения, а новая запись и дельта, необходимая для её отката к предыдущему состоянию. Такой вариант действительно используется и имеет свои недостатки, которые я привел выше
Это радикальный вариант, я его не рассматривал. В целом при таком подходе можно завершать ошибкой все конфликтующие операции доступа к разделяемым ресурсам, и это будет работать при небольшой нагрузке на систему.
И тем не менее, если одна из транзакций будет подвергнута откату как вы предлагаете, все равно моё утверждение подтверждается — две транзакции не смогут обновить одну и ту же запись: одна обновит, вторая упадет
Теоретически, такое обновление возможно при поколоночной организации данных и блокировках на конкретной ячейке: в этом случае две транзакции смогут параллельно обновить два разных поля одной и той же записи
Я посчитал с точностью до наоборот: в классической литературе описаны и уровни изоляции транзакций, и mvcc в том или ином роде. А вот пример как это реализовано в конкретной СУБД как раз очень интересен, потому что большая часть литературы писалась до того, как были разработаны современные СУБД, и в ней не хватает примеров.
Оптимизация с дельтой имеет место, но работает она немного по-другому: новая запись пишется полностью, а старая заменяется на измененную дельту. Недостатки указаны там же: The first issue is long record version chains. Oracle drops rollback segments when they get too large. Firebird never drops a back version if it could be seen by any running transaction. As a result, a long-lived transaction blocks the removal of back versions of all records, causing the database to grow and performance to deteriorate. The performance cost is due both to the decreased density of valid data and to the cost of checking whether any back versions of records can be deleted.
A second issue is the cost of removing back versions. Oracle's back versions are in a separate segment. Firebird's back versions are in the database, so they must be removed one at a time, as they are encountered by subsequent transactions.
A third issue is the cost of a rollback. When a transaction inserts, updates, or deletes a record, Firebird changes the database immediately, relying on the back versions as an undo log. A failed transaction's work remains in the database and must be removed when it is found.
В случае варианта работы с MVCC, принятого в Postgres, мы сталкиваемся только со второй проблемой из этих трех, «removing back versions», которая решается процессом vacuum (и autovacuum)
Update работает именно таким образом: видимая версия закрывается (устанавливается Xmax в ID текущей транзакции, равносильно Delete) и создается новая запись с обновленным значением и Xmin равным ID текущей транзакции (равносильно Insert). Но нужно понимать, что update не равносилен delete и insert, выполненным в разных транзакциях
Этот механизм сложно воспринимать по-другому: если вы будете хранить только измененную дельту, каким образом вы укажите движку, как нужно собирать данные по нескольким записям? Что будете делать при удалении? Как будут работать индексы? Теоретически всё это возможно, но я сомневаюсь что такой механизм реализован хотя бы в одной из используемых СУБД
Измененная дельта записывается только в журнал транзакций для уменьшения размера журнала и возможности последующего восстановления консистентного состояния СУБД по журналу
И да, блокировки всё равно необходимы, смотрите мой комментарий выше. Все эти ухищрения, приведенные здесь, позволяют избавиться практически от всех блокировок, кроме row-level блокировок писателей писателями
Второй шаг — собрать информацию по показам и кликам. На каждый запрос запоминать к какой категории относились товары, которые были показаны пользователю и товары, на которые пользователь кликал. Это будет вашей обучающей выборкой
Затем по обучающей выборке натренировать классификатор. Входные данные — текст запроса, категория и количество кликов. На выходе будет классификатор, который по тексту запроса будет выдавать наиболее вероятные категории для этого запроса. По обработке текста запроса стандартно: токенизация, исправление опечаток, опционально синонимизация и стемминг, затем tf-idf. Затем либо классификатор, работающий с разреженными данными (например, RandomForestClassifier из sklearn 0.16+) или же TruncatedSVD, а затем классификатор (пойдут те же SVG, XGBoost, RanddomForest)
Есть разные уровни изоляции транзакций, и разные модели консистентности (на видео выше их указано 16). Даже если вы выберете serializable, в том же mysql это serializable* (то есть не совсем serializable) и от проблемы указанного выше примера не защитит. В Oracle есть serializable*, который по сути RR, а совсем не serializable. В MS SQL ситуация аналогична, и их serializable* от проблемы в моем примере не защитит. В postgresql есть честный serializable, но эта честность не бесплатна — вторая транзакция при попытке commit упадет с ошибкой, и рестартовать её уже проблема вашего приложения. Также есть разница между serializability, lineralizability и strict serializability (см. здесь и здесь). Если просто, то serializability гарантирует, что «существует» порядок последовательного выполнения транзакций, выполняемых параллельно. Lineralizability же также гарантирует, то этот порядок соответствует порядку инициации транзакций (раньше стартовала — раньше выполнена).
Сам автор статьи говорит, что он не знает, что лучше использовать для классификации систем обработки данных. С моей точки зрения CAP теорема тем не менее в этом смысле очень хороша, если её правильно использовать. Не «наша система является AP» или «наша система является CP», а «проблема консистентности в нашей системе решается так ...», «проблема доступности в нашей системе решается так ...» — как общее направление рассуждений о характере распределенной системы. Сам автор теоремы убеждает избегать категоричности в классификации систем
Это неправильно, и CAP теорема в своё время послужила основанием для обширных исследований и подтолкнула развитие распределенных систем обработки данных. Также введенная ей концепция BASE стала основой для многих реальных систем.
То, что CAP-теорема кем-то неверно трактуется еще не значит, что она более не актуальна. Это равносильно высказыванию «теорема Пифагора более не актуальна» после появления неевклидовой геометрии
Запроса будет всего два — get и set. А в качестве лимита будет скользящее среднее за последний час.
Аналогично решается задача «замостить доминошками поле N*M», только там все допустимые переходы нужно уже генерировать, а не просчитывать вручную как сделал я. Описание есть здесь
Но в целом подхода к MVCC в Postgres это не изменило (по крайней мере в рамках описанного в статье). Был сделан новый менеджер блокировок, который для каждой транзакции сохраняет информацию о всех изменивших прочитанные ей записи транзакциях, а при коммите анализирует получившийся граф на наличие циклов, и если таковые есть делает rollback транзакции с сообщением об ошибке. Задумка очень интересная, не сталкивался с ней так как работаю с более ранним форком Postgresql (8.2.15), так что спасибо за ссылки
В описываемом вами случае речь идет не о честном или нечестном MVCC, а о optimistic locking, который напрямую не относится к MVCC: он может работать как с оптимистичными, так и с пессимистичными блокировками
«Скорее всего просто создастся новая версия текущей записи (или даже не полноценная запись, а лишь дельта к текущей)»
и я говорил о варианте с хранением измененной дельты вместо полной измененной записи
В рабочих вариантах хранится не дельта изменения, а новая запись и дельта, необходимая для её отката к предыдущему состоянию. Такой вариант действительно используется и имеет свои недостатки, которые я привел выше
И тем не менее, если одна из транзакций будет подвергнута откату как вы предлагаете, все равно моё утверждение подтверждается — две транзакции не смогут обновить одну и ту же запись: одна обновит, вторая упадет
Теоретически, такое обновление возможно при поколоночной организации данных и блокировках на конкретной ячейке: в этом случае две транзакции смогут параллельно обновить два разных поля одной и той же записи
The first issue is long record version chains. Oracle drops rollback segments when they get too large. Firebird never drops a back version if it could be seen by any running transaction. As a result, a long-lived transaction blocks the removal of back versions of all records, causing the database to grow and performance to deteriorate. The performance cost is due both to the decreased density of valid data and to the cost of checking whether any back versions of records can be deleted.
A second issue is the cost of removing back versions. Oracle's back versions are in a separate segment. Firebird's back versions are in the database, so they must be removed one at a time, as they are encountered by subsequent transactions.
A third issue is the cost of a rollback. When a transaction inserts, updates, or deletes a record, Firebird changes the database immediately, relying on the back versions as an undo log. A failed transaction's work remains in the database and must be removed when it is found.
В случае варианта работы с MVCC, принятого в Postgres, мы сталкиваемся только со второй проблемой из этих трех, «removing back versions», которая решается процессом vacuum (и autovacuum)
И да, в Firebird также есть блокировки
Этот механизм сложно воспринимать по-другому: если вы будете хранить только измененную дельту, каким образом вы укажите движку, как нужно собирать данные по нескольким записям? Что будете делать при удалении? Как будут работать индексы? Теоретически всё это возможно, но я сомневаюсь что такой механизм реализован хотя бы в одной из используемых СУБД
Измененная дельта записывается только в журнал транзакций для уменьшения размера журнала и возможности последующего восстановления консистентного состояния СУБД по журналу
И да, блокировки всё равно необходимы, смотрите мой комментарий выше. Все эти ухищрения, приведенные здесь, позволяют избавиться практически от всех блокировок, кроме row-level блокировок писателей писателями