Leaky bucket most efficient method

Help and Feedback Code Review
,
#1

I have two different leaky bucket scripts and these are the two loops:

First 
while true do
		if not next(entries) then -- if there is no entries then wait for an entry to be added
			module.EntryAdded:Wait()
		end
		for index, v in pairs(entries) do
			if tick() - v.createTime >= v.timeLength then
				entries[index] = nil -- remove from entries table
			end
		end
		stepped:Wait() -- RunService.Stepped:Wait()
	end
Second 
while true do
		if not next(entries) then -- if there is no entries then wait for an entry to be added
			module.EntryAdded:Wait()
		end
		local minimalWait = 0.03 -- default minimal wait
		for index, v in pairs(entries) do
                        local tickLengthRemainder = tick() - v.createTime -- tick difference from creation tick
			if tickLengthRemainder >= v.timeLength then
				entries[index] = nil
			else
				local waitTimer = v.timeLength - tickLengthRemainder
				if waitTimer < minimalWait then
					minimalWait = waitTimer
				end
			end
		end
		wait(minimalWait)
	end

The first one uses a RunService.Stepped:Wait() approach to constantly run iterations until the current tick minus the tick of the entry is longer than the supposed run time of the entry then remove it from the entries table.

The second one tries to find the lowest difference of the current tick minus the entry’s tick then use that as a wait. I believe this approach might create more inaccurate/unprecise waits but I could try an offsetted minus wait like math.min(minimalWait - 0.1, 0.03).

What I mean by entry’s tick is when the entry was made by marking its creation with tick() and the time length is set in a table with the creation tick() as well.

This is what an entry table would look like:

entries[entry] = { -- entry can be anything, including a player or player name
    createTime = tick(),
    timeLength = 2 -- this is an example number, it is how long the entry will last until being removed
}

Example function that would check if there is a given entry already (aka its in the bucket and you must wait):

local function inBucket(entry)
    return entries[entry] ~= nil
end

I just want to know which is technically more efficient or better, maybe even a different entire approach if possible as this is my first time making a leaky bucket module.

#2

Hmm cool approaches for sure; they both look quite efficient.

You have the same order of complexity inside the while loop on each approach; Θ(entries). The second one just iterates less and is more conscious about the elements in the bucket.

When it comes down to precision, stepped is of variable length in sync with physics frames. So I don’t think using a fixed wait time will be any less accurate, because any error in subtracting float numbers will be significantly small. Each implementations precision is bounded by the precision of tick().

So It’s hard to say which is better; but if I was expecting to have a large number of elements in the bucket at one time I would use the first one. Otherwise second one.

#3

Yeah I would go with the first one too, thank you for your feedback!

I reduce the need to needlessly wait using a BindableEvent so I think this is as efficient as it gets.

#4

Abstract will rarely be efficient enough for all usecases. Here’s an example implementation of “leaky bucket” for limiting player remote event calls:

local SpamCheckers = {
		--[[
		{
			PlayerBudget = {}, -- [table] {[player] = calls, ...}
			_id = 1, -- [integer] spam checker object index
			_calls_per_second = 1, -- [integer] Client budget every second
		},
		...
		--]]
	}

local function SpamCheckerUpdate()
	if tick() > NextUpdate then
		
		NextUpdate = tick() + 1
		
		for _, spam_checker in ipairs(SpamCheckers) do -- Update all spam checkers by setting player budget values to max
			local calls_per_second = spam_checker._calls_per_second
			local player_budget = spam_checker.PlayerBudget
			for player, _ in pairs(player_budget) do
				player_budget[player] = calls_per_second
			end
		end
		
	end
end

It just resets the player_budget every second (One budget is used whenever a player invokes a remote event) - it will effectively prevent any practical attempt at spamming the server to death.

1 Like
#5

Actually I think my use here is too different for a leaky bucket approach, more like a custom leaky bucket, I wanted to create something like facilitating cooldowns for things, sort of a server-side debounce.

Your example is a good approach for remote event spam prevention and I’ll keep it in mind for preventing request spam. Do remote request spam have any effect though? Roblox already prevent really fast spam anyways on remotes.

EDIT: What do you mean by “Abstract”?

#6

Yeah you wouldn’t get any benefit from preventing spam for remotes that either going to run one or two lines of code or have a built-in cooldown for doing something. You are going to want to spam check or throttle in any other way client requests for altering their appearance or anything that could lead to large graphical or data updates among the rest of the server and other clients.

I assumed your leaky bucked implementation was abstract, because I didn’t really notice you mentioning an exact implementation XD As you can see - clearing entries only after their time has expired is not always the most efficient way to solve a specific usecase. Regardless - it’s written pretty solid for what it is.

1 Like