Once upon a time I needed to make an efficient solution that would allow me to store and add a massive amount of statistics on the ad view counter with the ability to view statistics by day.
Input parameters and restrictions:
- Redis Cluster
- 10+ million entities with views to be counted
- Time complexity on increment -
O(1), on select -O(n)
Functions to be implemented:
- Increase the view count
- Get views for the last month
- Get views for all time
I figured out right away that it could be done very effectively with simple hash stored keys, the major sticking point was how to effectively implement the cluster. Redis' ability to distribute keys across clusters via hash slots came in handy, allowing me to spread the load across the cluster evenly.
A bit of theory
Redis utilises hash slots to distribute keys across multiple nodes in a Redis Cluster. This distribution mechanism enables scalability and high availability. The allocation of hash slots is based on the key name of each Redis key.
When a Redis key is created, a hash function is applied to its key name to determine the hash slot. Redis employs a 2^14-slot hash space, where each slot is identified by a number from 0 to 16383. By using a hash function and the modulo operation, Redis maps the hash value of the key name to a specific hash slot.
Using the CRC16 algorithm as the default hash function. This algorithm ensures a well-distributed allocation of keys across the hash space. However, keys that contain curly braces {} introduce a concept called hash tags. Hash tags allow Redis to group keys with the same hash tag into the same hash slot, irrespective of the rest of the key name. For instance, if a key has the format {advert:314}:views, Redis only considers the hash tag advert:314 when calculating the hash slot. Consequently, keys like {advert:314}:bids or new:{advert:314}:bids will also be assigned to the same hash slot.
Hash slots play a crucial role in Redis Cluster's ability to distribute keys evenly among nodes, facilitating efficient data sharding and horizontal scaling. By considering the key name and incorporating hash tags, Redis ensures that related keys are stored on the same Redis node, optimising data access for logical groups of keys.
Implementation
The structure I used in this solution:
Key name: {advert:%d}:views
Data structure: hash map[string]int, where string is date in YYYYMMDD format and int is the counter.
Let's have a look at each item of functionality in practice.
Increase the view count
I used HINCRBY command to increment the counter for a particular date.
Example command:
redis> HINCRBY {advert:314}:views 20230606 1
---------- Response ----------
(integer) 1
Get views for the last month
To get last month's data I'm using HMGET command with a list of dates I want to get statistics for.
Example command:
redis> HMGET {advert:314}:views 20230606 20230605 20230604 20230603 20230602 20230601
---------- Response ----------
1) 1
2) 2
3) (nil)
4) 1
5) 6
Note that the list of values associated with the given fields in the same order as they are requested.
Get views for all time
The issue is much more difficult than the previous ones.
I could run 2 queries to get a list of fields from the key and iterate through them but I didn't like it. So I decided to use internal LUA script via EVAL command, it would be more efficient with Redis' client because it works with 1 query only.
Example command:
redis> EVAL "local totalView = 0
local dayViews = redis.call('hvals', KEYS[1])
for _, dayView in ipairs(dayViews) do
totalView = totalView + tonumber(dayView)
end
return totalView" 1 {advert:314}:views
---------- Response ----------
(integer) 10
As a bonus I'll attach a ready-made PHP class with this implementation which was written using Illuminate Redis client from Laravel:
<?php declare(strict_types=1);
namespace App\Repositories;
use App\Contracts\Entity;
use Illuminate\Redis\RedisManager;
class ViewStatsRepository
{
private const
DATE_FORMAT = 'Ymd',
VIEW_STATS_DAYS = 30
;
public function __construct(
private readonly RedisManager $redis
) { }
public function getTotalViewsCount(Entity $entity): int
{
$evalScript = <<<LUA
local totalView = 0
local dayViews = redis.call('hvals', KEYS[1])
for _, dayView in ipairs(dayViews) do
totalView = totalView + tonumber(dayView)
end
return totalView
LUA;
return (int) $this->redis->eval($evalScript, 1, $this->viewCountKey($entity));
}
public function getTodayViewsCount(Entity $entity, DateTimeInterface $now): int
{
return $this->getViewsCountByDate($entity, $now);
}
public function getViewsCountByDate(Entity $entity, DateTimeInterface $now): int
{
return (int) $this->redis->hget($this->viewCountKey($entity), $now->format(self::DATE_FORMAT));
}
public function getViewStats(Entity $entity, DateTimeInterface $now): array
{
$keys = [];
for ($i = self::VIEW_STATS_DAYS - 1; $i >= 0; $i--) {
$keys[] = $now->modify("-{$i} days")->format(self::DATE_FORMAT);
}
$stats = array_combine($keys, array_values($this->redis->hMGet($this->viewCountKey($entity), $keys)));
return array_map('intval', $stats);
}
public function incrementViewsCount(Entity $entity, DateTimeInterface $now, int $incrementBy = 1): int
{
return (int) $this->redis->hIncrBy(
$this->viewCountKey($entity),
$now->format(self::DATE_FORMAT),
$incrementBy
);
}
private function viewCountKey(Entity $entity): string
{
return sprintf('{advert:%d}:views', $entity->getId());
}
}
Useful links to enhance your knowledge:
Top comments (0)