Deterministic Time Slicing

Is this new? I’ve been fighting with the fact that the local replica doesn’t have cycle simulation for months. This is great news if we now have cycle simulation on the local replica.

1 Like

Cycles and instructions are two different things. We do not have cycles simulation on the local replica. We have instruction simulation though. Instruction simulation is putting limits on how long a message can execute for. Cycles simulation is actually paying for resources that a canister is using.

I regularly have functions that work fine on the local replica and hit a limit in production. Is there a switch to turn this on?

2 Likes

I think the confusion also stems from the wording…

To ensure fast finality, IC imposes a limit on the number of instructions per WebAssembly call. If the limit is exceeded, then the execution traps with an error:
Canister <id> exceeded the cycles limit for single message execution.

Shouldn’t the error message say “exceeded the instruction limit”?

1 Like

@akhilesh.singhania: doesn’t dfx use the configuration of the system subnet by default, which has much higher instructions limits? I heard that there was a feature request to add a flag to use the application subnet configuration, but don’t know whether it materialized or not.

Shouldn’t the error message say “exceeded the instruction limit”?

Good point! I’ll prepare a fix for this message.

3 Likes

Good catch Ulan! Yes, this is why @skilesare is seeing the problem he reported above. We should really try to get the local replica to emulate the mainnet as closely as possible.

6 Likes

That feature would alleviate a massive pain in the developer experience, so I’m super enthusiast to see it implemented.

Is this still in the pipes ? Any news or update on this ?

2 Likes

Thanks, it is great to hear that the feature will be useful! We are implementing it and hoping to get the initial prototype around end of May/June.

5 Likes

Just wanted to check back in regarding the progress on the Deterministic Time Slicing feature.

I’ve been load testing insertion into several data structures recently (Buffer, HashMap, RBTree), all of which seem to start hitting the message instruction limit on canisters much earlier than their heap capacity, regardless of their insertion runtimes ( i.e. O(1) vs. O(log(n) ).

I’d be interested in further testing out how these data structures perform as they scale within canisters, and DTS would be key in doing so.

Just curious @ulan or @dieter.sommer - is some variant of Deterministic Time Slicing enabled for the bitcoin integration project, or are all update types of transactions/operations able to be completed over a single round of consensus?

5 Likes

The implementation of DTS is close to completion. We hope to merge the main remaining changes in 1-2 weeks. After that we need to do stress testing to ensure that we didn’t not miss anything. Once that’s done I’ll update this thread and give a more concrete timeline for shipping.

(Buffer, HashMap, RBTree) all of which seem to start hitting the message instruction limit on canisters much earlier than their heap capacity, regardless of their insertion runtimes

That is expected for HashMap because it occasionally copies the entire backing store in O(n) time, but the result for RBTree is surprising because it should have the worst case runtime of O(m * log(n)) where m is the number of operations and n is the number of elements. As long as m is not large for each message (e.g. doesn’t exceed 10^6), I would expect it to not hit the instruction limit.

is some variant of Deterministic Time Slicing enabled for the bitcoin integration project, or are all update types of transactions/operations able to be completed over a single round of consensus?

AFAIK @ielashi has carefully designed the operations to not exceed a single round.

8 Likes

At the moment, the Bitcoin API is implemented in the replica, which means we’re not subject to the same cycles limitation as Wasm canisters. We’ve added some measures so we don’t spend too much time on execution within the round, however these measures are rather crude.

We’re now in the process of migrating the Bitcoin API into a wasm canister, and there we’ll be subject to the same cycles limitation as all other canisters. Some computations like block ingestion do require a lot of cycles, even more than what DTS will initially support, and for that we’ll be implementing a simple slicing logic within the canister to stay within the cycles limit.

8 Likes

Great to hear, thanks for the update!

How many rounds of consensus and cycles do you see some of these operations taking?

Also, would love to hear a bit more about the strategies/techniques behind what this simple slicing logic looks like - is it implemented on the replica level or directly in the API (in a way that is currently accessible to IC developers)?

2 Likes

I have seen some large blocks take up to 385B instructions to be ingested. With a 5B instruction limit, that translates to ~77 execution rounds. A large block can have tens of thousands of inputs/outputs, which translates to tens of thousands of insert/remove operations on our StableBTreeMap data structures. These numbers are using the code that we have in the replica as-is. I expect there would be some low-hanging optimizations that would help reduce the required number of instructions.

Also, would love to hear a bit more about the strategies/techniques behind what this simple slicing logic looks like - is it implemented on the replica level or directly in the API (in a way that is currently accessible to IC developers)?

We’ll be adding the slicing logic in the canister itself. It hasn’t been written yet, but it’ll be highly specific to the case of block ingestion, so it’s unfortunately not something that can be packaged up and used elsewhere. I’ll share pointers to the slicing code as soon as its available.

On the API level, you may have noticed we added pagination to our get_utxos endpoint, which was one way we were able to stay within the instructions limit for these requests.

5 Likes

Quick update: we are aiming to enable deterministic time slicing on master in the week of September 19th and to roll it out to the mainnet in the subsequent week.

24 Likes

Do you mind sharing the GitHub PR and/or the “Bless Replica Version” NNS proposal when they become available? This is quite an important feature. Thanks!

4 Likes

Do you mind sharing the GitHub PR and/or the “Bless Replica Version” NNS proposal when they become available?

Absolutely! I’ll share the PR and the proposal. We are currently fixing two blockers that may delay the launch a bit.

8 Likes

We are currently fixing two blockers that may delay the launch a bit.

One of these blockers turned out to be more tricky than we thought. We are still working on it.

3 Likes

Are any of the blockers something that the community can give input on/or help with in an advisory capacity?

3 Likes

Thanks for the offer! It is more of an implementation issue about how to ensure correctness of DTS state in certain cases. We have an idea on how to solve and are currently implementing it.

4 Likes

Never give up, never surrender! You’re doing such excellent work

11 Likes