100 more of those BITFIELDs | Hacker News Reader

100 more of those BITFIELDs

antirez.com

77 pointsfcambus24 comments

With the #N syntax, Redis is getting dangerously close to having C-struct-typed fields (i.e. product types with a known bit-level encoding.)

I could imagine a STRUCT LOAD command (like SCRIPT LOAD) to push a struct definition to the server; and then STRUCT GETFIELD and STRUCT SETFIELD commands to manipulate the structs. The GETFIELD and SETFIELD commands would just boil down to the same BITFIELD command after dereferencing. (Heck, Redis could probably cheaply tag the fields with their struct definition, and then you could GET/SETBYFIELD would be polymorphic.)

...thinking about this more, this is possible now, isn't it? The struct-definition loader command, and the dereferencing commands, can all just be Lua functions passed to EVAL. The struct definitions could be loaded into a sorted set; the dereferencing commands would read from that set and then translate your query into a call to this BITFIELD command to do the work.

Anyone care to implement this silliness? :)

Not that silly and perfectly doable with the current support for Lua scripts...

Check out Concise [0] or Roaring Bitmaps [1] before rolling your own compressed bitset scheme. Wish I had known about these sooner.

(I realize now this is offtopic, as this is bit fields not bit sets; nevermind, but still it's interesting!)

[0] http://arxiv.org/pdf/1004.0403.pdf

[1] http://roaringbitmap.org/

+1 for Roaring Bitmaps. We are starting to use it in multiple products.

I'm quite excited for bitfields in Redis. We are going to need to implement some bloom filter-based data structures for one of our products in the near future. Previously the best way to do this was to either keep a hash map or a binary k/v, both of which have substantial drawbacks (such as the need for locking). These bitfields, however, are a perfectly-timed ideal solution to the problem.

You can implement bloom filters in redis >2.6 with SETBIT And GETBIT. But I'm guessing this is not your case exactly? I'm curious what exactly you're trying to model.

We want to count the number of users, including guests, who are currently viewing a resource. To count guests, we plan to count unique IPs, so each IP should be counted at most once even if it connects to several different servers as a result of load balancing.

The approach we're moving towards is an augmented bloom filter where each "bit" is actually an unsigned integer counting the number of items hashed to the position, allowing us to add and remove IPs to the filter as users come and go (just rehashing and "subtracting" the IP when it leaves). This lets us ensure that IPs are not counted more than once. SETBIT and GETBIT would work with a normal filter, but they can't increment multiple bits, so we'd end up needing to lock.

I wonder if you could use Redis hyperloglogs for this... You count IP ins in an HLL, COUNT IP out, and subtract.

sounds to me like it's more suitable for HLL than for blooms actually.

Ah yes, a counting filter. [0] How do you plan on tackling rare overflow?

Have you looked at Cuckoo Filter [1]? Same abilities as a counting bloom filter, but has some advantages like reducing false positives while using even less memory and requiring less processing.

[0]: https://en.wikipedia.org/wiki/Bloom_filter#Extensions_and_ap... [1]: https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

i love using 64 bit unsigned ints in mysql for 64 boolean columns. I do:

alter table foo add column bar bigint(20) unsigned default 18446744073709551615

and that gets you 64 111111111111111111111111111111 etc.

so much better than individual boolean columns cluttering up your user table.

Poe's law in action.

I can't tell if you are serious, but if you are, there are generally database constructs to help with this (if the database doesn't just outright support condensing bit fields or a specific type for sets) in a way that doesn't make it impossible to read easily from the database. You're basically making your data unusable without the separate code you've written to parse that field, which can be really annoying in many, many instances (such as debugging!).

Edit: It's worth noting that one way to use a complex structure in the database without making it too dependent on external code would be to create some stored procedures for setting, updating and viewing the structure. In this case, that would be some functions that took the field value, and extracted the individual bits into a result, or allowed updating a specific flag. That would keep how the data is represented within the purview of the database, but you're stuck with a bunch of SQL functions that approximate what your code is doing in the application, which is a pain. Thankfully, a lot of database systems acknowledged this a long time ago and provided constructs to make it easier.

That sounds pretty painful to query, though. If the first bit position represented if the user had confirmed their email address, wouldn't a SELECT for confirmed users look something like SELECT * FROM users WHERE (mydata & b'0000000000000000000000000000000000000000000000000000000000000001')?

in rails I add:

  [:foo_boolean1, :foo_boolean2].each_with_index do |flavor, i|
    power = 1 
    i.times do
      power *= 2
    end 
    define_method "has_#{flavor}" do
      (foo_options & power) > 0 
    end 
    define_method "has_#{flavor}=" do |value|
      value = value == '1' if value.class == String
      current_value = self.send("has_#{flavor}")
      if (current_value && !value) || (!current_value && value)
        self.foo_options = foo_options ^ power 
      end 
    end 
  end

which lets me access each col like normal. blah.has_foo_boolean1 or blah.has_foo_boolean1=true etc.

You might want to take a look at https://github.com/pboling/flag_shih_tzu, which does all of that and a lot more, like adding database scopes.

aw, but it was so much fun writing that logic myself and really learning how bit ops work in ruby.

reminds me of this http://jeremykun.com/2013/02/08/why-there-is-no-hitchhikers-... article about doing Math cuz u love it.

No, you can just compare against an integer: SELECT * FROM users WHERE mysql & 1

This sounds like it'd be a full table scan to me.

53 bits.. they're returning a bitfield as a double float at some layer?

Or am I misreading the implication and they can do signed 64 bits but not unsigned?

Would like to see speed vs storage benchmarks. Bit twiddling must be a bit slow, no?

The only slow operations these days are L3 cache misses and transcendental function calls, around 100 cycles each. Optimize for that, not a 1 CPU clock cycle "bit twiddle."

Computers are generally very good at bit-twiddling - why do you expect this to be slow?

Reply on news.ycombinator.com