[Bro] effects of &synchronized and &mergeable

Robin Sommer robin at icir.org
Tue Jan 15 09:39:28 PST 2013



On Mon, Jan 14, 2013 at 17:09 -0500, you wrote:

> global icmp_too_many_destination_unreachable_table: table[addr] of count = {}
>         &default=0
>         &create_expire=icmp_too_many_destination_unreachable_window
>         &synchronized
>         &mergeable;

Short version: using &synchronized (wo/ &mergeable, not needed here)
should work but there's a better solution coming up.


Longer version follows.

First, regarding your questions:

> Is increment a single atomic operation or is it implemented as multiple
> atomic operations (fetch, locally add one, store, return)?

Neither. :) What happens is (fetch, locally add one, send "add one"
over the other nodes, store, return). The other nodes receive "add
one" and replay that operation locally. In other words, each node
applies the same operation locally and will eventually reach the same
value (because all will see, e.g., two increments when two nodes do
that simultaneously), but they don't have a consistent view at all
times (because there's a delay in propagating the updates, and no
locking in place that would guarantee global consistency.).

There are a number design decisions/trade-offs behind this scheme; if
you're curious, the details are here: http://www.icir.org/robin/papers/acsac05.pdf

> If increment is atomic, is it still atomic when incrementing a default
> value? I.e., if a host isn't in the table when two nodes simultaneously
> increment its count, is the count always properly set to two?

Yes, likewise because what's actually send is two increments, and both
nodes with still start with the default.

>  If a host is in the table and one node deletes it while another node
>  increments it, is the resulting value always either 0 or 1, or can
>  the value be old_value + 1?

Now it's getting tricky and I'm not quite sure off the top of my head,
but I believe this leads to a race condition and depends on order of
the operations (per the paper linked to above, we deliberately accept
race conditions and do a "best effort synchronization").

>  Does it matter if the delete is because of &create_expire or because
>  of an explicit delete?

Does not matter iirc ... 

> Is &mergeable necessary in this case? I couldn't figure out from the
> documentation if &mergeable applies to the outer table or to its values
> if those values are container types.

It's the latter. I'm impressed that you even got so far in figuring
that out. :)

Second, two more notes:

    - in some sense &synchronized is a legacy mechanism. It works and
      and is supported, but we're moving away from using it. One
      replacement is the new upcoming "metrics framework", which is a
      general mechanism to measure/count "stuff". It will have cluster
      transparency built in that "just works" and should support your
      counting application nicely. Internally that framework sends
      evetns around rather than using &synchronized. It's scheduled to
      be part of Bro 2.2.

    - we have been kicking around the idea of removing &synchronized
      completely. it has a number of drawbacks (the loose semantics
      and race condition; a lack of control for which nodes gets
      updates) and internally it's very complex to implement. The idea
      is to replace it with something simpler but more well-defined
      (like a distributed key-value store) that would be wrapped with
      script-layer frameworks to provide for easy use.

      But that's probably more than you wanted to know. :)

Robin


-- 
Robin Sommer * Phone +1 (510) 722-6541 * robin at icir.org
ICSI/LBNL    * Fax   +1 (510) 666-2956 *   www.icir.org



More information about the Bro mailing list