Table of Contents

Greylisting - centralized versus distributed databases

When filtering messages for some domain is done in multiple MXs, there are two basic ways to manage databases for greylisting : having a single database accessed by all MXs or having a copy of triplets database distributed over all nodes.

In the centralized database implementation, when a node needs to handle a triplet, it queries the central node, who knows everything happening on all nodes.

In the distributed database, each node contains the history off all nodes and can locally handle all triplets. Each time it sees a new triplet or change the state (validate it) of some triplet it sends the information to all other nodes, so they are able to handle this same triplet if it appears elsewhere.

Centralizing database is simpler but it's a point of failure. Distributing database over all nodes requires synchronisation of data over all nodes.

ze-filter implements an intermediate solution which consists of having a centralized database and a local dababase on each node. The database located on each node contains only the information handled by the node. When a node handles a triplet, it looks for the required information at local database - if it's there it uses it otherwise it queries the central server. If it updates its local database, it sends the information to the central database. This way each node knows only its own history and the central database knows the history of all nodes.

In the distributed implementation, each node knows the history of all nodes, as everything present at each node is propagated to all other nodes.

Paragraphs bellow try to determine behaviours of both greylisting architectures, beginning with the simpler situation and adding complexity to it to arrive to real world situations.

Analysis - 1

Let's consider a cluster of mail servers handling SMTP connections. Suppose an experiment with some duration, long enough to validate most triplets, but not too long so triplets won't expire - something like one or two days is good.

Let N be the number of nodes in the cluster, M the number of different triplets handled by the cluster (all nodes), and k the fraction of triplets which will finally be validated.

Initially we'll suppose that each triplet will be validated in the same node at which it was presented the first time. This restriction will be removed further.

With these assumptions, the number of triplets handled by the cluster is M * (1 + k) and each node will handle M * (1 + k) / N triplets.

Network Traffic

Messages Exchanged ze-greyd Synchro MX Ratio
Sent (each node) M * (k + 1) / N M * (k + 1) * (N - 1) / N (N - 1)
Received (each node) 0 M * (k + 1) * (N - 1) / N N.A.
Total (each node) M * (k + 1) / N 2 * M * (k + 1) * (N - 1) / N 2 * (N - 1)
Global M * (k + 1) M * (k + 1) * (N - 1) (N - 1)

CPU cycles

Each message received by a node costs some CPU cycles. Let p be the ratio between the number of CPU cycles required to handle a triplet from an incoming SMTP connection and those required to handle a synchronisation message.

p take the value 1 if both processing wastes the same number of CPU cycles. If the cost of handling synchronisation messages is half the cost of handling the triplet of an incoming SMTP connection, p equals 0.5.

Messages Handled (each node) ze-greyd Synchro MX Ratio
Raw count M * (k + 1) / N M * (k + 1) N
Weighted count M * (k + 1) / N M * (k + 1) * (1 + p * (N - 1)) / N (1 + p * (N - 1))

You can play with these formulas for different values of p and N.

Database sizes

Records ze-greyd Synchro MX Ratio
Node M / N M N
- Validated triplets M * k / N M * k N
- Pending triplets M * (1 - k) / N M * (1 - k) N
Central database M - -

Analysis - 2

In the previous paragraph we've imposed that each triplet should be validated in the same node it was presented for the first time. Let's remove this restriction and see how this will change previous results.

Records ze-greyd Synchro MX Ratio
Node M * (1 + k * (N - 1) / N) / N M N * N / (N + k * (N - 1))
- Validated triplets M * k / N M * k N
- Pending triplets M * (1 - k / N) / N M * (1 - k) N * N * (1 - k) / (N - k)
Central database M - -

Analysis - 3