Add a general purpose unbounded buffer implementation

[easwars]

This PR moves the unbounded buffer implementation found in
scStateUpdateBuffer to the internal package. It also makes the buffer
work with interface{} type.

This addresses a TODO in the existing code. This will also help with the
eventual BalancerManager implementation which will supersede the
ccBalancerWrapper implementation found in balancer_conn_wrappers.go.

This can also be used by the xdsClient to buffer different responses from
the ADS stream.

[easwars]

Updated the PR by fixing the year in the copyright and also removing examples from comments. PTAL.

[easwars]

Ping ...

[adtac]

Is the buffer ordered? If Put(A) happens before Put(C), is Get guaranteed to return A before C? If so, consider this series of events where goroutines 1 and 2 are executing concurrently.

Goroutine 1:

1.1. Put(A)
1.2. Put(B)
1.3. Get()
1.4. Load()

Goroutine 2:

2.1. Put(C)

Between 1.3 and 1.4, let's say 2.1 happens. Since <- b.Get has completed, the chan is empty, so 2.1 puts C into the chan. Now the channel has C, but the backlog has B, so C would be returned before B the next time Get() is called even though B was inserted before C. (1.4's execution doesn't matter anymore because Load's select executes the empty default and simply returns.)

If this isn't ordered, ignore everything I said :D (but maybe add a note on the Get saying that this may return values out of order, though?)

P.S. I know that this is just code being moved, but thought it'd be interesting to mention.

[easwars]

Get doesn't actually return values. It simply returns the channel and it is the caller's responsibility to read from that channel. So, in your example when 1.3 returns, it does not mean that the underlying channel in the buffer implementation has been drained. It just means that goroutine-1 has a channel from which it can read the same two values that it pushed.

[adtac]

I understand that, but to clarify, I meant x := <-b.Get() when I said "1.3. Get()":

barrier := make(chan bool)

go func() {
  b.Put(1)
  b.Put(2)
  v1 := <-b.Get()
  barrier<-true
  b.Load()
  v2 := <-b.Get()
  b.Load()
}()

go func() {
  <-barrier // used to ensure that b.Put(3) strictly happens after b.Put(2)
  b.Put(3)
  v3 := <-b.Get()
  b.Load()
}()

The question is: is v2 guaranteed to be 2?

I think v2 = 3, v3 = 2 is possible if b.Put(3) happens before the post-barrier b.Load(), which breaks ordering, no? Because 2 was inserted before 3.

[easwars]

You are right with your last statement, but I don't think that breaks ordering. This buffer has the same behavior as a buffered channel. In your example, if you used a vanilla channel with a buffer of 3, you can still run into the same issue that you have mentioned here.

[adtac]

True. I assumed that since Put is non-blocking (unlike a vanilla channel), a user might expect the result to be in the order that Puts returned (like a vanilla channel). That is, in a vanilla channel of capacity 2, if ch <- x completes before ch <- y, then receiving from the channel guarantees that x will be returned before y. This buffer, however, does not guarantee it, correct?

[adtac]

Note that I impose no restriction on which channel send completes first (that's entirely random); just that if x completes first, then x will be returned first when receiving from the channel.

[easwars]

Coming back to your original question:

The question is: is v2 guaranteed to be 2?

If you can guarantee that the assignment to v2 happens before the assignment to v3, then we can guarantee that v2 will be equal to 2.

If you look at it from the point of view of reading from the channel returned from Get, it still maintains order. Now, if you use the returned channel in different goroutines, the order in which you see values will be the order in which the reads execute.

Maybe I'm missing your point.