Здравствуйте, Ikemefula, Вы писали:

I>Это ж была упрощенная задача. Теперь хочется смасштабировать подход на реальную модель и получить хотя бы оценки сверху-снизу.
Простите, я не знаю, что такое "реальная модель". Вашу задачу я решил, даже не приступив к оптимизациям.
Чем "реальная" модель отличается от "упрощённой"? Можно покрутить параметры типа объёма данных. Но ничего интересного это не даст — картинка перестанет помещаться в экран до того, как RDBMS станет узким местом.

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

Здравствуйте, Ikemefula, Вы писали:

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

I>Вопрос — во сколько оценишь время работы аналогичного запроса, если скажем количество простых линков в пути будет примерно таким же, как ты посчитал в уже решенной задаче ?
Всё это не имеет никакого значения. Вся задача сводится к построению транзитивного замыкания в некотором графе. Типы узлов графа нас не волнуют. Волнует только размер транзитивного замыкания. Каков он будет?
И, на всякий случай — как именно формулируется задача? Ну, кроме как "попытаться доказать, что RDBMS справляются хуже"? В том смысле, что я не очень понимаю, как и что вы хотите отобразить в клиенте. Зачем там за время клика все эти ненужные подробности?

Здравствуйте, Ikemefula, Вы писали:

I>Здравствуйте, Sinclair, Вы писали:

S>>

Как делать к ней запросы?
S>>Очень просто, ANSI SQL поддерживает синтаксис Common Table Expressions, на основе которого легко вычислять транзитивные замыкания на графах.
S>>

S>>  with AllRoutes(sourceLink, targetLink, isPrimaryRoute) as
S>>  ( select sourceLink, targetLink, isPrimaryRoute from Routes where sourceLink = @linkID
S>>    union all
S>>    select r.sourceLink, r.targetLink, ar.isPrimaryRoute 
S>>      from AllRoutes ar inner join Routes r on ar.targetLink = r.sourceLink 
S>>  )
S>>  select targetLink, min(isPrimaryRoute)+2*max(isPrimaryRoute) as ColorId from AllRoutes group by targetLink
S>>

I>Я не понял фокус с цветами. Цвет линка на нижнем уровне определяется цветом самого верхнего пути, основной, резервный или смешаный. Шота не пойму как у тебя это получается.
Очень просто. isPrimaryRoute всегда берётся из самого верхнего пути — обрати внимание на то, что он взят из AllRoutes.
Затем мы выполняем свёртку — ведь один и тот же линк нижних слоёв может встречаться много раз в разных роутах. Вычисляем минимум и максимум, и комбинируем их для получения цвета. Из-за бинарности isPrimaryRoute комбинаций всего три: (min=0, max=0), (min=0, max=1), (min=1, max=1). Я в спешке протупил, и рассчитал для четырёх комбинаций. На самом деле надо их просто сложить, тогда получится 0 для резервного, 1 для смешанного, и 2 для основного.

Здравствуйте, Sinclair, Вы писали:

I>>Вопрос — во сколько оценишь время работы аналогичного запроса, если скажем количество простых линков в пути будет примерно таким же, как ты посчитал в уже решенной задаче ?
S>Всё это не имеет никакого значения. Вся задача сводится к построению транзитивного замыкания в некотором графе. Типы узлов графа нас не волнуют. Волнует только размер транзитивного замыкания. Каков он будет?

В конечном итоге такой же примерно как я и говорил. Не совсем понятно,почему количество таблиц не имеет значения ?

S>И, на всякий случай — как именно формулируется задача? Ну, кроме как "попытаться доказать, что RDBMS справляются хуже"? В том смысле, что я не очень понимаю, как и что вы хотите отобразить в клиенте. Зачем там за время клика все эти ненужные подробности?

Все подробности не нужны, в итоге нужен только набор линков, если визуализация самих путей. Еще задача — нужно смотреть по какому каналу чей трафик идет. Еще можно посмотреть нет ли дыр в роутинге. Или длину логических линков обновить. Примерно так. Задач которые используют такую раскрутку роутинга очень много, все они формулируются по разному.
За время клика нужно только визуализацю делать.

Здравствуйте, gandjustas, Вы писали:

G>Во-первых миллионы лайков это для RDBMS простая задача. Даже сотни миллионов. И совершенно без шардинга.

Лайк бывает разный. Например можно хранить просмотры для каждого пользователя и давать рекомендации вроде — люди похожие на вас часто заходят еще и на страницу P. Лично я бы вынес это хозяйство в отдельную базу, чтобы не нагружать основную. Хотя бы для того, чтобы облегчить процедуру бэкапа основной БД. Теперь возникает вопрос, нужен в этой базе ACID или он будет только мешать?

G>Во-вторых 99,9999% программистов такое не пишут и никогда не будут.

Какое это имеет отношение к предмету беседы? Ну и ты не прав насчет рекомендаций, они довольно часто нужны, просто пока очень мало используются по причине сложности алгоритмов для среднего программиста. В любом случае оценка количества у тебя ошибочна, если учесть, что в мире всего миллионов десять программистов. Не получится ли так что и остальные оценки у тебя такие же?

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

Я нажал лайк, количество изменилось, кеш должен сброситься. Как он тут поможет? Есть огромная таблица, которая постоянно дописывается. По этой таблице регулярно проходятся агрегатные запросы. Я вижу тут возможный ботлнек от ACID, а ты?

Здравствуйте, Ikemefula, Вы писали:

I>В конечном итоге такой же примерно как я и говорил.
Тогда и скорость будет примерно такая же.
I>Не совсем понятно,почему количество таблиц не имеет значения ?
Потому, что значение имеет только объём работы. Во-первых, накладные расходы на сканирование другой таблицы не шибко отличаются от расходов на сканирование той же самой.
Во-вторых, если эти расходы начнут иметь значение, то мы легко перенесём весь граф в одну таблицу, оставив специфичные для типов узлов данные за её пределами.

I>Все подробности не нужны, в итоге нужен только набор линков, если визуализация самих путей.
Тогда задача полностью решена.
I>Еще задача — нужно смотреть по какому каналу чей трафик идет. Еще можно посмотреть нет ли дыр в роутинге. Или длину логических линков обновить. Примерно так. Задач которые используют такую раскрутку роутинга очень много, все они формулируются по разному.
I>За время клика нужно только визуализацю делать.
Тогда вопросов вовсе нет — все перечисленные задачи, очевидно, имеют математическую формулировку в терминах реляций. Пишем запрос — и вперёд, на танки. Раз нет требований к производительности, то они гарантированно решаются.

И можно вернуться к разговору о надёжности и непротиворечивости, которые непонятно, как обеспечивать в Nosql решениях.

В итоге мы имеем классическое неравенство: из корректного медленного решения есть способ сделать быстрое. Из быстрого некорректного решения способа сделать корректное — нету.

Здравствуйте, Ziaw, Вы писали:

Z>Лайк бывает разный. Например можно хранить просмотры для каждого пользователя и давать рекомендации вроде — люди похожие на вас часто заходят еще и на страницу P. Лично я бы вынес это хозяйство в отдельную базу, чтобы не нагружать основную. Хотя бы для того, чтобы облегчить процедуру бэкапа основной БД. Теперь возникает вопрос, нужен в этой базе ACID или он будет только мешать?
При типичных нагрузках на среднестатистическое приложение, ACID совершенно не повлияет на результативность. Т.е. не будет ни помогать, ни мешать.
Z>Я нажал лайк, количество изменилось, кеш должен сброситься. Как он тут поможет?
Вы себе противоречите. Если должен сброситься — то сразу нужен ACID и точный подсчёт количества. А если не нужен точный подсчёт количества, то кэш прекрасно проживёт ещё 60 (300, 15000, etc) секунд.
Z>Есть огромная таблица, которая постоянно дописывается. По этой таблице регулярно проходятся агрегатные запросы. Я вижу тут возможный ботлнек от ACID, а ты?
Я вижу непонимание задачи.

Здравствуйте, Sinclair, Вы писали:

Z>>Лайк бывает разный. Например можно хранить просмотры для каждого пользователя и давать рекомендации вроде — люди похожие на вас часто заходят еще и на страницу P. Лично я бы вынес это хозяйство в отдельную базу, чтобы не нагружать основную. Хотя бы для того, чтобы облегчить процедуру бэкапа основной БД. Теперь возникает вопрос, нужен в этой базе ACID или он будет только мешать?
S>При типичных нагрузках на среднестатистическое приложение, ACID совершенно не повлияет на результативность. Т.е. не будет ни помогать, ни мешать.

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

Z>>Я нажал лайк, количество изменилось, кеш должен сброситься. Как он тут поможет?
S>Вы себе противоречите. Если должен сброситься — то сразу нужен ACID и точный подсчёт количества. А если не нужен точный подсчёт количества, то кэш прекрасно проживёт ещё 60 (300, 15000, etc) секунд.

Точный не нужен, пользователь должен увидеть результат своих действий.

Z>>Есть огромная таблица, которая постоянно дописывается. По этой таблице регулярно проходятся агрегатные запросы. Я вижу тут возможный ботлнек от ACID, а ты?
S>Я вижу непонимание задачи.

Здравствуйте, Ziaw, Вы писали:

Z>>>Я нажал лайк, количество изменилось, кеш должен сброситься. Как он тут поможет?
S>>Вы себе противоречите. Если должен сброситься — то сразу нужен ACID и точный подсчёт количества. А если не нужен точный подсчёт количества, то кэш прекрасно проживёт ещё 60 (300, 15000, etc) секунд.

Z>Точный не нужен, пользователь должен увидеть результат своих действий.
Разные хаки используют.

Например, есть такое понятие как "read-your-own-writes" consistensy специально для таких случаев.
Я про него услышал из Software Engineering Radio Episode 165: NoSQL and MongoDB with Dwight Merriman (в районе 24 минуты).

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

СУВ, Aikin

Здравствуйте, Ziaw, Вы писали:

Z>Здравствуйте, gandjustas, Вы писали:

G>>Во-первых миллионы лайков это для RDBMS простая задача. Даже сотни миллионов. И совершенно без шардинга.

Z>Лайк бывает разный. Например можно хранить просмотры для каждого пользователя и давать рекомендации вроде — люди похожие на вас часто заходят еще и на страницу P. Лично я бы вынес это хозяйство в отдельную базу, чтобы не нагружать основную. Хотя бы для того, чтобы облегчить процедуру бэкапа основной БД. Теперь возникает вопрос, нужен в этой базе ACID или он будет только мешать?

Это же довольно просто проверить. Берем сценарий вроде блогодвижка средней руки или интернет-магазина. Счиатем что у нас 20,000 юзеров и 1,000 лайкаемых элементов (записей\товаров).
Каждый пользователь делает примерно 50 лайков, то есть всего 1М лайков.
Посмотрим как sql справится.

Делаем таблицы:

CREATE TABLE [dbo].[Users]
(
    [Id] INT NOT NULL PRIMARY KEY identity, 
    [Name] NVARCHAR(50) NOT NULL    
)
CREATE TABLE [dbo].[Items]
(
    [Id] INT NOT NULL PRIMARY KEY identity, 
    [Name] NVARCHAR(50) NOT NULL    
)

CREATE TABLE [dbo].[Likes]
(
    [UserId] INT NOT NULL foreign key references Users(id), 
    [ItemId] INT NOT NULL foreign key references Items(id), 
    constraint LikesPK primary key clustered([UserId], [ItemId]) 
)

Фигачим в них данные:

--Populate Items table

declare @i int 

set @i = 0
while (@i<1000)
begin
  insert into Items values(CAST(@i as nvarchar))
  set @i = @i + 1
end
go

--Populate Users table: 20,000
declare @i int 

set @i = 0
while (@i<20000)
begin
  insert into Users values(CAST(@i as nvarchar))
  set @i = @i + 1
end

go

--Populate Likes table: 1,000
declare @i int 
declare @j int 

--Populate likes
set @i = 0
while (@i<20000)
begin
  set @j = 0
  while (@j<50)
  begin
    insert into Likes values(@i+1, CAST(RAND()*1000 as int)+1)
    set @j = @j + 1
  end
  set @i = @i + 1
end

--add likes to 1M count
while ((select count(*) from likes) < 1000000)
begin
    declare @i int 
    set @i = (select count(*) from likes)
    while (@i < 1000000)
    begin
        insert into Likes values(CAST(RAND()*20000 as int)+1, CAST(RAND()*1000 as int)+1)
        set @i = @i + 1
    end
end

Первый цикл генерации лайков повторяющиеся пары дает, поэтому генерит меньше 1М записей. Второй цикл добивает до 1М.

А теперь основной запрос:

dbcc dropcleanbuffers

declare @userId int = 1000
set statistics time on 

select top 10 l.ItemId, sum(s.Similarity) as Rating  
from (
    select l.UserId as LeftUserId, r.UserId as RightUserId, (1/(1+exp(-count(l.ItemId)/10.0))-0.5)*2 as Similarity 
    from dbo.Likes as l
    join dbo.Likes as r on l.itemId = r.ItemId    
    where  l.UserId <> r.UserId
    and l.UserId = @userId        
    group by l.UserId, r.userId
    having (1/(1+exp(-count(l.ItemId)/10.0))-0.5)*2 > 0.3
) s
join Likes l 
on s.RightUserId = l.UserId
where s.LeftUserId = @userId
group by l.ItemId
order by sum(s.Similarity) desc
set statistics time off

Внутренний select получает похожих пользователей, а внешний строит топ 10 самых лайкаемых похожими пользователями айтемов. Все это делается для одного пользователя с id = @userId.

Первый прогон говорит что надо бы добавить индекс:

CREATE NONCLUSTERED INDEX LikesIdx
ON [dbo].[Likes] ([ItemId])
INCLUDE ([UserId])

Полный сброс, второй прогон:

SQL Server Execution Times:
   CPU time = 234 ms,  elapsed time = 2535 ms.

2,5 секунд. Это на localDB (SQL Express), который работает на 1 процессоре и 1 гб оперативки на моем ноуте с медленными дисками.
Если все данные в кеше, то 1 сек.

Обрати внимание на CPU Time — это реальное время вычислений, остальное — IO. На мощном сервере IO будет на порядок быстрее.
Размер базы — 50МБ.


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

Для тех что скажет что это плохо масштабируется:
1) По хорошему расчет похожих пользователей делается в отдельном процессе\сервере и результаты пишутся в базу. Кстати я сделал таблицу похожести пользователей и база была всего 130 мб.
2) Рекомендации можно также хранить и периодически пересчитывать. Тогда запросы вообще сведутся к тривиальным.


Для практики попробуйте обогнать SQL при выполнении этого запроса в рукопашном коде.

G>>Во-вторых 99,9999% программистов такое не пишут и никогда не будут.

Z>Какое это имеет отношение к предмету беседы? Ну и ты не прав насчет рекомендаций, они довольно часто нужны, просто пока очень мало используются по причине сложности алгоритмов для среднего программиста. В любом случае оценка количества у тебя ошибочна, если учесть, что в мире всего миллионов десять программистов. Не получится ли так что и остальные оценки у тебя такие же?
Думаю что я почти угадал. Реальные (не надуманные как в этом посте) проблемы от ACID испытывают порядка 100 программистов в мире, скорее всего они все работают в Bing ил Google.
А что касается алгоритмов рекомендаций, то value от них низкий, а effort большой, поэтому и редко применяют.

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

Z>Я нажал лайк, количество изменилось, кеш должен сброситься. Как он тут поможет? Есть огромная таблица, которая постоянно дописывается. По этой таблице регулярно проходятся агрегатные запросы. Я вижу тут возможный ботлнек от ACID, а ты?
Пересчитывать рекомендации на каждый лайк нет смысла, они почти не изменятся.
А я сделал тест, вроде как проблем нет. А если нужно количество лайков на элемент, то элементарно делается индексированная вьюха.

Здравствуйте, Ziaw, Вы писали:

Z>Типично такие нагрузки вообще не делают, нерационально. Хотя вполне востребовано и если это будет стоить дешево, то будет делаться повсеместно.
Да ладно. А мне казалось, что в каждом первом веб-магазине есть фича "вместе с этим покупают:", которая построена ровно на описанном вами функционале.

Z>Точный не нужен, пользователь должен увидеть результат своих действий.
Я продолжаю вас не понимать. Вот, допустим, я вижу "This page is liked by 15k users", нажимаю Like, что я должен увидеть? Если 15001 — то это точный подсчёт. Если неточный — то я так и увижу 15k, а результатом моих действий будет флаг "Like", в который превратилась кнопка после нажатия. Для этого вообще не нужен подсчёт никаких агрегатов.