state: add allWatcher.respond method

state: add allWatcher.respond method

This is probably the most complex piece - we
maintain reference counts to keep track of
which clients know about which which objects,
so we can delete those objects when everyone
has been notified of their removal.

https://code.launchpad.net/~rogpeppe/juju-core/243-allwatcher-respond/+merge/153519

(do not edit description out of merge proposal)

[rog, 2013-03-15 10:03:19]

Please take a look.

https://codereview.appspot.com/7594048/diff/2001/state/api/apiserver.go.THIS
File state/api/apiserver.go.THIS (left):

https://codereview.appspot.com/7594048/diff/2001/state/api/apiserver.go.THIS#...
state/api/apiserver.go.THIS:1: package api
i don't know why this has crept in. it's not in trunk, so i'm not sure why it's
shown as being deleted.

[dimitern, 2013-03-15 13:04:42]

Overall LGTM with some suggestions.

I have a bad feeling about holding references to all objects and assuming 100k
nodes. Possibly some benchmarking is in order?

https://codereview.appspot.com/7594048/diff/4001/state/megawatcher.go
File state/megawatcher.go (right):

https://codereview.appspot.com/7594048/diff/4001/state/megawatcher.go#newcode205
state/megawatcher.go:205: // the entry nothing else is waiting to be notified
that it's
s/entity/entity;/

https://codereview.appspot.com/7594048/diff/4001/state/megawatcher_internal_t...
File state/megawatcher_internal_test.go (right):

https://codereview.appspot.com/7594048/diff/4001/state/megawatcher_internal_t...
state/megawatcher_internal_test.go:513: //
why are these commented out regions not removed?

https://codereview.appspot.com/7594048/diff/4001/state/megawatcher_internal_t...
state/megawatcher_internal_test.go:599: for n := 0; n <
1<<uint(len(respondTestChanges)); n++ {
it'll be better to have
numBits := 1<<uint(len(respondTestChanges))
before the for loop, and amend the comment above, I think.

[rog, 2013-03-15 13:57:07]

On 2013/03/15 13:04:42, dimitern wrote:
> Overall LGTM with some suggestions.
> 
> I have a bad feeling about holding references to all objects and assuming 100k
> nodes. Possibly some benchmarking is in order?

I agree with your concern. Three things:

1) the plan is to change this code to be able summarise information
rather than simply hold all state entities. That's not too big
a change, and that will mean that we won't necessarily need to hold
all objects.

2) A quick benchmark (adding 100,000 MachineInfo and 100,000 UnitInfo
objects to the allInfo) shows that it uses about 460 bytes per object,
giving a storage cost of about 46MB, which doesn't too unreasonable (and there's
some space to be gained by embedding the linked list pointers rather than using
container/list). It took about 400ms to add all the objects.

3) Although I think we need to keep *some* information around about for each
object so that we can present each client with a coherent sequence of changes
and minimise mongo traffic when we have several StateWatcher clients, we could
potentially move to holding information about the object's existence only, and
maintain a limited size cache of information on recently seen objects. I'm not
sure the resulting complexity would be worth it though.

[rog, 2013-03-15 14:24:59]

Please take a look.

https://codereview.appspot.com/7594048/diff/4001/state/megawatcher.go
File state/megawatcher.go (right):

https://codereview.appspot.com/7594048/diff/4001/state/megawatcher.go#newcode205
state/megawatcher.go:205: // the entry nothing else is waiting to be notified
that it's
On 2013/03/15 13:04:42, dimitern wrote:
> s/entity/entity;/

Done.

https://codereview.appspot.com/7594048/diff/4001/state/megawatcher_internal_t...
File state/megawatcher_internal_test.go (right):

https://codereview.appspot.com/7594048/diff/4001/state/megawatcher_internal_t...
state/megawatcher_internal_test.go:513: //
On 2013/03/15 13:04:42, dimitern wrote:
> why are these commented out regions not removed?

because i forgot to :-)

https://codereview.appspot.com/7594048/diff/4001/state/megawatcher_internal_t...
state/megawatcher_internal_test.go:599: for n := 0; n <
1<<uint(len(respondTestChanges)); n++ {
On 2013/03/15 13:04:42, dimitern wrote:
> it'll be better to have
> numBits := 1<<uint(len(respondTestChanges))
> before the for loop, and amend the comment above, I think.

numBits wouldn't be accurate, because the number of bits is
len(respondTestChanges).

it's really numCombinations, or something like that. i've changed accordingly.

i'm not sure how how you'd want the comment to be modified, though.

[jameinel, 2013-03-17 11:31:09]

On 2013/03/15 13:57:07, rog wrote:
> On 2013/03/15 13:04:42, dimitern wrote:
> > Overall LGTM with some suggestions.
> > 
> > I have a bad feeling about holding references to all objects and assuming
100k
> > nodes. Possibly some benchmarking is in order?
> 
> I agree with your concern. Three things:
> 
> 1) the plan is to change this code to be able summarise information
> rather than simply hold all state entities. That's not too big
> a change, and that will mean that we won't necessarily need to hold
> all objects.
> 
> 2) A quick benchmark (adding 100,000 MachineInfo and 100,000 UnitInfo
> objects to the allInfo) shows that it uses about 460 bytes per object,
> giving a storage cost of about 46MB, which doesn't too unreasonable (and
there's
> some space to be gained by embedding the linked list pointers rather than
using
> container/list). It took about 400ms to add all the objects.


I think a reasonable process is to think about what you think is a reasonable
upper limit, and then add an order of magnitude. When I was benchmarking MaaS
the back-of-the-envelope calculations were about ~100k nodes so 1M nodes as an
upper limit.

So with your numbers, even at 1M nodes you're at 460MB which is perfectly
reasonable. (If you are running 1M machines, virtual or not, you should be able
to afford an extra 1GB of RAM in your control node.)

We'll need to be careful of anything O(N^2) as that will obviously be terrible.
But we also need to watch out for O(N) and O(N log N) algorithms, since even
those will start to get a bit slow if the constants are large. (1s per node
processing * 1M nodes is a about 12 days to complete :).

So I guess that is to say, I'm not worried about 1M nodes held in memory, I
would be concerned if you had to round trip to a DB/API for each of them. Even
getting a sequential scan out of a DB for 1M records is going to be a bit of a
problem.

I'm guessing some of that is going to be part of the HA story (seeing where you
can split things horizontally). Though fundamentally having a process that wants
to see what is happening on every node of 1M nodes is not going to scale well.

So we'll probably need to rethink the all watcher at those sort of scales. (You
probably need to actually store the aggregate data in the DB if you really want
to scale to that many.)

Certainly in MaaS when we found things that needed to be O(N) [computing tags]
we found ways to split the actual work across M workers, so that you can always
scale up M as N gets large.

[jameinel, 2013-03-17 11:36:54]

As long as we are sure allInfo only has one thread/goroutine accessing it: LGTM.

https://codereview.appspot.com/7594048/diff/11001/state/megawatcher.go
File state/megawatcher.go (right):

https://codereview.appspot.com/7594048/diff/11001/state/megawatcher.go#newcod...
state/megawatcher.go:313: }
Odd: http://golang.org/src/pkg/container/list/list.go?s=1535:1580#L68

Checks to see if the element being removed thinks it is part of the list, but
doesn't end up setting e.l to nil after it has been removed.

Do we need to worry about thread safety? Certainly the invariant of being in
a.entities and being a valid entry in a.list should be preserved if possible.

I don't know if allInfo needs to be thread-safe, though.

[rog, 2013-03-18 12:04:10]

On 17 March 2013 11:31,  <john.meinel@canonical.com> wrote:

Firstly, thanks for these helpful thoughts.

> I think a reasonable process is to think about what you think is a
> reasonable upper limit, and then add an order of magnitude. When I was
> benchmarking MaaS the back-of-the-envelope calculations were about ~100k
> nodes so 1M nodes as an upper limit.
>
> So with your numbers, even at 1M nodes you're at 460MB which is
> perfectly reasonable. (If you are running 1M machines, virtual or not,
> you should be able to afford an extra 1GB of RAM in your control node.)
>
> We'll need to be careful of anything O(N^2) as that will obviously be
> terrible. But we also need to watch out for O(N) and O(N log N)
> algorithms, since even those will start to get a bit slow if the
> constants are large. (1s per node processing * 1M nodes is a about 12
> days to complete :).
>
> So I guess that is to say, I'm not worried about 1M nodes held in
> memory, I would be concerned if you had to round trip to a DB/API for
> each of them. Even getting a sequential scan out of a DB for 1M records
> is going to be a bit of a problem.

Yeah, and this is a problem with the current implementation.
Those nodes have to get into memory somehow.

> I'm guessing some of that is going to be part of the HA story (seeing
> where you can split things horizontally). Though fundamentally having a
> process that wants to see what is happening on every node of 1M nodes is
> not going to scale well.
>
> So we'll probably need to rethink the all watcher at those sort of
> scales. (You probably need to actually store the aggregate data in the
> DB if you really want to scale to that many.)

Agreed. For instance I had been thinking that by shipping only a summary
of the data to the remote node, we could get away without storing
any per-node data on the API server. However, thinking a little more
into this, we are going to need to store *some* data per node,
otherwise when a node changes, we won't know which way to adjust
the summaries.

If we're interested in counting things, then we can aggregrate the counts
in stages, rather than forcing all updates to every unit to change the
counts in a single document. There's lots of potential for useful work
here.

> Certainly in MaaS when we found things that needed to be O(N) [computing
> tags] we found ways to split the actual work across M workers, so that
> you can always scale up M as N gets large.

Yes, that's a nice approach.

[rog, 2013-03-18 12:37:54]

*** Submitted:

state: add allWatcher.respond method

This is probably the most complex piece - we
maintain reference counts to keep track of
which clients know about which which objects,
so we can delete those objects when everyone
has been notified of their removal.

R=dimitern, jameinel
CC=
https://codereview.appspot.com/7594048

https://codereview.appspot.com/7594048/diff/11001/state/megawatcher.go
File state/megawatcher.go (right):

https://codereview.appspot.com/7594048/diff/11001/state/megawatcher.go#newcod...
state/megawatcher.go:313: }
On 2013/03/17 11:36:54, jameinel wrote:
> Odd: http://golang.org/src/pkg/container/list/list.go?s=1535:1580#L68
> 
> Checks to see if the element being removed thinks it is part of the list, but
> doesn't end up setting e.l to nil after it has been removed.

you mean e.list, presumably? it does get set to nil - see in the  public Remove
method (line 61)

> Do we need to worry about thread safety? Certainly the invariant of being in
> a.entities and being a valid entry in a.list should be preserved if possible.
> 
> I don't know if allInfo needs to be thread-safe, though.

allInfo does not need to be thread-safe. If it did, it would be very wrong! (in
general, if there's no mutex and no channels, a Go data structure cannot be
thread-safe).