Scalable approximate counting

A method for implementing an intentionally approximate counting scheme, said method comprising:

• accessing a counter that is included in a portion of code, wherein the counter is structured to update a count that is approximately representative of a number of times the code portion is called or executed;
• causing the counter to operate in a first mode, wherein the first mode is a mode in which the counter updates the count by a value of 1, and wherein, while the counter is operating in the first mode, a probability by which the counter updates the count is set to a value of 1 such that the counter updates the count each time the code portion is called or executed;
• determining the count has reached a first threshold while the counter is operating in the first mode;
• causing the counter to switch from operating in the first mode to operating in a second mode, wherein the second mode is a mode in which the counter updates the count by a value of N, where N is an integer larger than 1, and wherein, while the counter is operating in the second mode, the probability by which the counter updates the count is set to a value of 1/N such that, despite multiple calls being made to the code portion, the count is updated in accordance with the 1/N probability;
• causing the counter, which is now in the second mode, to continue to update the count, wherein the count is updated in accordance with the 1/N probability, and wherein the counter updates the count by the value of N;
• and
• writing, each time the count is updated, a value of the count to a storage system.

A computer system comprising:

• a processor system;
• and
• a storage system that stores instructions that are executable by the processor system to cause the computer system to:
• access a counter that is included in a portion of code, wherein the counter is structured to update a count that is approximately representative of a number of times the code portion is called or executed;
• cause the counter to operate in a first mode, wherein the first mode is a mode in which the counter updates the count by a value of 1, and wherein, while the counter is operating in the first mode, a probability by which the counter updates the count is set to a value of 1 such that the counter updates the count each time the code portion is called or executed;
• determine the count has reached a first threshold while the counter is operating in the first mode;
• cause the counter to switch from operating in the first mode to operating in a second mode, wherein the second mode is a mode in which the counter updates the count by a value of N, where N is an integer larger than 1, and wherein, while the counter is operating in the second mode, the probability by which the counter updates the count is set to a value of 1/N such that, despite multiple calls being made to the code portion, the count is updated in accordance with the 1/N probability;
• cause the counter, which is now in the second mode, to continue to update the count, wherein the count is updated in accordance with the 1/N probability, and wherein the counter updates the count by the value of N;
• and
• write, each time the count is updated, a value of the count to the storage system.