Some embodiments provide a method of performing stateful services that keeps track of changes to states of service nodes to update connection tracker records when necessary. At least one global state value indicating a state of the service nodes is maintained at the edge device. The method generates a record in a connection tracker storage including the current global state value as a flow state value for a first data message in a data message flow. Each time a data message is received for the data message flow, the stored state value (i.e., a flow state value) is compared to the relevant global state value to determine if the stored action may have been updated. After a change in the global state value relevant to the flow the method examines a flow programming table to determine if the flow has been affected by a flow programming instruction(s) that caused the global state value to change.