Заден план:
В моя уебсайт потребителите създават социалнимрежа. Това причинява известяванията да летят до свързани възли в мрежата. Например искания за приятели, харесвания, коментари, всички генерират уведомление за съответните възли в мрежата.
За да поддържате всичко прозрачно, потребителите могат да виждат съответните си известия като списък в отделен URL адрес. Този списък се захранва от сортиран набор с подновен резерв ss:<user_id>, Сортираният комплект съдържа hash ids, заедно с времето след епохата (като. \ t score). Например:
hash_id | updated_at
np:1:0:544 | 1482234321.48124
np:1:2:454 | 1482235629.73111
np:1:1:701 | 1482237000.59143
Също така е и всяко уведомление видян или невидим, Това seen състояние се съхранява в съответния хеш, при ключ s, Например на s въведете хеш np:1:0:544 е False; ни казва, че това е невидимо уведомление.
Предизвикателството:
Предизвикателството е да преброим всички невиждани уведомления отвъд предварително определено време на епохата. Това време се съхранява в отделен наричан брояч cut-off.
Това, което вече правя:
1) Вземете всички hash_ids от ss:<user_id> с резултати по - високи от. \ t cut-off, Например ZRANGEBYSCORE ss:<user_id> (cut-off +inf (in redis parlance).
2) Превъртете през всеки hash_id, като го проверите s ключ (т.е. seen ключ). ако s е False, увеличете брояча. Например правя HGET hash_name s за всеки хеш обект. Ако върнатата стойност е False, incr отделен брояч за пренастройка.
Времевата сложност на стъпка 1 е O(log(N)+M), Това от стъпка 2 е O(M), Може да бъде O(N) при макс.
Какво трябва да подобря:
Има ли някакъв начин да направя това в по-малка времева сложност (напр. O(log(N))? Например чрез използване на композитно индексиране и лексикографска подредба?
Изпълнението е критично; това изчисление се случва ~ 2 милиона пъти дневно на моя уебсайт (и мащабиране), така че търся начини за подобряване на скалируемостта.
Забележка: Разбира се, има и други мерки, които мога да предприема, за да се намали натоварването на този алгоритъм (например намаляване на неговата честота, подобряване на инфраструктурата и т.н.), но това е различно съображение.
Отговори:
0 за отговор № 1Промених подхода си.
Най- score (Т.е. updated_at) на сортирания набор сега time.time()+SEEN[status] където SEEN={True:2000000000,False:4000000000}, Това автоматично сортира ключовете от видян и невидим, като същевременно запазва информация за времето (придобито от score-SEEN[status]).
Като цяло този подход ми позволи да се отрежастъпка 2 от изчислението. Времевата сложност е до O (log (N)). Голямото отнемане е, че интелигентната формулировка на индекса наистина може да доведе до представяне. За всеки, който се интересува, тук е прочетена информация за това как сложното индексиране може да постигне различни неща.