CODEWITHSUNDEEP
data-structuresnosqlredis
Derek Organ
Derek Organ

Reputation: 8473

Optimal storage structure in Redis

I'm looking to store the follow group of information. I store a minute timestamp(e.g. group all browserIDs seen in a 1 minute window) and then a list of browser references. I'd like to be able have only one instance of a browser id

What data structure in Redis can I use for this data structure? Is there a more optimal way to store it?

...
12:06 -> browser1, browser7
12:07 -> browser8
12:08 -> browser4, browser5, browser6, browser9
...

Each row can have a time to live of about 1 day.

When adding a new browserID I'm first checking to see if the browser id already exists somewhere in the data if so delete and add to new minute row.

Lastly every 1 minute I take the row from 30 minutes ago and process those browserIDs and then remove that row from the list when fully processed.

There could be up to 1 million browser referenes in this data structure at any one time.

Upvotes: 0

Views: 162

Answers (2)

Jonatan Hedborg
Jonatan Hedborg

Reputation: 4432

Ok, new information, new answer :)

Let's make each browser a key in the database, pointing to which timestamp it's currently in. And also a key for each timestamp, with a set of which browsers it "contains".

When a new browser is added;

  1. Check if it's already in the system by checking if its key exists.
  2. If it is, check which timestamp it belongs to, remove it from the old time stamp, add it to the new one. Update the browser key.
  3. If not, add it to the time stamp and set the browser key.

To expire the keys I would probably not use the built in expire, instead use a cron job or something to

  1. Remove all browser keys in the timestamp
  2. Remove the timestamp key.

Example data structure;

ts:12:01 -> {1, 3}
ts:12:02 -> {2}

browser:1 -> 12:01
browser:2 -> 12:02
browser:3 -> 12:01

This should be reasonably O(1), but with a slightly higher constant time (multiple requests for each operation). Could be reduced by using server side ruby scripting possibly.

Hope that helps!

Upvotes: 1

kaitian521
kaitian521

Reputation: 578

List is enough. In fact, if the number of browser is less than 400(according to your conf file, but default 400), Redis implements a sequential array to substitude list for space-efficient.

For more infomation : https://github.com/antirez/redis/blob/unstable/src/ziplist.h

Upvotes: 0

Related Questions