POC for short ASCII IDs

poc-ascii-id.ts

type ClientParams = { boardID: number; collaboratorID: string };

/**
 * POC of generating short CharIDs per board client. (See the reasoning here: https://miro.atlassian.net/wiki/spaces/PT/pages/3180396935/RFC+Collaborative+Editing+on+Ordered+Sequences#Ways-to-tackle-these-issues%3A)
 *
 * This algorithm respects the _reserved values_ of the total order generator algorithm on the client.
 *
 * - Everytime a client connects to the board we generate a ASCII char ID.
 * - Everytime a client disconnects from the board, we put their char ID in the `free slots` for recycling.
 *
 * This Algorithm guarantees **91** unique single character IDs. (125 - 33 - 2 + 1) (Everything in the range [33, 125], excluding {44, 46})
 * After the limit is reached for single character IDs, it will then add a new element in the sequence.
 * This results in **91^2** 2-byte IDs for boards with over 91 simultaneously connected clients.
 *
 * Connected Users < 92 => 1 byte
 * 
 * Connected Users < 8372 => 2 bytes
 * 
 * Connected Users < 761,943 => 3 bytes
 */
class CollaborativeBoard {
  static MIN = 33;
  static MAX = 126;
  static RESERVED = [44, 46];

  private clientCount = 0;
  private freeSlots: string[] = [];
  private lastCharID: string = String.fromCharCode(CollaborativeBoard.MIN - 1);

  constructor(public readonly id: number) {}

  /**
   * When a new client connects to the board
   * We generate a new Char ID, increase the client count, and update the last used Char ID
   */
  onConnect(): ClientParams {
    const charID = this.getNextCharID();

    this.clientCount++;
    this.lastCharID = charID;

    return { boardID: this.id, collaboratorID: charID };
  }

  /**
   * When a client disconnects from the board, we keep their Char ID in the free slots, for later use.
   * If the disconnected client is the last one on the board, we clear the `freeSlots` array, and reset the `lastCharID` to the default
   */
  onDisconnect(charID: string): void {
    if (this.clientCount === 1) {
      this.freeSlots.length = 0;
      this.lastCharID = String.fromCharCode(CollaborativeBoard.MIN - 1);
    } else {
      this.freeSlots.push(charID);
    }

    this.clientCount--;
  }

  /**
   * Generates a new Char ID using this branching:
   * - There is a free slot available:
   *  - Return the Char ID of the first disconnected client.
   *
   * - If the new Char Code is reserved by the algorithm skip it.
   *
   * - If the new Char Code is less than the MAX:
   *  - Increase the ASCII Code of the last char in the sequence by one
   * - Else:
   *  - If a Char Code in the existing sequence(starting from the beginning) can be increased:
   *    - Increase the ASCII Code of that character in the sequence by one and replace the right hand side with the `MIN` Chars
   *  - Else:
   *    - Return a new sequence with length of `PREVIOUS_LENGTH + 1` with repeated `MIN` chars
   *
   *
   * ## Example 1: The Default Behaviour
   *
   * - Free Slots = []
   * - Connected Clients: 0
   * - Last Returned Char ID = DEFAULT
   *
   * ```typescript
   * const board = new CollaborativeBoard(1)
   * const {collaboratorID} = board.onConnect() // collaboratorID = '!' (char code = 33)
   * ```
   *
   * ## Example 2: Skipping Reserved Chars (44 and 46)
   *
   * - Free Slots = []
   * - Last Returned Char ID = '+' (char code = 43)
   *
   * ```typescript
   * const {collaboratorID: id_1} = board.onConnect() // collaboratorID = '-' (char code = 45)
   * const {collaboratorID: id_2} = board.onConnect() // collaboratorID = '/' (char code = 47)
   * ```
   *
   * ## Example 3.1: Respecting `MAX` values
   *
   * - Free Slots = []
   * - Last Returned Char ID = "}" (char code = 125)
   *
   * ```typescript
   * const {collaboratorID} = board.onConnect() // collaboratorID = "!!" (char code = [33, 33])
   * ```
   *
   * ## Example 3.2: Not increasing sequence length while respecting `MAX` values
   *
   * - Free Slots = []
   * - Last Returned Char ID = "!}" (char code = [33, 125])
   *
   * ```typescript
   *  const {collaboratorID} = board.onConnect() // collaboratorID = '"!' (char code [34, 33])
   * ```
   *
   * ## Example 4. Using available free slots instead of incrementing the char counter.
   *
   * 50 Clients connect to the board, receive a Char ID, then disconnect from the board.
   * Then 2 clients connect to the board without disconnecting.
   * The resulting Char IDs for those clients will be `'!'`(char code = 33) and `'"'`(char code = 34)
   *
   * ```typescript
   * const results: string[] = []
   *
   * for (let i = 1; i < 103; i++) {
   *   if (i <= 100 && i % 2 === 0) {
   *    board.onDisconnect(results.shift()!)
   *   } else {
   *	  const {collaboratorID} = board.onConnect()
   *    results.push(collaboratorID)
   *  }
   * }
   * ```
   */
  private getNextCharID(): string {
    if (this.freeSlots.length) {
      return this.freeSlots.shift()!;
    }

    let lastCharCode = this.lastCharID.charCodeAt(this.lastCharID.length - 1);

    if (CollaborativeBoard.RESERVED.includes(lastCharCode + 1)) {
      lastCharCode++;
    }

    if (lastCharCode + 1 >= CollaborativeBoard.MAX) {
      const indexToIncrease = this.lastCharID
        .split("")
        .findIndex((c) => c.charCodeAt(0) + 1 < CollaborativeBoard.MAX);

      if (indexToIncrease === -1) {
        return String.fromCharCode(CollaborativeBoard.MIN).repeat(
          this.lastCharID.length + 1
        );
      }

      return (
        this.lastCharID.substring(0, indexToIncrease) +
        String.fromCharCode(
          this.lastCharID[indexToIncrease].charCodeAt(0) + 1
        ) +
        String.fromCharCode(CollaborativeBoard.MIN).repeat(
          this.lastCharID.length - indexToIncrease - 1
        )
      );
    }

    return (
      this.lastCharID.substring(0, this.lastCharID.length - 1) +
      String.fromCharCode(lastCharCode + 1)
    );
  }
}

// Tests

// The Default Behaviour
let board = new CollaborativeBoard(1);
let id = board.onConnect().collaboratorID;
console.assert("!" === id, 'Incorrect collaboratorID: %s, Expected "!"', id); // '!'

// Skipping Reserved Chars
board = new CollaborativeBoard(2);
for (let i = 0; i < 11; i++) {
  board.onConnect();
}
id = board.onConnect().collaboratorID;
console.assert("-" === id, 'Incorrect collaboratorID: %s, Expected "-"', id); // '-'

// Respecting `MAX` values
board = new CollaborativeBoard(3.1);
for (let i = 0; i < 91; i++) {
  board.onConnect();
}
id = board.onConnect().collaboratorID;
console.assert("!!" === id, 'Incorrect collaboratorID: %s, Expected "!!"', id); // '-'

// Not increasaing sequence length while respecting `MAX` values
board = new CollaborativeBoard(3.2);
for (let i = 0; i < 182; i++) {
  board.onConnect();
}
id = board.onConnect().collaboratorID;
console.assert('"!' === id, 'Incorrect collaboratorID: %s, Expected ""!"', id);

// Using available free slots instead of incrementing the char counter
board = new CollaborativeBoard(4);
const results: string[] = [];

for (let i = 1; i < 103; i++) {
  if (i <= 100 && i % 2 === 0) {
    board.onDisconnect(results.pop()!);
  } else {
    const { collaboratorID } = board.onConnect();
    results.push(collaboratorID);
  }
}

console.assert(
  results[0] == "!" && results[1] == '"',
  'Incorrect collaboratorIDs %s, Expected "!"',
  results.join("")
);

export {};