Building a high concurrency student course selection system

Intro

Remember those days when your school system suck so much that you can never pick the course you want? Well, those days are no more. After learning how to design a high concurrency student course selection system. You can make it so that everyone can pick their class in the most fair way possible.

Technology

Node.js, Postgresql, Redis, RabbitMQ

Database design

The first step of building a great system is great data modelling and subsequently a great database design. All following database schema was created in Prisma schema format.

Suppose you are in a school, some common entites in the school are teachers, students, courses, classes. So here we have

model Teacher {
  id           String     @id @default(dbgenerated("uuid_generate_v4()")) @db.Uuid
  idNumber     String     @unique
  name         String
  gender       String
  phoneNumber  String     @unique
  email        String     @unique
  passwordHash String
  age          Int
  jobTitle     String
  departmentId String     @db.Uuid
  department   Department @relation(fields: [departmentId], references: [id])
  courses      Course[]

  enrolledAt  DateTime
  createdAt   DateTime      @default(dbgenerated("now()"))
  updatedAt   DateTime      @default(dbgenerated("now()")) @updatedAt
  deletedAt   DateTime?
  courseClass CourseClass[]

  @@index([idNumber])
  @@index([name])
  @@index([email])
  @@index([phoneNumber])
}

Teachers, who are employees at school, who have jobTitle, email, department and teach some classes.

model Student {
  id            String               @id @default(dbgenerated("uuid_generate_v4()")) @db.Uuid
  idNumber      String               @unique
  name          String
  gender        String
  phoneNumber   String               @unique
  email         String               @unique
  passwordHash  String
  age           Int
  departmentId  String               @db.Uuid
  department    Department           @relation(fields: [departmentId], references: [id])
  courseClasses StudentCourseClass[]
  subjects      StudentSubject[]

  enrolledAt DateTime
  createdAt  DateTime  @default(dbgenerated("now()"))
  updatedAt  DateTime  @default(dbgenerated("now()")) @updatedAt
  deletedAt  DateTime?

  @@index([idNumber])
  @@index([name])
  @@index([email])
  @@index([phoneNumber])
}

Students, who study at school, have id number, and take some classes. Majoring some subjects and might minor some other subjects.

model Department {
  id       String    @id @default(dbgenerated("uuid_generate_v4()")) @db.Uuid
  name     String    @unique
  students Student[]
  teachers Teacher[]

  createdAt DateTime  @default(dbgenerated("now()"))
  updatedAt DateTime  @default(dbgenerated("now()")) @updatedAt
  deletedAt DateTime?
}

Departments, which consist of students and teachers, also have unique names.

model Course {
  id                 String           @id @default(dbgenerated("uuid_generate_v4()")) @db.Uuid
  name               String
  credit             Int
  courseClasses      CourseClass[]
  courseCategories   CourseCategory[]
  type               CourseType       @default(PUBLIC)
  selectableSubjects Subject[]

  createdAt DateTime  @default(dbgenerated("now()"))
  updatedAt DateTime  @default(dbgenerated("now()")) @updatedAt
  deletedAt DateTime?

  @@index([name])
}

enum CourseType {
  PUBLIC
  MAJOR_LIMITED
}

model CourseCategory {
  id      String   @id @default(dbgenerated("uuid_generate_v4()")) @db.Uuid
  name    String
  courses Course[]

  createdAt DateTime  @default(dbgenerated("now()"))
  updatedAt DateTime  @default(dbgenerated("now()")) @updatedAt
  deletedAt DateTime?
  @@index([name])
}

Courses, which have names, credits and can be divided into many categories, also a same course can have multiple courseClasses, taught by different teachers. Also there can be different types of courses, ones that can be select by everyone and ones that can only be selected by students of certain subjects.

model Subject {
  id          String           @id @default(dbgenerated("uuid_generate_v4()")) @db.Uuid
  name        String           @unique
  courses     Course[]
  students    StudentSubject[]
  departments Department[]
  teachers    Teacher[]

  createdAt DateTime  @default(dbgenerated("now()"))
  updatedAt DateTime  @default(dbgenerated("now()")) @updatedAt
  deletedAt DateTime?
}

model StudentSubject {
  studentId String  @db.Uuid
  subjectId String  @db.Uuid
  student   Student @relation(fields: [studentId], references: [id])
  subject   Subject @relation(fields: [subjectId], references: [id])

  isMajor Boolean @default(true)

  @@id([studentId, subjectId])
}

Subjects, which are chosen by students when enrolled. Multiple teachers can teach same subject. Student can major them or minor them, identified by isMajor column in relation table StudentSubject.

model CourseClass {
  id        String               @id @default(dbgenerated("uuid_generate_v4()")) @db.Uuid
  name      String
  course    Course               @relation(fields: [courseId], references: [id])
  courseId  String               @db.Uuid
  capacity  Int
  time      String
  location  String
  status    CourseClassStatus    @default(NEW)
  teacher   Teacher              @relation(fields: [teacherId], references: [id])
  teacherId String               @db.Uuid
  students  StudentCourseClass[]

  createdAt DateTime  @default(dbgenerated("now()"))
  updatedAt DateTime  @default(dbgenerated("now()")) @updatedAt
  deletedAt DateTime?

  @@index([name])
}

enum CourseClassStatus {
  NEW
  OPEN
  CONFIRMED
  CANCELED
}

CourseClasses, which are instances of classes for a certain course. They should have time, name, location and can have 1 teacher and many students. The number of students it can hold are indicated by capacity and it should have four statuses:

  • NEW means this course class is newly created, should only be visible to admin.
  • OPEN means this course class is open to be selected, all students who met the requirement of course should be able to see it.
  • CONFIRMED means this course class have all the students it needed and will take place in the future.
  • CANCELED means this course class might have too few students, therefore it's canceled. 
model StudentCourseClass {
  student       Student         @relation(fields: [studentId], references: [id])
  studentId     String          @db.Uuid
  courseClass   CourseClass     @relation(fields: [courseClassId], references: [id])
  courseClassId String          @db.Uuid
  status        SelectionStatus @default(SELECTED)
  selectedAt    DateTime        @default(dbgenerated("now()"))

  @@id([studentId, courseClassId])
}

enum SelectionStatus {
  SELECTED
  CANCELED
}

As for the actual course class selection phase, we need a status to indicate the status of the selection to avoid abuse of the system in the form of SELECTED and CANCELED, if student have more than 3 classes canceled at the same day, we might pose some punishment for this particular student.

Business Scenarios

Preparation for course selection

Admin will first need to create new course classes from courses, filling a form about the course classes including name, location, time, capacities of the class, also assign the teacher of this class.

After creation, admin can setup the start end time when all classes are available to be selected, which can be cancelled at any time before the actual selection begins.

Course Selection

At the beginning of the course selection, students would be waiting in the lobby, waiting for course selection begin countdown.

After count down runs out, the page would automatically refresh, loading all course classes that are available to the student.

After click on the pick button, students will be prompted a modal, to see if student is going to confirm selecting this course class.

After student confirms, the course class status in the list would become SELECTED, and capacity would go up by 1.

Student can cancel courses after selection a course class by click on CANCEL button.

After three cancellations in the same day, student would not be able to cancel selection.

Course Selection Finished

After course selection time ends, student would not be able to see course list. But they should be able to see list of course they selected.

Admin should be able to see the overall selection result of each class, including class participants, and can make adjustments on the selection result.

Admin can also cancel course class if the select count is too low.

Key implementation

Preparation for course selection

Things to do before task selection:

  1. Use timed background worker jobs to open up course selection.
  2. Cache warm-up
  3. Random token for course information requests to avoid people from requesting before selection starts
  4. API gateway rate-limit
Setup redis and background jobs

Here we use bull for timed background jobs.

Admin will use UI to set a start, end time for course class selection.

First we store studentCouseClassBegin and studentCouseClassEnd keys with value of start end time into Redis. We then use bull to create a new queue named CoureSelectionQueue, add a task to remove the key from Redis at end time.

When user request for available course list, we check the Redis for studentCouseClassBegin and studentCouseClassEnd, depending on the result, we can have 4 type of response.

  1. No keys, we can return Course selection not available.
  2. Current time < studentCouseClassBegin, return xxx mintues before course selection begins, admin can call cancel option, which would remove both keys from Redis and remove the task from bull queue.
  3. studentCouseClassBegin < Current time < studentCouseClassEnd, we return xxx minutes before course selection ends.
  4. Current time > studentCouseClassEnd , we return Couse selection have ended.
Cache warm-up

Before course selection begins, we need to warm it up to avoid scenarios where too many people are requesting at the same time and due to cache is mostly empty, most of requests would hit our api server and database, causing cache breakdown, cache penetration and even cache avalanche.

To warm-up the the cache, first we need to know what to cache. Based on our database model, we need to:

  1. Get information about course class and teacher by id
  2. Generate a random uuid as token for request.
  3. Use redis-semaphore to generate a distributed semaphore, the key of semaphore is generated token and value is the capacity for a certain course class.

We use hashes to store the information. For each course class, key is course class id, value is nested course class information read from db and the random token in json form.

We also use the same token for key of semaphore we mentioned before and course capacity as its value.

This combo stores all the information we need before querying and actually selecting course classes.

Course Selection

We then need to store the StudentCourseClass information, with key of couseClass Id + studentId value is the selection status.

Select

To prevent malicious request(by bot or script), api would only send out token after course selection begins. Without token, api would invalidate the request instantly. Also the value inside Redis is tightly coupled with token, so api can only find the data within Redis if it has the correct token.

Considering there might be multiple instances of api, we only want data be cached into Redis once, We will need to check if data already exist inside cache as well as adding mutex lock using redis-semaphore.

  1. Student selecting a course, we will need capacha to filter bots and reduce the peak of request count.
  2. After request hits api, there should be a set of request validation, including whether user is authenticated, capacha, random token and if this student have already selected this class.
  3. If request is valid, we use acquire() function to try to reduce the capacity of this course class.
  4. After reduction success, we will need to read and update course information from Redis. Then we need to generate a course selection data, write it to message queue.
Cancel

Basically the same as the select, after request validation, we would just release 1 semaphore based on the token.

Message queue

After request hit the message queue. There's still a lot going on.

We will need one exchange and a queue for rabbitmq, also an api route that listens on the queue. When the route receives message from message queue, it will then update the information to database and then send ack to message queue.

We also needed to ensure the reliability of message queue.

  • Message loss:
    • Message didn't reach broker: before sending message, store message information to Redis, and remove it once we received confirm from broker. Also we need to resend message inside Redis with a maximum of 3 times. If message failed to send for more than 3 times. we need manual intervention.
    • ack didn't reach broker: retry 3 times, then manual intervention.
  • Message duplication: since we have message retries, there could be message duplication. We need to make sure the operation on the receiving api is Idempotent.
  • Message backlog: Using dedicated message queue service, Persist all messages into database and process them later.

Ending

At this point, our high concurrency course selection system has been finished. Under high concurrency, our selection and cancel api only have a few Redis IOs and negligible cost of sending message to message queue. The response time is very short, which is enough to achieve high concurrency.

The main reason for the good performance of this api is due to the asynchronous implementation of the message queue. Database operations that might have taken a long time is replaced by sending a message, which would only take a few milliseconds.

25

Tags:

NodeRedisRabbitmqConcurrency