#Order of execution

92 messages · Page 1 of 1 (latest)

gusty pecan
#

Code:

var subscriptions map[MessageType][]chan<- any
var mutSub sync.Mutex

func Subscribe(messageType MessageType, hitFunc func([]any) (any, bool)) (chan<- any, error) {
    subCh := subscribe(messageType)

    message, exists, err := FindMessage(messageType, hitFunc)
    if err != nil {
        errlog.Println(err)
        return nil, errors.New("unsuccessful subscribe")
    }

    if exists {
        subCh <- message
    }

    return subCh, nil
}

func subscribe(messageType MessageType) chan<- any {
    subCh := make(chan<- any, 1)

    defer mutSub.Unlock()
    mutSub.Lock()

    subscriptions[messageType] = append(subscriptions[messageType], subCh)

    return subCh
}

func StoreAndNotify(messageType MessageType, message any) error {
    err := StoreMessage(messageType, message)
    if err != nil {
        errlog.Println(err)
        return err
    }

    defer mutSub.Unlock()
    mutSub.Lock()
    for _, ch := range subscriptions[messageType] {
        ch <- message
    }

    return nil
}

var messages map[MessageType][]any
var mutMess sync.Mutex

func messageTypeExists(messageType MessageType) bool {
    if messageType != SCLServerStarted {
        return false
    }

    return true
}

func StoreMessage(messageType MessageType, message any) error {
    if !messageTypeExists(messageType) {
        return errors.New("unknown message type")
    }

    defer mutMess.Unlock()
    mutMess.Lock()

    messages[messageType] = append(messages[messageType], message)

    return nil
}

func FindMessage(messageType MessageType, hitFunc func([]any) (any, bool)) (any, bool, error) {
    if !messageTypeExists(messageType) {
        return nil, false, errors.New("unknown message type")
    }

    defer mutMess.Unlock()
    mutMess.Lock()

    if len(messages[messageType]) == 0 {
        return nil, false, nil
    }

    message, exist := hitFunc(messages[messageType])

    return message, exist, nil
}
#

Goroutines subscribe on some type of messages by invoking Subscribe. This function returns sub channel and additionally write message to channel if the message already came. Otherwise, if it doesn't write, the sub goroutine will stay stuck forever (waiting on sub channel). Creating channel is done by invoking non-exported function subscribe and checking for message is done by invoking FindMessage, in that order.

On the other side of system, there is a goroutine that receives messages from the p2p network. Upon receiving the message, it invokes StoreAndNotify function. This function first store the message by invoking Store function and then notify all subscribers.

So, we can divide these code in 4 independent parts (2 elements per goroutine):

  • first goroutine:
  1. write channel to subscriptions (subscribe)
  2. check for message
  • second goroutine:
  1. store the message
  2. notify the subscribers

Since 1) and 4) are under same mutex, and, 2) and 3) are under same mutex, there isn't any data race.

All possible permutations of executing this code are as follows (since everything is in locks):

1 2 3 4
1 3 2 4
1 3 4 2
3 1 2 4
3 1 4 2
3 4 1 2

If I can rely on the execution order to always be 1 then 2 as well as 3 then 4. Then everything if fine.

However, if not, my system may crash. For example, consider 2 3 4 1 (2 happens before 1). In this scenario:

  1. (2) check for message - NO message
  2. (3) store message
  3. (4) notify channels - still NO new subscriber
  4. (1) subscribe - late, notify already happened
#

@worthy hatch @pine sequoia @honest shell @rocky atlas

honest shell
#

yes, 1 will happen before 2, and 3 will happen before 4

#

because 1/3 are sequenced before 2/4, they have a happens-before relationship

#

(that's part of requirement 2 in the memory model: happens-before relationships are the union of all sequenced-before and synchronized-before relationships)

#

like i said back in #go-chat, as long as no data races exist, program statements execute in order. that's not necessarily a declaration that they are done so in the hardware as such, but it's a declaration that you cannot prove it false.

#

if 2 could be observed to happen before 1, that statement would be proven false, which is a contradiction

gusty pecan
#

Well yes, I know that "everything before" sync primitive will happens-before "everything after" sync primitive, but I also know that compiler can do some optimization on code in "everything before" and on code in "everything after" for faster execution. Since 1) (write channel) and 2) (check for message) are totally independent operations, it can theoretically change the order. That's where my confusion came from 😛

honest shell
#

it cannot change the order in any way that would be observable by a non-racy program

#

that's the limitation

#

(it even technically cannot be observed by a racy program, because you can always explain it away by an old value being read because of the race)

#

let me try that explanation again

#

from the perspective of the memory model: no, no reordering can happen

#

does reordering happen in hardware or even the compiler? sure, but it's Go's job to make it impossible to view that reordering

#

you are programming against this abstract memory model, not the hardware

#

the statements being independent doesn't matter at all from the memory model's point of view, because they are sequenced

#

it's totally irrelevant, the guarantee still holds

honest shell
gusty pecan
#

That's why they say data-race-free programs execute in a sequentially consistent manner, right? Within goroutine statements are executed in sequence, and statements from different goroutines are executed in some order (if we have synchronization we would also know in which one; at least for some of them) 😛 However, on compiler and hardware level in can change (reorder) the things, but the sequentially consistent execution MUST apply and I am programming in that abstraction 😄

honest shell
#

yes, though sequential consistency doesn't matter for the execution of one single goroutine

#

the "sequential" in "sequential consistency" and "sequenced" aren't directly related

#

the execution model of a single goroutine is stronger than sequential consistency, because it guarantees a specific ordering, not just some sequential ordering

gusty pecan
#

Well, in sequential consistency paper Lamport says that instructions from the same process (in our case goroutine) is executed in program order (without reorganization)

gusty pecan
honest shell
#

well that, but also just that line x executes before x+1

#

(ok, if there are no backwards jumps, you get what i mean 😁)

gusty pecan
honest shell
#

that is requirement R1 in the paper

gusty pecan
#

Yes

honest shell
#

the paper is a (loose) proof that the two requirements result in sequential consistency, but that does not necessarily mean that sequential consistency requires those two things (despite the wording)

#

it's a one-way proof

gusty pecan
#

sequencial CPUs, R1, R2 -> s sequential consistency
sequential consistency /-> sequencial CPUs, R1, R2

honest shell
#

correct, the converse of a statement is not necessarily true

#

it may well be, but that's not what's proven in the paper

#

(at least from my reading)

gusty pecan
#

So thats how you know it has an error. You read it 😛

honest shell
#

i quickly skimmed it yesterday. i don't think i had read this previously but i've certainly been around lamport's works

#

paxos is easily the seminal paper in the entire field

#

and/or lamport clocks, depending what you define as the field

gusty pecan
#

Paxos is around consensus algorithms, right?

honest shell
#

yeah, i suppose i was being a bit loose there

#

in-hardware concurrency and distributed systems do differ in some key ways, but they share a ton of overlap

gusty pecan
#

I read something about hardware and its memory model

#

There is also a good book: "A Primer on Memory Consistency and Cache Coherence"

#

Well I guess it's good, did you hear about it?

honest shell
#

no, i truthfully don’t know a ton about the hardware level

#

or even memory model considerations at the ISA level

#

my background stems more from above, in the distributed systems realm

gusty pecan
#

What confuses me in requirement 1 of golang memory model:

"The memory operations in each goroutine must correspond to a correct sequential execution of that goroutine, given the values read from and written to memory. That execution must be consistent with the sequenced before relation, defined as the partial order requirements set out by the Go language specification for Go's control flow constructs as well as the order of evaluation for expressions."

They say partial order, not total order

gusty pecan
honest shell
tame leafBOT
#
Spec: "Order of evaluation"

Order of evaluation

At package level, initialization dependencies determine the evaluation order of individual initialization expressions in variable declarations. Otherwise, when evaluating the operands of an expression, assignment, or return statement, all function calls, method calls, [receive operations](https://golang.org/ref/spec#Receive operator), and binary logical operations are evaluated in lexical left-to-right order.

For example, in the (function-local) assignment

y[f()], ok = g(z || h(), i()+x[j()], <-c), k()

the function calls and communication happen in the order f(), h() (if z evaluates to false), i(), j(), <-c, g(), and k(). However, the order of those events compared to the evaluation and indexing of x and the evaluation of y and z is not specified, except as required lexically. For instance, g cannot be called before its arguments are evaluated.

More documentation omitted

honest shell
#

that may not be all, but that alone is enough to disqualify a total order

gusty pecan
honest shell
#

sequential consistency is a model for concurrent execution; a single goroutine is not concurrent

#

statements are executed in the "expected" order, that's the strongest guarantee possible

gusty pecan
honest shell
#

yes, it doesn't make sense to talk about sequential consistency within a goroutine

#

only between goroutines

gusty pecan
#

Al right, so the conclusion is that in DATA-race-free program I can observe execution as line X always executes before X+1 (within line X, follow the specification), and that's it (no reordering). Reordering can happen on compiler and hardware level but that's on golang to "fix"/"handle".

#

I highlighted the DATA since we can have other "types" of races, and it's only important to be free of DATA races

#

@honest shell Something like this? 😄

honest shell
#

sounds right to me, yep!

gusty pecan
worthy hatch
#

thanks for having made this a thread

#

that messageTypeExists function looks odd. also not sure what is the logic behind shoving one out of possibly many messages into the channel seems all of them should be

gusty pecan
worthy hatch
#

triple negation is harder to read than needed, I can’t tell when it is used if it forces only that one type or prevents it

#

your findmessage in subscribe, it puts only 1 message in the channel

gusty pecan
gusty pecan
worthy hatch
#

why is it doing that in subscribe and something else in store&notify (as in why not 0, also you might want to make the channel buffered)

#

I don’t see in storemessage that it forces you only have 1

gusty pecan
#

With closures and hitFunc

#

In store&notify I won't have ID

#

I mean, I can somehow store channels together with ID and Type, but it's just demo

worthy hatch
#

not sure what ID is given there is no code above with that name

gusty pecan
#

Well message will have different kind of ID to compare (it can be some string, or it can be a set of fields), and when goroutine calls Subscribe it will define hitFunc and within it will compare the message ID with some closure

worthy hatch
#

my point is simple: you can call store() 10 times with the same message then 1 more times in store&notify(), if you already had subscribed before you will get all 11 messages, if subscribed in middle you get 1 dup (maybe, depending what hitFunc actually is) + 11 later, changing the order… it’s odd (and seems unnecessary)

gusty pecan
#
...
clientID := getClientID(...)
ch, _ := Subscribe(NewOrderType, func(messages []any) (any, bool){
  for message := messages {
    if clientID == message.ClientID {
      ....    
    } 
  }
  ..
})
...
#

Something like this

gusty pecan
#

But as I said, it's just demo. I made it in 1h think, nothing special

#

And has a lot to improve and think about (for example, if no1 listen on channel and we already have 1 message in channel, then the StoreAndNotify will block and entire system crache 😄 )

#

@worthy hatch So yea, a lot of things to do, the actual point was about order

worthy hatch
#

you want the code to be correct (and as simple and fool proof as possible) none of the map stuff has an impact on the order question (single channel is enough for that), it just complicates,

and conversely if it’s meant to become real code then it’s better if it doesn’t have traps or unchecked assumptions about X called only once for instance

#

btw even called once my point is same about 2 vs 3 messages (instead of 11 and 12)