T-SQL Weighted Round Robin Algorithm

In a previous post I was discussing of ways to load balance MSMQ messages to a group of servers by implementing a Weighted Round Robin Algorithm in a software module.

I chose to implement the load balancing feature in the database for 2 main reasons:

• The application is heavily database driven; stored procedures have to run to retrieve the data that will be used to build each MSMQ message. Therefore, the cost of an additional statement or stored procedure to retrieve the MSMQ path the message should be sent to is much less than the existing cost.
• All the application configuration information is also database driven. This is because our organization uses custom tools for administrators so that they can configure servers and applications centrally. In the case at hand, they need to be able to modify queue names, machine relative weights as well as to add and remove machines from the load balanced group of server (the cluster).

The Weighted Round Robin algorithm is implemented as a stored procedure returning the next MSMQ path a message should be sent to. The stored procedure could be bundled or merged with the other stored procedures that have to run before each MSMQ message is sent, so that it would only be one more parameter coming back from the database. This parameter will tell the .Net code to which queue the current MSMQ message build has to be sent to.

T-SQL Weighted Round Robin Algorithm Implementation.

Each machine of a cluster should receive a percentage of messages which is relative to its weight:
%age = ((weight of machine) / (sum of weights for all the machines in the cluster)) * 100
Moreover, the distribution of messages to each machine should be function of the weight in real time, not only in average.

To satisfy these conditions, one way to implement the weighted round robin algorithm and which suits well T-SQL capabilities is to calculate a ratio between the relative number of messages sent to a particular machine of a cluster and the relative weight of that machine within the cluster. The machine having the higher ratio will be the next machine a MSMQ message should be sent to in respect with its relative weight. An ORDER BY clause will easily implement that in T-SQL.

First of all, we need to create a table where we will hold the different server parameters:

Column name	Data type	Purpose
server_name	[nvarchar](20)	Machine name
cluster	[char](10)	Cluster name in which the machine belongs to
queue_path	[nvarchar](100)	MSMQ path
number_requests_sent	[float]	Number of request sent to this machine so far
weight_factor	[float]	Weight factor of this machine
enabled_status	[bit]	Says if the machine is active or inactive in the cluster

Here is the SQL script to create the table:

SET ANSI_NULLS ON

GO

SET QUOTED_IDENTIFIER ON

GO

SET ANSI_PADDING ON

GO

CREATE TABLE [dbo].[msmq_machines](

[server_name] [nvarchar](20) NOT NULL,

[cluster] [char](10) NOT NULL,

[queue_path] [nvarchar](100) NOT NULL,

[number_requests_sent] [float] NOT NULL CONSTRAINT [DF_msmq_machines_number_requests_sent]DEFAULT ((0)),

[weight_factor] [float] NOT NULL CONSTRAINT [DF_msmq_machines_weight_factor]DEFAULT ((100)),

[enabled_status] [bit] NOT NULL,

CONSTRAINT [PK_msmq_machines] PRIMARY KEY CLUSTERED

(

[server_name] ASC,

[cluster] ASC

)WITH (PAD_INDEX= OFF, STATISTICS_NORECOMPUTE= OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS= ON, ALLOW_PAGE_LOCKS= ON) ON [PRIMARY]

) ON [PRIMARY]

GO

SET ANSI_PADDING OFF

Second we need to create a Stored Procedure that will actually implement the algorithm:

SET ANSI_NULLS ON

GO

SET QUOTED_IDENTIFIER ON

GO

CREATE PROCEDURE [dbo].[GetLoadBalancedQueueName]

@cluster as char(10),

@serverName as nvarchar(20) out,

@queuePath as nvarchar(100) out

AS

DECLARE @totalClusterRequestSent as float

DECLARE @totalWeight as float

SELECT @totalClusterRequestSent = sum(number_requests_sent)+1, @totalWeight = sum(weight_factor)

FROM dbo.msmq_machines

WHERE cluster = @cluster

AND enabled_status = 1

SELECT top 1 @serverName = server_name, @queuePath = queue_path

FROM dbo.msmq_machines as A

WHERE A.cluster = @cluster

AND A.enabled_status = 1

order by (number_requests_sent/@totalClusterRequestSent)/(weight_factor/@totalWeight), weight_factor desc

UPDATE dbo.msmq_machines

SET number_requests_sent = number_requests_sent + 1

WHERE server_name = @serverName

AND cluster = @cluster

Note on the T-SQL implementation:

• In the definition of the table msmq_machines, I have chosen data types to be float instead of integers (as they actually will hold only integers values) so that no data type conversion is needed when calculating ratios.
• @totalClusterRequestSent is calculated as the sum of number_requests_sent + 1 so that if the sum of number_requests_sent is 0 (zero), no division by zero error occurs.

In addition of this, an SQL job will have to run on a regular basis to re-initialize the number_requests_sent column to 0 (zero) so that the value never overflows the data type.

T-SQL weighted Round Robin algorithm Testing

We can test if the algorithm works as expected by creating 3 machines in the msmq_machines table and give them different weights:

If we send 100 messages to the cluster “Bangkok”:

• DEV1 should receive (100 / 350) * 100 = 28.57 -> 29 messages
• DEV2 should receive (200 / 350) * 100 = 57.14 -> 57 messages
• DEV3 should receive (50 / 350) * 100 = 14.28 -> 14 messages

We can create an SQL script that calls the Stored Procedure 100 times and see if the result is what is expected.

declare @counter int

set @counter = 0

while @counter < 100

begin

set @counter = @counter + 1

DECLARE @server as nvarchar(20)

DECLARE @msmq as nvarchar(100)

EXEC [dbo].[GetLoadBalancedQueueName] ‘Bangkok’ , @serverName = @server out, @queuePath = @msmq out

print @server

print @msmq

end

Opening the msmq_machines table, we can see that the expected number of messages has been sent to each server of the cluster proving that the implementation works.