Fix deadlock bug between Get, SetCapacity and Put

Fix deadlock bug between Get, SetCapacity and Put

[sougou, 2013-05-04 21:10:57]

With this change, Get releases the read lock before waiting on the channel.
This will ensure that SetCapacity will not get blocked if Get waits on a the
channel.
But SetCapacity can allocate a new channel, If so, it broadcasts to all pending
waits by closing the old channel. So, if Get receives a channel closed message,
it retries on the new channel.
This also addresses the other Get->Close->Put deadlock.

https://codereview.appspot.com/9209043/diff/1/go/pools/resource_pool.go
File go/pools/resource_pool.go (right):

https://codereview.appspot.com/9209043/diff/1/go/pools/resource_pool.go#newco...
go/pools/resource_pool.go:117: defer rp.mu.RUnlock()
I could make it more efficient by avoiding the defer, and by explicitly
releasing the read lock at specific locations in the function. But, we would be
vulnerable if a Factory() call panicked.
FYI: RoundRobin is still vulnerable to Factory panics.

https://codereview.appspot.com/9209043/diff/1/go/pools/resource_pool.go#newco...
go/pools/resource_pool.go:131: if startTime.IsZero() {
Just doing this for correctness. We can cut corners and not bother recording
waits if the channel was closed.

https://codereview.appspot.com/9209043/diff/1/go/pools/resource_pool.go#newco...
go/pools/resource_pool.go:134: resources := rp.resources
We need to save the channel in a local variable before releasing the read lock.

[sougou, 2013-05-04 21:14:05]

Please read the previous comments I posted on this CL.

[dvyukov, 2013-05-05 08:04:57]

LGTM

[sougou, 2013-05-05 18:01:51]

There are two other schemes I considered:

1. Two channel approach: Get fetches from an unbuffered channel, Put sends on a
buffered channel. We run a goroutine that pumps everything from the unbuffered
to the buffered channel.  The unbuffered channel never changes. So, Get does not
need to obtain a read lock. The downside: Every Get costs two channel
operations.

2. A more conservative read lock: The read lock obtained by Get is released only
by Put. In this case, if we successfully obtain a write lock, we're guaranteed
that all resources are in the channel, and that there are no waits. As long as
the app behaves and regularly cycles the resources, which is the prevailing
assumption, SetCapacity will get its turn.

Theoretically speaking, if channels were implemented using sync.Cond, RoundRobin
would outperform ResourcePool? If this is the case, sync.Cond may be improved in
the future to match channel performance. So, I'm thinking of keeping RoundRobin
around, and simplify ResourcePool to not implement SetCapacity (or only allow
shrinking).

[dvyukov, 2013-05-06 15:39:12]

On Sun, May 5, 2013 at 10:01 PM,  <sougou@google.com> wrote:
> There are two other schemes I considered:
>
> 1. Two channel approach: Get fetches from an unbuffered channel, Put
> sends on a buffered channel. We run a goroutine that pumps everything
> from the unbuffered to the buffered channel.  The unbuffered channel
> never changes. So, Get does not need to obtain a read lock. The
> downside: Every Get costs two channel operations.
>
> 2. A more conservative read lock: The read lock obtained by Get is
> released only by Put. In this case, if we successfully obtain a write
> lock, we're guaranteed that all resources are in the channel, and that
> there are no waits. As long as the app behaves and regularly cycles the
> resources, which is the prevailing assumption, SetCapacity will get its
> turn.
>
> Theoretically speaking, if channels were implemented using sync.Cond,
> RoundRobin would outperform ResourcePool? If this is the case, sync.Cond
> may be improved in the future to match channel performance. So, I'm
> thinking of keeping RoundRobin around, and simplify ResourcePool to not
> implement SetCapacity (or only allow shrinking).


You should not use sync.Cond on fast paths, when the pool is not
full/empty. Fast-path performance should not depend on sync.Cond
performance.
So it's just sync.Mutex vs runtime mutex. There is not much we can do
to improve sync.Mutex performance, it's pretty much near it's limit.
While channels will become faster.

[sougou, 2013-05-06 16:15:51]

I have a lock-free scheme in mind, but it depends on a behavior that may
violate go's memory model.
I'll ask the question on public nuts since many people will benefit from
the answer.


On Mon, May 6, 2013 at 8:39 AM, Dmitry Vyukov <dvyukov@google.com> wrote:

> On Sun, May 5, 2013 at 10:01 PM,  <sougou@google.com> wrote:
> > There are two other schemes I considered:
> >
> > 1. Two channel approach: Get fetches from an unbuffered channel, Put
> > sends on a buffered channel. We run a goroutine that pumps everything
> > from the unbuffered to the buffered channel.  The unbuffered channel
> > never changes. So, Get does not need to obtain a read lock. The
> > downside: Every Get costs two channel operations.
> >
> > 2. A more conservative read lock: The read lock obtained by Get is
> > released only by Put. In this case, if we successfully obtain a write
> > lock, we're guaranteed that all resources are in the channel, and that
> > there are no waits. As long as the app behaves and regularly cycles the
> > resources, which is the prevailing assumption, SetCapacity will get its
> > turn.
> >
> > Theoretically speaking, if channels were implemented using sync.Cond,
> > RoundRobin would outperform ResourcePool? If this is the case, sync.Cond
> > may be improved in the future to match channel performance. So, I'm
> > thinking of keeping RoundRobin around, and simplify ResourcePool to not
> > implement SetCapacity (or only allow shrinking).
>
>
> You should not use sync.Cond on fast paths, when the pool is not
> full/empty. Fast-path performance should not depend on sync.Cond
> performance.
> So it's just sync.Mutex vs runtime mutex. There is not much we can do
> to improve sync.Mutex performance, it's pretty much near it's limit.
> While channels will become faster.
>

[sougou, 2013-05-07 02:33:38]

After looking at the other CL, I'm leaning back towards this one. It's not that
much more complex, and supports SetCapacity.

https://codereview.appspot.com/9209043/diff/8001/go/pools/resource_pool.go
File go/pools/resource_pool.go (right):

https://codereview.appspot.com/9209043/diff/8001/go/pools/resource_pool.go#ne...
go/pools/resource_pool.go:115: rp.resources = make(chan resourceWrapper,
capacity)
I missed this race condition. It's possible that there are straggler Gets
waiting on the channel even though we set factory to nil. So, it's safer to
close the current channel and create a brand new one.

https://codereview.appspot.com/9209043/diff/8001/go/pools/resource_pool.go#ne...
go/pools/resource_pool.go:129: factory, resources := rp.info()
This code is more readable. We obtain and release read lock within info. If we
need to create a new resource, we re-obtain an independent read lock.
This also reduces the number of read locks to one for the fast-path scenarios.

[dvyukov, 2013-05-07 06:57:14]

What do you think about this one?
http://play.golang.org/p/TvtjgNpfff

Fast path for both Put and Get is a single non-blocking chan send/recv.
It creates resources lazily, trying to reuse existing resources first.
It allows resizing within the limit.
And I think it's relatively simple as compared to other solutions.

[sougou, 2013-05-07 07:12:46]

I actually pursued this idea for a bit, and then abandoned it thinking that
waiting on two channels may not be very efficient...
I was going to ask you, and then forgot.

If this approach is viable, it certainly looks more elegant.




On Mon, May 6, 2013 at 11:57 PM, <dvyukov@google.com> wrote:

> What do you think about this one?
> http://play.golang.org/p/**TvtjgNpfff<http://play.golang.org/p/TvtjgNpfff>
>
> Fast path for both Put and Get is a single non-blocking chan send/recv.
> It creates resources lazily, trying to reuse existing resources first.
> It allows resizing within the limit.
> And I think it's relatively simple as compared to other solutions.
>
>
https://codereview.appspot.**com/9209043/<https://codereview.appspot.com/9209...
>

[dvyukov, 2013-05-07 07:21:00]

On Tue, May 7, 2013 at 12:12 AM, Sugu Sougoumarane <sougou@google.com> wrote:
> I actually pursued this idea for a bit, and then abandoned it thinking that
> waiting on two channels may not be very efficient...
> I was going to ask you, and then forgot.
>
> If this approach is viable, it certainly looks more elegant.


Yes, it's somewhat slower than normal chan operations now. I hope I
will make it faster in foreseeable future.
But the point is that 2-chan select is executed on slow path, when we
are out of resources and need to wait anyway. I thought that it's not
an expected scenario.

[sougou, 2013-05-07 07:42:34]

> Yes, it's somewhat slower than normal chan operations now. I hope I
> will make it faster in foreseeable future.
> But the point is that 2-chan select is executed on slow path, when we
> are out of resources and need to wait anyway. I thought that it's not
> an expected scenario.
>

We have both scenarios right now under different circumstances:
- The transaction pool is usually expected to operate below capacity.
- The general query pool always operates at full capacity with frequent
waits. 7KQPS on old hardware, and 14K on new.
- The memcache pool for rowcache, I hope to operate below capacity. This is
what worried me. But we can make sure we have enough connections so we
rarely have to wait.

The 2-chan select will still be substantially faster than condvars right?

[sougou, 2013-05-07 08:00:36]

I just looked up one of my past benchmarks. RoundRobin was beginning to
show up in the profile graphs. Like in this one:
http://www.corp.google.com/~sougou/3.vtocc.nomc.01.svg (5.5%)

It's one of the reasons why I started looking for alternatives.

[dvyukov, 2013-05-07 10:03:04]

On Tue, May 7, 2013 at 11:42 AM, Sugu Sougoumarane <sougou@google.com> wrote:
>
>> Yes, it's somewhat slower than normal chan operations now. I hope I
>> will make it faster in foreseeable future.
>> But the point is that 2-chan select is executed on slow path, when we
>> are out of resources and need to wait anyway. I thought that it's not
>> an expected scenario.
>
>
> We have both scenarios right now under different circumstances:
> - The transaction pool is usually expected to operate below capacity.
> - The general query pool always operates at full capacity with frequent
> waits. 7KQPS on old hardware, and 14K on new.
> - The memcache pool for rowcache, I hope to operate below capacity. This is
> what worried me. But we can make sure we have enough connections so we
> rarely have to wait.

You can implement a special eager mode. In this mode emptyc is always
empty, so it Get() you just block on resc.

> The 2-chan select will still be substantially faster than condvars right?

It depends.

[sougou, 2013-05-07 16:22:32]

> You can implement a special eager mode. In this mode emptyc is always
> empty, so it Get() you just block on resc.
>

Eager mode will bring back the same deadlock issues of the single channel.
This is the case where Put has to discard a closed resource.


>
> > The 2-chan select will still be substantially faster than condvars right?
>
> It depends.
>

I'm pretty torn here. The two-channel approach is much more elegant and
readable. But it becomes more expensive under heavy load situations where
waits will increase.
Let me stare some more at the two approaches.

[dvyukov, 2013-05-07 16:26:03]

On Tue, May 7, 2013 at 8:22 PM, Sugu Sougoumarane <sougou@google.com> wrote:
>
>> You can implement a special eager mode. In this mode emptyc is always
>> empty, so it Get() you just block on resc.
>
>
> Eager mode will bring back the same deadlock issues of the single channel.
> This is the case where Put has to discard a closed resource.

In eager mode it just need to create a new resource and put in back.

[sougou, 2013-05-07 16:38:22]

> In eager mode it just need to create a new resource and put in back.
>

Resource creation can fail also. I actually tried a scheme where a failed
resource creation would transmit the error into the channel. The code
started looking uglier :).
It becomes a degenerate case of the signal. The recipient of the error has
to transmit the error back into the channel because we don't know who else
could be waiting, etc.

[dvyukov, 2013-05-07 16:51:21]

On Tue, May 7, 2013 at 8:38 PM, Sugu Sougoumarane <sougou@google.com> wrote:
>
>> In eager mode it just need to create a new resource and put in back.
>
> Resource creation can fail also. I actually tried a scheme where a failed
> resource creation would transmit the error into the channel. The code
> started looking uglier :).
> It becomes a degenerate case of the signal. The recipient of the error has
> to transmit the error back into the channel because we don't know who else
> could be waiting, etc.

Ah, yes, that will be necessary.
But a single chan if the best you can get. Probably it will be simpler
to create a separate "eager" pool, to not complicate a single pool
with 2 different modes of operation.

[sougou, 2013-05-08 00:17:52]

This version greatly simplifies the implementation, but at the cost of not
reallocating the channel. I've modified the API a bit:
NewResourcePool accepts a maxCapacity
Open accepts a capacity
capacity is not allowed to exceed maxCapacity

This version can also be made lock-free. I'm debating on the readability. So, I
wanted to get this out before reworking it.

[msolomon, 2013-05-08 01:30:14]

It is somewhat simpler. I also like that Get/TryGet are merged.

[sougou, 2013-05-08 05:37:10]

I couldn't go lock-free because of possible race condition between Close & Get.
Changes in this iteration:
- Get obtains a read lock. Close will wait for all existing Gets to return, and
will not allow any further Gets until factory becomes nil. Newer gets will
bounce off because of factory being nil.
- capacity is changed atomically, and SetCapacity is agnostic of Open or Close
state.

[dvyukov, 2013-05-08 18:08:59]

On Wed, May 8, 2013 at 9:37 AM,  <sougou@google.com> wrote:
> I couldn't go lock-free because of possible race condition between Close
> & Get. Changes in this iteration:
> - Get obtains a read lock. Close will wait for all existing Gets to
> return, and will not allow any further Gets until factory becomes nil.
> Newer gets will bounce off because of factory being nil.
> - capacity is changed atomically, and SetCapacity is agnostic of Open or
> Close state.


Can't you set the capacity to 0 (thus waiting for all outstanding
Put's) and then close the chan (to abort all current and future
Get's)?

Do you need to reopen the pool? If so, can you recreate it from scratch?

[sougou, 2013-05-08 18:34:39]

> Can't you set the capacity to 0 (thus waiting for all outstanding
> Put's) and then close the chan (to abort all current and future
> Get's)?
>
> Do you need to reopen the pool? If so, can you recreate it from scratch?
>

That was what I first went for. The race condition in that case is that
it's possible you could Close and Open after a Get sees a non-empty channel
and before it starts to wait on the channel, in which case it would end up
waiting on the new channel. This would also require a read lock or atomic
read on the channel.

Now that you mention it, maybe it's not a good idea to allow a resource
pool to be reopened (which we currently do). There is no tangible benefit
in reusing a closed resource. Let me look through the code and make sure it
won't cause problems.

[sougou, 2013-05-08 18:38:00]

> That was what I first went for. The race condition in that case is that
> it's possible you could Close and Open after a *Get sees a non-empty
> channel* and before it starts to wait on the channel, in which case it
> would end up waiting on the new channel. This would also require a read
> lock or atomic read on the channel.
>
>
Correction: Get sees a non-nil factory.

[sougou, 2013-05-08 21:31:54]

We finally have a lock-free implementation!
- Got rid of the Open. So, ResourcePool should not be reused once closed. This
will require some changes in how I use it, but it will be well worth the
simplification.
- I'm also deprecating IsClosed as a requirement for the Resource interface. If
a resource is closed, the caller will need to call Put(nil) instead.
- I couldn't figure out how to atomically set and get factory. So, I went for
capacity==0 as the criteria for a pool being closed.

[msolomon, 2013-05-08 21:53:15]

This is going around in circles. I don't understand what benefit we are looking
for. In this case, the correctness and clarity is #1 and performance is
secondary.

https://codereview.appspot.com/9209043/diff/41005/go/pools/resource_pool.go
File go/pools/resource_pool.go (right):

https://codereview.appspot.com/9209043/diff/41005/go/pools/resource_pool.go#n...
go/pools/resource_pool.go:137: panic(CLOSED_ERR)
Is this a programming error? Or can this happen during normal usage?

https://codereview.appspot.com/9209043/diff/41005/go/pools/resource_pool.go#n...
go/pools/resource_pool.go:149: capacity = 0
panic on totally degenerate value?

https://codereview.appspot.com/9209043/diff/41005/go/pools/resource_pool.go#n...
go/pools/resource_pool.go:151: capacity = cap(rp.resources)
Need error on failure to expand.

https://codereview.appspot.com/9209043/diff/41005/go/pools/resource_pool.go#n...
go/pools/resource_pool.go:160: break
This doesn't feel clear at all.  Only one person should be doing set capacity at
once and this cas loop doesn't guarantee that at all.

[sougou, 2013-05-08 22:18:35]

https://codereview.appspot.com/9209043/diff/41005/go/pools/resource_pool.go
File go/pools/resource_pool.go (right):

https://codereview.appspot.com/9209043/diff/41005/go/pools/resource_pool.go#n...
go/pools/resource_pool.go:137: panic(CLOSED_ERR)
On 2013/05/08 21:53:15, msolomon wrote:
> Is this a programming error? Or can this happen during normal usage?
This can happen if the caller misbehaves. Similar to calling Unlock on mutex
that's not locked.

https://codereview.appspot.com/9209043/diff/41005/go/pools/resource_pool.go#n...
go/pools/resource_pool.go:149: capacity = 0
On 2013/05/08 21:53:15, msolomon wrote:
> panic on totally degenerate value?
sounds good.

https://codereview.appspot.com/9209043/diff/41005/go/pools/resource_pool.go#n...
go/pools/resource_pool.go:151: capacity = cap(rp.resources)
On 2013/05/08 21:53:15, msolomon wrote:
> Need error on failure to expand.
ok

https://codereview.appspot.com/9209043/diff/41005/go/pools/resource_pool.go#n...
go/pools/resource_pool.go:160: break
On 2013/05/08 21:53:15, msolomon wrote:
> This doesn't feel clear at all.  Only one person should be doing set capacity
at
> once and this cas loop doesn't guarantee that at all.
I'll look at moving this section into sync2 as a Swap function. It should make
this much more readable.

[msolomon, 2013-05-08 22:37:11]

SGTM

On Wed, May 8, 2013 at 3:18 PM,  <sougou@google.com> wrote:
>
> https://codereview.appspot.com/9209043/diff/41005/go/pools/resource_pool.go
> File go/pools/resource_pool.go (right):
>
>
https://codereview.appspot.com/9209043/diff/41005/go/pools/resource_pool.go#n...
> go/pools/resource_pool.go:137: panic(CLOSED_ERR)
> On 2013/05/08 21:53:15, msolomon wrote:
>>
>> Is this a programming error? Or can this happen during normal usage?
>
> This can happen if the caller misbehaves. Similar to calling Unlock on
> mutex that's not locked.
>
>
>
https://codereview.appspot.com/9209043/diff/41005/go/pools/resource_pool.go#n...
> go/pools/resource_pool.go:149: capacity = 0
> On 2013/05/08 21:53:15, msolomon wrote:
>>
>> panic on totally degenerate value?
>
> sounds good.
>
>
>
https://codereview.appspot.com/9209043/diff/41005/go/pools/resource_pool.go#n...
> go/pools/resource_pool.go:151: capacity = cap(rp.resources)
> On 2013/05/08 21:53:15, msolomon wrote:
>>
>> Need error on failure to expand.
>
> ok
>
>
>
https://codereview.appspot.com/9209043/diff/41005/go/pools/resource_pool.go#n...
> go/pools/resource_pool.go:160: break
> On 2013/05/08 21:53:15, msolomon wrote:
>>
>> This doesn't feel clear at all.  Only one person should be doing set
>
> capacity at
>>
>> once and this cas loop doesn't guarantee that at all.
>
> I'll look at moving this section into sync2 as a Swap function. It
> should make this much more readable.
>
> https://codereview.appspot.com/9209043/

[sougou, 2013-05-08 22:47:10]

PTAL

https://codereview.appspot.com/9209043/diff/43002/go/pools/resource_pool.go
File go/pools/resource_pool.go (right):

https://codereview.appspot.com/9209043/diff/43002/go/pools/resource_pool.go#n...
go/pools/resource_pool.go:167: }
I couldn't move this to sync as a generic Swap because it was convenient to
check for 0 here before swapping. This allows us to return an error if someone
tried to SetCapacity on a closed pool.

[dvyukov, 2013-05-11 12:48:33]

I like this version. I think it's good idea to handle re-opening on the higher
level, rather than trying to solve all cases inside of the pool.

https://codereview.appspot.com/9209043/diff/43002/go/pools/resource_pool.go
File go/pools/resource_pool.go (right):

https://codereview.appspot.com/9209043/diff/43002/go/pools/resource_pool.go#n...
go/pools/resource_pool.go:52: func NewResourcePool(factory Factory, capacity
int, idleTimeout time.Duration) *ResourcePool {
I don't know how you use it, but I would pass maxCap and curCap separately.
Because currently it requires either to call NewResourcePool() with max capacity
and then instantly shrink the capacity (which is ugly) or only every shrink the
capacity in future (which is not necessary what users want).

https://codereview.appspot.com/9209043/diff/43002/go/pools/resource_pool.go#n...
go/pools/resource_pool.go:92: if rp.IsClosed() {
This is unnecessary, complicates things (2 different ways to detect closed
pool), and slows things down a bit. I would suggest removing it.

[sougou, 2013-05-11 18:16:58]

I'll send out a new CL.

https://codereview.appspot.com/9209043/diff/43002/go/pools/resource_pool.go
File go/pools/resource_pool.go (right):

https://codereview.appspot.com/9209043/diff/43002/go/pools/resource_pool.go#n...
go/pools/resource_pool.go:52: func NewResourcePool(factory Factory, capacity
int, idleTimeout time.Duration) *ResourcePool {
On 2013/05/11 12:48:33, dvyukov wrote:
> I don't know how you use it, but I would pass maxCap and curCap separately.
> Because currently it requires either to call NewResourcePool() with max
capacity
> and then instantly shrink the capacity (which is ugly) or only every shrink
the
> capacity in future (which is not necessary what users want).
We've never had to change capacity on-the-fly, mainly because of our
zero-downtime restarts. But I agree that it's awkward. Might as well do it
right.

https://codereview.appspot.com/9209043/diff/43002/go/pools/resource_pool.go#n...
go/pools/resource_pool.go:92: if rp.IsClosed() {
On 2013/05/11 12:48:33, dvyukov wrote:
> This is unnecessary, complicates things (2 different ways to detect closed
> pool), and slows things down a bit. I would suggest removing it.
This handles the case where Close is called, and it's waiting for Puts to return
resources. Then any new Gets will immediately fail. It's a very rare corner
case, but it's not really an error. Just better behavior.
I'm ok with dropping this, since it will go faster.

[dvyukov, 2013-05-12 11:14:26]

On 2013/05/11 18:16:58, sougou wrote:
> I'll send out a new CL.
> 
> https://codereview.appspot.com/9209043/diff/43002/go/pools/resource_pool.go
> File go/pools/resource_pool.go (right):
> 
>
https://codereview.appspot.com/9209043/diff/43002/go/pools/resource_pool.go#n...
> go/pools/resource_pool.go:52: func NewResourcePool(factory Factory, capacity
> int, idleTimeout time.Duration) *ResourcePool {
> On 2013/05/11 12:48:33, dvyukov wrote:
> > I don't know how you use it, but I would pass maxCap and curCap separately.
> > Because currently it requires either to call NewResourcePool() with max
> capacity
> > and then instantly shrink the capacity (which is ugly) or only every shrink
> the
> > capacity in future (which is not necessary what users want).
> We've never had to change capacity on-the-fly, mainly because of our
> zero-downtime restarts. But I agree that it's awkward. Might as well do it
> right.


Then why do you need SetCapacity()?



>
https://codereview.appspot.com/9209043/diff/43002/go/pools/resource_pool.go#n...
> go/pools/resource_pool.go:92: if rp.IsClosed() {
> On 2013/05/11 12:48:33, dvyukov wrote:
> > This is unnecessary, complicates things (2 different ways to detect closed
> > pool), and slows things down a bit. I would suggest removing it.
> This handles the case where Close is called, and it's waiting for Puts to
return
> resources. Then any new Gets will immediately fail. It's a very rare corner
> case, but it's not really an error. Just better behavior.
> I'm ok with dropping this, since it will go faster.

[sougou, 2013-05-12 17:58:50]

> Then why do you need SetCapacity()?
>
>
Because the functionality is already there. So, it's better to keep
supporting it. It's also possible we may need it in the future for a
different situation.
From an implementation perspective, getting rid of SetCapacity() won't make
the code any simpler because of Close() needs that same functionality, or
something of similar complexity.