Question: Design User System

For example: Twitter Login

User Case

• Register/Update/Remove
• Login/Logout
• Balance/Membership

Necessary - Register

• Current Total User: 100,000,000
• Current Daily active users: 1,000,000
• Predict
  • Daily active users in three months = 1,000,000*2 = 2,000,000
  • Register Percentage = 1%
  • Daily new register users = 2,000,000*1% = 20,000

Necessary - Login

• Predict
  • Login percentage = 15%
  • Average login time = 1.2, concerning login failure/ login<-->logout
  • Daily login time = 2,000,000 * 15% * 1.2 = 360,000
  • Average Login Frequency = 360,000 / 24 hour = 1,800,000/24/60/60 = 4.2/s
  • Normal Login frequency = 4.2 * 2 8.4/s
  • Peak Login Frequency = 8.4 * 5 = 42/s

Application

Data - User(V1)

protocol User {
    private var userID: Int // Primary Key Int64
    private var name: String
    private var password: String
}

Data - User Tble(V1)

//column: UserID Name Password
protocol UserTable {
    private var table: Array<User>

    public func insert(...) -> ...
    public func delete(...) -> ...
    public func update(...) -> ...
    public func select(...) -> ...
}

Question: Support user management such as verification and ban

State Lifecycle Graph(V1)

New User -> Register action -> Active state -> Remove action

State Lifecycle Graph(V2)

• User Verification - what if bot register user

New User -> Register Action -> Unverified State User -> Approve Action-> Active State User

New User -> Register Action -> Unverified State User -> Reject Action -> Delete/Waiting for timeout to Delete(will not add it into user system)

• User Ban/Active - what if user/admin want to ban or make Account in private

Active State User -> Ban Action -> Banned state user (admin action)

Banned state User -> Unban action -> Active User (admin action)

Active User -> Deactivate state-> Inactive state (user action)

• Remove

Unverified State User -> Reject Action -> Delete/Waiting for timeout to Delete(will not add it into user system)

Banned state User -> Remove action -> Delete/Fake Delete showing "User Canceled"

Inactive state User -> Remove action -> Delete/Fake Delete showing "User Canceled"

Data - User(V2)

protocol User {
    private var userID: Int // primary key Int64
    private var name: String // constant size
    private var hiddenPassword: String // constant size, one-way hashing with salts
    private var state: Int
}

Session

• Session is a conversation between a user and a server
• A user will have multiple sessions when user logins form different devices at the same time
• You should as least remember your sessionID
• Has service has session, even if does not login

Session LifeCycle graph(V1)

Offline state User -> Login action -> Online state user -> Logout state -> Offline user

Online state User -> timeout -> Offline state User

Data - User(V3)

protocol User {
    private var userID: Int // primary key Int64
    private var name: String // constant size
    private var hiddenPassword: String // constant size, one-way hashing with salts
    private var state: Int
    private var sessionList: Array<Session>
}

protocol Session {
    private var sessionID: Int
    private var userID: Int
    private var deviceCode: Int
    private var timeOut: Date
}

Problems: So separate UserTable/SessionTable

• What if unlogin user? Generate 100W unnamed random user, once unlogin user addin, pair a random user to unlogin user
• We update sessionList more frequently
• The size of sessionList is dynamic

Data - UserTable and SessionTable(V4)

protocol User {
    private var userID: Int // primary key Int64
    private var name: String // constant size
    private var hiddenPassword: String // constant size, one-way hashing with salts
    private var state: Int
}

// column: UserID Name Password
protocol UserTable {
    private var table: Array<User>

    public func insert(...) -> ...
    public func delete(...) -> ...
    public func update(...) -> ...
    public func select(...) -> ...
}

protocol Session {
    private var sessionID: Int // primary key Int64
    private var userID: Int // Foreign Key
    private var deviceCode: Int
    private var timeOut: Date
}

// session table
protocol SessionTable {
    private var table: Array<Session>

    public func insert(...) -> ...
    public func delete(...) -> ...
    public func update(...) -> ...
    public func select(...) -> ...
}

Question: How to implement remember me

• Setting the timeout in Session

Question: How optimize SessionTable

• save SessionTable in Memory. Even if memory loses all, just re-login
• no need to check the timeout frequenly.
  • When the user login, first check whether the session is expired. If so, update timeout.
  • Or delete timeout session once per day

Question: Query userID = 11?

• index with hash O(1): add - private var hashValue:Int

Question: Range query userID < 30?

• Index with Binary Search Tree,
  • space O(n)
  • insert O(lg2N)
• • delete O(lg2N)
  • lookup O(lg2N)
  • range query O(lg2(N+K)), binary search find, then inorder traversal
• B+Tree,
  • space O(n)
  • insert O(lgbN)
  • delete O(lgbN)
  • lookup O(lgbN)
  • query O(lognb(N+K))
  • Advantages: disk friendly with continuous reading

Question: Payment with membership

class Membership {
    private var userID: Int
    private var money: Double
    private var expirationTime: Date

    public func addMoney(...) -> ...
    public func buyMmeber(...) -> ...
}

Problems

• data inconsistence, system down after money paid, before expirationTime add
  • Solution: add transaction with log. Wite log first then perform operation
• dup Member with the same userID / shadow User, userID not valid
  • add checker

typealias CheckFunction = ()->()
class Checker {
    private var checkList: Array<CheckFunction>
    public func register(checkFunction: CheckFunction) -> Bool
}

Checker checker;
checker.register(checkUnknownUser)
checker.register(checkDuplicatedUser)

• user buy seversal times shortly
  • thread-safe problem
  • lock when transaction processing

ACID Principle ~ too strict

• Atomicity - all or nothing
• Consistency, valid according to all defined rules
• Isolation, a kind of independency between transactions
• Durability, stored permanently

Question: Design PayPal

start from Scenario

• send/reveive
• add money/ get cash
• transfer/payment

AddMoney

• calculate QPS
• addMoney LifeCycle Graph

New Order -> Verification -> success/fail

• data structure
  • UserTable
  • OrderTable

protocol User {
    private var userID: Int
}

protocol Account {
    private var accountID: Int
    private var userID: Int
    private var bankID: Int
    private var routingNumber: String
    private var dayLimit: Int
}

protocol Order {
    private var orderID: Int // primary Key
    private var userID: Int // foreign Key
    private var accountID: Int
    private var amount: Int
    private var operation: Int
    private var state: Int
    private var createTime: Date
    private var expirationTime: Date
}

Question: If succeed, process?

• log at first, view of dataflow
• lock transaction -> log -> load user data -> update -> unlock transaction -> submit -> notification