# US 2012/0075996 A1 · Techniques to support large numbers of subscribers to a real-time event

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0075996 A1
- Document ID: US20120075996A1
- Status: Published application
- Kind: A1
- Application number: 12/892,649
- Filed: 2010-09-28
- Published: 2012-03-29
- Earliest claimed: 2010-09-28
- Assignees: Microsoft Corporation
- Inventors: Cheuk Wan William Lau; RaviKant Cherukuri; Stephen Gordon; Offir Bakshitz
- Web page: https://patentgrep.com/patent/US20120075996A1

## CPC

- H04L 51/214: using selective forwarding
- G06F 16/335: Filtering based on additional data, e.g. user or group profiles (filtering in web context G06F16/9535, G06F16/9536)
- G06F 16/35: Clustering; Classification
- G06F 16/353: into predefined classes
- G06F 16/9535: Search customisation based on user profiles and personalisation
- G06F 16/958: Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking
- H04L 12/1859: {adapted to provide push services, e.g. data channels}
- H04L 43/16: Threshold monitoring
- H04L 51/04: Real-time or near real-time messaging, e.g. instant messaging [IM]
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Techniques to manage large numbers of subscribers to real-time events are described. Embodiments may filter subscribers dynamically into buckets where publications are distributed only to subscribers in the same bucket as the publisher. Buckets may be dynamically created and removed to lower or raise the publication rate for subscribers to an acceptable level. Embodiments may use a two-level bucketing algorithm for filtering that is memory and CPU efficient, and scales with large numbers of subscriptions. The techniques may also reduce the context loss for a subscriber when a new bucket has to be created and subscribers distributed between buckets. Embodiments may be scaled out to multiple servers, to accommodate very large numbers of subscribers and publications. Other embodiments are described and claimed.

## Claims

### Claim 1

A computer-implemented method, comprising:
allocating subscribers to a real-time event to a bucket and a slot within the bucket, the bucket having at least one slot;
monitoring a publication rate for the real-time event;
adding a bucket when the publication rate exceeds a first threshold;
removing a bucket when the publication rate falls below a second threshold; and
publishing a first subscriber publication only to other subscribers allocated to the same bucket as the first subscriber.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
allocating subscribers to a slot in a bucket by hashing a subscriber identifier to a slot number.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
ordering the total number of slots for the real-time event;
allocating slots to a bucket by evenly dividing the slots among the buckets for the real-time event; and
re-allocating the slots among the buckets while maintaining the order of the slots when a bucket is added.

### Claim 4 (depends on 1)

The method of claim 1, wherein monitoring the publication rate comprises:
monitoring a moving average rate of publications per bucket over a number of defined periods.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
monitoring a publication rate for each slot;
adding ordered slots to the bucket while the publication rate is between the second threshold and the first threshold;
adding a bucket and allocating a slot to the added bucket when adding the slot causes the publication rate to exceed the first threshold;
removing the added bucket and allocating any slots in the removed bucket to a previous bucket when adding a bucket causes the publication rate to fall below the second threshold.

### Claim 6 (depends on 5)

The method of claim 5, further comprising:
allocating new slots to existing buckets in a round-robin fashion when no more buckets can be added.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
monitoring the publication rate for each bucket;
dividing one bucket having a publication rate that exceeds the first threshold into two buckets until the publication rate per bucket falls to between the second and first thresholds; and
merging one bucket having a publication rate that falls below the second threshold into another bucket until the publication rate per bucket rises to between the second and first thresholds.

### Claim 8 (depends on 7)

The method of claim 7, wherein merging a bucket comprises:
selecting a second bucket to merge with by selecting the second bucket such that the merged bucket publication rate does not exceed the first threshold.

### Claim 9

An article comprising a storage medium containing instructions that if executed enable a system to:
maintain an ordered set of servers to host a real-time event;
maintain at least one bucket on each server in the set, wherein each bucket on a server corresponds to a bucket on every other server;
allocate a subscriber of the real-time event to a server;
allocate the subscriber to a bucket at the server and a slot within the bucket, the bucket having at least one slot;
monitor a publication rate for the real-time event;
broadcast a first subscriber publication to all servers in the set; and
publish the first subscriber publication only to other subscribers allocated to the same bucket as the first subscriber and to the buckets corresponding to the same bucket on each server.

### Claim 10 (depends on 9)

The article of claim 9, further comprising instructions that if executed enable the system to re-allocate the subscriber to the same or a different server when a server is added to or removed from the ordered set of servers.

### Claim 11 (depends on 9)

The article of claim 9, further comprising instructions that if executed enable the system to select one server in the set of servers as a primary server, wherein the primary server determines the number of buckets and the allocation of slots to buckets to be used by all of the servers.

### Claim 12 (depends on 9)

The article of claim 9, further comprising instructions that if executed enable the system to:
add a bucket at the server when the publication rate at a server exceeds a first threshold; and
remove a bucket from the server when the publication rate at the server falls below a second threshold.

### Claim 13 (depends on 12)

The article of claim 12, further comprising instructions that if executed enable the system to:
order the total number of slots for the real-time event;
allocate slots to a bucket by evenly dividing the slots among the buckets for the real-time event; and
re-allocate the slots among the buckets while maintaining the order of the slots when a bucket is added.

### Claim 14 (depends on 12)

The article of claim 12, further comprising instructions that if executed enable the system to:
monitor a publication rate for each slot;
add ordered slots to the bucket while the publication rate is between the second threshold and the first threshold;
add a bucket and allocate a slot to the added bucket when adding the slot causes the publication rate to exceed the first threshold; and
remove the added bucket and allocate any slots in the removed bucket to a previous bucket when adding a bucket causes the publication rate to fall below the second threshold.

### Claim 15 (depends on 12)

The article of claim 12, further comprising instructions that if executed enable the system to:
monitor the publication rate for each bucket;
divide one bucket having a publication rate that exceeds the first threshold into two buckets until the publication rate per bucket falls to between the second and first thresholds; and
merge one bucket having a publication rate that falls below the second threshold into another bucket until the publication rate per bucket rises to between the second and first thresholds.

### Claim 16

An apparatus, comprising:
a processor; and
a real-time event host module operative on the processor to:
allocate subscribers to a real-time event to a bucket and a slot within the bucket, the bucket having at least one slot;
monitor a publication rate for the real-time event;
add a bucket when the publication rate exceeds a first threshold;
remove a bucket when the publication rate falls below a second threshold; and
publish a first subscriber publication only to other subscribers allocated to the same bucket as the first subscriber.

### Claim 17 (depends on 16)

The apparatus of claim 16, the real-time event host module further operative to:
order the total number of slots for the real-time event;
allocate slots to a bucket by evenly dividing the slots among the buckets for the real-time event; and
re-allocate the slots among the buckets while maintaining the order of the slots when a bucket is added.

### Claim 18 (depends on 16)

The apparatus of claim 16, the real-time event host module further operative to:
monitor a publication rate for each slot;
add ordered slots to the bucket while the publication rate is between the second threshold and the first threshold;
add a bucket and allocate a slot to the added bucket when adding the slot causes the publication rate to exceed the first threshold;
remove the added bucket and allocate any slots in the removed bucket to a previous bucket when adding a bucket causes the publication rate to fall below the second threshold.

### Claim 19 (depends on 16)

The apparatus of claim 16, the real-time event host module further operative to:
monitor the publication rate for each bucket;
divide one bucket having a publication rate that exceeds the first threshold into two buckets until the publication rate per bucket falls to between the second and first thresholds; and
merge one bucket having a publication rate that falls below the second threshold into another bucket until the publication rate per bucket rises to between the second and first thresholds.

### Claim 20 (depends on 16)

The apparatus of claim 16, wherein:
the apparatus is one of a set of servers;
each bucket on the apparatus corresponds to a bucket of each of the other servers in the set; and
the first subscriber publication is published only to other subscribers allocated to the same bucket as the first subscriber and to the buckets corresponding to the same bucket on each server in the set.
