4 ms·

Do you store the entire set of 1.7 million entries in redis? Or is redis an index to data stored elsewhere, in a relational DB perhaps? I was under the impress

Do you store the entire set of 1.7 million entries in redis? Or is redis an index to data stored elsewhere, in a relational DB perhaps? I was under the impression that redis wouldn't be all that useful to store a lot of data. Would be great if something as quick as redis could work with large data sets.

vinnyglennon 14y ago
Storing a list of 1.7 million strings for us takes 70mb stored in memory. Testing for membership is an O(1) op. Very happy with it. We use mongo as a dumb data store as well as a bunch of other infrastructure tools, like http://circleci.com http://circleci.com we could have only dreamt of years ago.
- StavrosK 14y ago
  Why not use a bloom filter?
  - genwin 14y ago
    Maybe because of this fact (according to Wikipedia)?: "The more elements that are added to the set, the larger the probability of false positives."
    - StavrosK 14y ago
      That depends on its size, though. You can make it larger and get fewer false positives.
  - vidarh 14y ago
    The main benefit of Bloom filters is that they can be made small. Given that his database takes only 70MB or so and he's not trying to ship this to devices that might have much in terms of space limitations, there would appear to be little point.
    - StavrosK 14y ago
      Eh, true, I guess redis is sufficiently awesome.
- genwin 14y ago
  > Testing for membership is an O(1) op Curious how. O(1) an array index lookup, not a string lookup, I thought.
  - milkshakes 14y ago
    http://redis.io/commands/sismember http://redis.io/commands/sismember
    - genwin 14y ago
      Again just curious, but I'd still like to know how. Someone there asks the mod how it could be O(1), the mod replies it's a "hash table lookup". But Wikipedia at http://en.wikipedia.org/wiki/Big_O_notation http://en.wikipedia.org/wiki/Big_O_notation suggests that such lookup is no faster than O(log log n). I think the redis info is incorrect. O(1) implies that the location of the member in the list is already known, with no search required. I don't see how that could be the case when it's a key lookup. The key could be anywhere in the list, even if the list is sorted. They key would have to be searched for, it seems.
      - milkshakes 14y ago
        O(1) means constant time. Redis sets are interesting, because there are a few possible implementations under the hood, but the typical case winds up implementing it as a hash table. Hash tables have constant time lookup. Think of it this way (this isn't literally what happens, but it's close). 1) Take the url you're looking for. Run it through a hash function. This takes an (amortized) constant amount of time. 2) Now you have an index to check. (the return value from the hash function). So index into your actual table, and check to see what's stored there. If there's a value stored there, then the url is a member of the set. This also takes a constant amount of time. Does this help?
        genwin 14y ago
        > So index into your actual table, and check to see what's stored there But that check isn't a constant time lookup. The lookup time can vary. (Analogously, a lookup in a phone book can vary in time; we can't necessarily go to the exact spot the first time.) So the total time for both steps must vary as well. I think.

vinnyglennon 14y ago

Storing a list of 1.7 million strings for us takes 70mb stored in memory. Testing for membership is an O(1) op. Very happy with it. We use mongo as a dumb data store as well as a bunch of other infrastructure tools, like http://circleci.com http://circleci.com we could have only dreamt of years ago.

StavrosK 14y ago
Why not use a bloom filter?
- genwin 14y ago
  Maybe because of this fact (according to Wikipedia)?: "The more elements that are added to the set, the larger the probability of false positives."
  - StavrosK 14y ago
    That depends on its size, though. You can make it larger and get fewer false positives.
- vidarh 14y ago
  The main benefit of Bloom filters is that they can be made small. Given that his database takes only 70MB or so and he's not trying to ship this to devices that might have much in terms of space limitations, there would appear to be little point.
  - StavrosK 14y ago
    Eh, true, I guess redis is sufficiently awesome.
genwin 14y ago
> Testing for membership is an O(1) op Curious how. O(1) an array index lookup, not a string lookup, I thought.
- milkshakes 14y ago
  http://redis.io/commands/sismember http://redis.io/commands/sismember
  - genwin 14y ago
    Again just curious, but I'd still like to know how. Someone there asks the mod how it could be O(1), the mod replies it's a "hash table lookup". But Wikipedia at http://en.wikipedia.org/wiki/Big_O_notation http://en.wikipedia.org/wiki/Big_O_notation suggests that such lookup is no faster than O(log log n). I think the redis info is incorrect. O(1) implies that the location of the member in the list is already known, with no search required. I don't see how that could be the case when it's a key lookup. The key could be anywhere in the list, even if the list is sorted. They key would have to be searched for, it seems.
    - milkshakes 14y ago
      O(1) means constant time. Redis sets are interesting, because there are a few possible implementations under the hood, but the typical case winds up implementing it as a hash table. Hash tables have constant time lookup. Think of it this way (this isn't literally what happens, but it's close). 1) Take the url you're looking for. Run it through a hash function. This takes an (amortized) constant amount of time. 2) Now you have an index to check. (the return value from the hash function). So index into your actual table, and check to see what's stored there. If there's a value stored there, then the url is a member of the set. This also takes a constant amount of time. Does this help?
      - genwin 14y ago
        > So index into your actual table, and check to see what's stored there But that check isn't a constant time lookup. The lookup time can vary. (Analogously, a lookup in a phone book can vary in time; we can't necessarily go to the exact spot the first time.) So the total time for both steps must vary as well. I think.