A coupon management system stores a definition of a coupon and also every time a user redeems a coupon. A coupon consists of an id, a title, a start date, end date, maximum number of coupons per user and also a maximum number of coupons across all users. When a user redeems a coupon the system keeps track of the users identifier, the datetime when the redemption occurred and a unique code that is generated by the application.
The coupon management system is required to provide the following capabilities:

• Provide an active list of coupons.
• Determine if a consumer can redeem a coupons.
• Store redemptions as they occur.
• Provide reporting on the redemptions for a specific offer.

The coupon management system is expected to have the following capacity:

• Coupons up to 50000 unique coupons. Generally 100-500 active at any point in time.
• Redemptions – Upwards of 1 billion rows. Expect at least 1 million redemptions per day.

Requirements:

1. Create a data model to represent the data in the above scenario. You are free to choose any storage mechanism you feel appropriate. The model should take into account the volume and expected operations into account.
2. Define additional optimizations that you would apply to the basic data model. (For example if you were to choose SQL you might want indexes on certain columns) Note: Implementation/Code is not required.

My solution:
For the given requirements, we could leverage Cosmos DB in Azure as a backend datastore for the Coupon management system. Key motivation for selecting Cosmos DB is the considerable price savings in comparison to a SQL cluster, while at the same time providing for a scalable and highly available data storage environment.
We will have a database that is configured for multi-region read-write to ensure high availablity. By default Cosmos DB indexes all fields in a document. We will define a custom indexing policy to only index the fields that we are interested in. This will lower the amount of storage used and improve the latency with writes.

Entities
In addition to the below mentioned fields, each entity will also define a partition key. The different entity sections will define how the partition key is created.

CouponDefinition
To store the different coupons and its related properties.

Field Name Type Notes
CouponDefinitionId Guid This will be the id field of the document to enforce unique constraints. It is called CouponDefinitionId here to make it very explicit and for easier reference from other entity sections.
Title String
StartDate Date
EndDate Date Will have an index against this field to support the list of active coupons query.
MaximumNumberOfCouponsPerUser Integer
MaximumNumberOfCoupons Integer
Partition key will be the string constant "CouponDefinition" across all records for this entity type.

CouponRedemption
Used to record a coupon redemption.

Field Name Type Notes
CouponRedemptionId Guid Unique id generated by the application when a coupon is redeemed. Will map to the id field of the document to enforce unique constraints.
RedemptionDate DateTime
CouponDefinitionId Guid This will be the partionkey for this document type.
UserId Guid
UserCouponRedemption
Used to keep a count of redemptions made by each user.

Field Name Type Notes
CouponDefinitionId Guid This will be the partionkey for this document type. The value will be prefixed with the string "UserCouponRedemption".
UserId Guid This will be the id field for the document to ensure unique constraints.
RedemptionCount Integer Total number of redemptions made by the user for the coupon identified by the CouponDefinitionId field.
Queries

1. Provide a list of active coupons
   This can be retrieved by querying for CouponDefinition records with a filter on the EndDate.

2. Determine if a customer can redeem a coupon
   The assumption here is that there are two requirements to be met before a user can redeem a coupon:

Total number of coupon redemptions is less than or equal to MaximumNumberOfCoupons field in the coupon definition.
Total number of coupon redemptions for a user is less than or equal to MaximumNumberOfCouponsPerUser field in the coupon definition.
Solutions for requirment 1 are discussed further below. To meet requirement 2, we maintain a UserCouponRedemption record for each user, coupon combination. When a request is made to redeem a coupon:

We first check this record to determine the number of existing redemptions by a user.
We then proceed to increment and update the redemption count for the user.
Cosmos DB provides an etag field for every document which can be used for optimistic concurrency checks when updating the redemption count.
Requirement 2 requires us to keep an exact count of the number of redemption per coupon. This is a hard problem in a high volume distributed environment. Few solutions are proposed below:

1. Not enforcing a strict count on the total redemptions per coupon
   In this model we keep an in memory count of the number or redemptions made for an active coupon.
   This list is periodically updated by a background task. We can leverage the change feed feature of Cosmos DB to calculate this count.
   A request to redeem a coupon will be checked against this in-memory count before proceeding further.
   The disadvantage with this approach is that we could potentially over redeem a coupon during a small window, but may be an acceptable compromise by the business.

2. Pregenerate a list of CouponRedemption entries for a coupon
   In this model, the coupon redemptions entries for a coupon are pre-populated.
   The CouponRedemptionId and RedemptionDate fields for the record will be empty initially.
   When redeeming a coupon, we fetch a record with an empty CouponRedemptionId and update the CouponRedemptionId and RedemptionDate fields accordingly.
   CouponRedemptionId field will be indexed to make this query efficient.
   If the system is used alongside a shopping cart, where a redemption involves first adding the coupon to the cart and then redeeming it as part of payment, a separate field could be added to track this Reserved status which will then be updated to Confirmed.
   Key considerations: The above model ensures that we dont over redeem coupons. The requirement to pre-populate CouponRedemption entries has some implications which should be considered.
   Upfront cost of provisioning these records. This may mean that we will have to run with a higher RU allocation than would be otherwise required. However if we operate in a model where the Coupons are created in advance before it goes on sale, this pre-generation could be scheduled to a non-busy period for the system.
   A coupon may not be used to its full capacity, this would result in a lot of empty records and increased space consumption. We could provision these records with a Time To Live (TTL) setting that is set to expire when the coupon expires, or alternatively we could have a clean up job to remove the unused entries.

3. Adopt a single writer approach
   The key issue we are facing here is that it is hard to keep an accurate count when there are concurrent writes.
   If we serialize these writes, then a single writer could keep track of the coupon redemption count.
   The challenge is that this approach wont scale in high workload environment.
   One approach is to shard the number of redemptions for a coupon across multiple nodes. Say for eg: a coupon has 1000 redemptions, then Node A can do upto 500 redemptions and Node B does the rest.
   We will require a smart router fronting these nodes, that can route the request based on the Coupon.
   Key considerations:
   This approach has the best of both worlds - preventing over redemptions and keeping the Cosmos DB cost minimal.
   However this comes with increased operational and development overhead.
   We can tweak and adopt these approaches to best fit the business model. If we can allow for some amount of over-redemptions then option 1 is preferred, followed by options 2 and 3.

4. Store redemptions as they occur
   Every redemption will create a CouponRedemption record after populating the required fields.

5. Provide reporting on the redemptions for a specific offer
   While a typical SQL model will allow for adhoc reports after the schema has been defined, the desired query patterns needs to be thought upfront with a NoSQL design. Some assumptions made here:

We need to report on the total redemptions for a coupon
The redemptions made should be reported per week or day or another unit of time as desired.
For one of the above queries, we need to keep track of the total redemption count per coupon. The Change feed feature in Cosmos DB helps us to keep a running total of this count. We could persist this information for the desired time frame , as a new entity type to help with reporting. A background process can periodically consume these new record types and create a tailor fit materialised view for the report.