Notes
Requirements
Fix the scope. A user asks a question with one to five tags. Others answer, and anyone can comment on a question or an answer. Users vote up or down, but only once per post, and they can change or take back that vote. Votes and accepted answers change reputation, and reputation unlocks privileges. The asker accepts one answer. Questions are searchable by tag, and followers are notified when something happens.
Ask the questions that change the code. Can you vote on your own post? No. What happens if you click the same vote twice? It undoes it. Can the asker change which answer is accepted? Yes, and the bonus moves with it. Can reputation go below one? We show a floor of one, but keep the exact sum underneath. Full text search, edit history, moderation queues and badges are out of scope for now.
- ask a question with 1 to 5 tags
- answer a question
- comment on any post
- upvote or downvote a post
- one vote per user per post
- change it or undo it
- reputation from votes, accepts
- privileges unlock with rep
- asker accepts one answer
- search questions by tag
- notify followers of activity
- vote on your own post?
- no
- click the same vote twice?
- it undoes the vote
- can the asker change accept?
- yes, the bonus moves
- reputation below one?
- shown as one, sum kept exact
- out of scope: full text search,
- edits history, moderation,
- bounties, badges
Entities
Underline the nouns: user, question, answer, comment, tag, vote. The key modelling move is to notice that questions and answers behave the same way for voting and comments. So both extend an abstract Post that holds the author, the body, the score, the vote ledger and the comments. A question adds a title, tags, a list of answers and the accepted answer. An answer points back to its question. A comment is a small record, and it has no votes in this version.
Class diagram
Here is the shape. Post is abstract and owns everything voting needs: an atomic score and a vote ledger, which is a concurrent map from user id to up or down. Question and Answer extend it and add their own fields. The type method tells the reputation rules whether a vote was on a question or an answer. Because one map entry exists per voter, the rule of one vote per user per post is true by construction, not by a check you might forget.
abstract class Post {
final long id; final User author;
final AtomicInteger score;
final ConcurrentHashMap<Long, VoteType>
votes; // userId to vote
final List<Comment> comments;
abstract PostType type();
}
class Question extends Post {..tags..}
class Answer extends Post {..question..} Privileges
Privileges are just data. An enum lists each power with its minimum reputation, and the user has one method, can, that compares. These numbers are an example we made up for this lesson: ten to upvote, twenty to comment on other people's posts, fifty to downvote. Commenting on your own question, or on answers to it, is always allowed. Adding a new privilege is one enum line plus one check where the action happens.
enum Privilege {
UPVOTE(10), COMMENT_ANYWHERE(20),
DOWNVOTE(50), EDIT_ANY_POST(500);
}
boolean can(Privilege p) {
return reputation() >= p.minReputation;
}
numbers are an example for this
lesson, not any real site Strategy: reputation
Reputation rules change over time, so they live behind a ReputationRules interface: the Strategy pattern. Our example rules are simple round numbers. An upvote gives the author five on a question and ten on an answer. A downvote costs the author two, and downvoting an answer also costs the voter one, so downvotes are not free. An accepted answer earns fifteen, and the asker gets two for accepting. A different community just plugs in a different rules class.
- upvote on a question: author +5
- upvote on an answer: author +10
- any downvote: author -2
- downvote an answer: voter -1
- answer accepted: author +15
- asker who accepts: +2
- self-accept earns nothing
- shown reputation floor: 1
Flow: vote
Walk the vote flow. Reject a vote on your own post, and check the privilege for up or down. Then one atomic compute on the ledger decides the new state: if the old vote equals the wanted one, remove it, which is an undo; otherwise store the wanted vote. We remember what was there before. Finally take back the effect of the old vote and add the effect of the new one, to the score and to both reputations.
reject own post, check privilege
VoteType[] before = new VoteType[1];
after = votes.compute(userId, (k, old) -> {
before[0] = old;
return old == wanted ? null : wanted;
});
apply(post, voter, before[0], -1);
apply(post, voter, after, +1);
return after; // null: no vote now Change and undo
This one rule handles every case, which is why it is worth showing. A first vote only adds. An undo only removes. A switch from down to up removes the down, giving back two points to the author and one to the voter, and then adds the up, ten more. Clicking up again removes it. The demo checks that after this dance the score and both reputations are back exactly where they started. No special case code for switching at all.
- none to UP: add UP
- UP to none: remove UP (undo)
- DOWN to UP: remove DOWN, add UP
- reviewer switches on a2:
- remove DOWN: author +2,
- voter +1
- add UP: author +10
- click UP again: author -10
- net result: exactly zero
Flow: accept
Accepting an answer. Only the asker may do it. The question holds the accepted answer in an atomic reference, and get-and-set swaps it in one step and hands back the previous one. If it was the same answer, nothing to do. If another answer was accepted before, take its fifteen points away, then give fifteen to the new one, unless the asker answered their own question. The asker's two point bonus is paid only the first time.
if (q.author.id != userId) throw prev = q.accepted.getAndSet(a); if (prev == a) return; if (prev != null) prev author -15 a author +15 // unless self-answer if (prev == null) asker +2 notify a.author: accepted
Search by tag
Search by tag uses an inverted index: a concurrent map from each tag to the set of question ids that carry it. Tags are lower-cased on the way in, so Java and java are the same tag. For several tags, sort the sets by size, walk the smallest one, and keep ids found in every other set. Results are sorted by score, highest first, then oldest first. Full text search over titles and bodies is a separate search engine, and we say so.
Map<String, Set<Long>> questionsByTag
java -> {q1, q3}
concurrency -> {q1}
sort the sets by size
walk the smallest, keep ids in all
sort: score high to low, then oldest
tags lower-cased on the way in Observer: notifications
Notifications use the Observer pattern. Each question keeps a set of followers, and the asker follows automatically. When an answer arrives, the site publishes a new answer event for every follower except the person who answered. Comments notify the post's author, and accepts notify the answerer. The site never knows whether a listener writes to an in-app inbox, sends an email or a push message. Adding a channel is one more listener.
enum EventType { NEW_ANSWER,
NEW_COMMENT, ANSWER_ACCEPTED }
record Event(type, recipientId, msg)
interface SiteListener {
void onEvent(Event e);
}
listeners: CopyOnWriteArrayList
Inbox, EmailSender, PushSender:
each is just one more listener Concurrency
Now concurrency. A user double clicks, and two requests arrive together. With a naive check then put, both see no vote and the score goes up by two from one person. Instead, the ledger's compute method runs atomically for each key, so the second click sees the first one's result and undoes it. Score and reputation change with atomic adds, and since additions can happen in any order, the totals always match the ledger.
Give every shared field a safe home. The ledger is a concurrent map updated with compute. Score and reputation are atomic integers. The accepted answer is an atomic reference, swapped with get and set. The tag index uses concurrent key sets. Answers, comments and listeners are copy-on-write lists, because they are read far more often than written. Ids come from an atomic counter. There is no global lock, so one busy question never slows down another.
The demo proves it under load. Three hundred voters upvote one answer from eight threads, and the score is exactly three hundred. Then every voter switches to a downvote while half of them also undo it, and at the same time one user clicks up four thousand times from four threads. Each click toggles, so that user ends with no vote. The score equals the ledger sum, minus one hundred and fifty, and the author's reputation change is exactly what the rules predict.
- naive: if (!votes.contains(u))
- votes.put(u, UP); score++
- two clicks both see no vote:
- score +2 from one user
- fix: votes.compute(u, ...)
- runs one at a time per key
- score and reputation: atomic
- adds, and adds commute
- vote ledger: ConcurrentHashMap
- compute() per post and user
- score, reputation: AtomicInteger
- accepted answer: AtomicReference
- getAndSet moves the bonus
- tag index: concurrent key sets
- answers, comments, listeners:
- CopyOnWriteArrayList
- ids: AtomicLong
- no global lock anywhere
- 300 voters upvote one answer
- on 8 threads: score 300
- then all switch to down,
- and even ones undo it
- one user clicks UP 4000 times
- from 4 threads: ends with none
- score -150 = ledger sum -150
- author change -300, exactly
Extensibility
Interviewers will add features. Votes on comments? Pull the voting part into a Votable interface that both posts and comments implement. Bounties? A bounty object on the question, paid out on accept through the rules. Badges? Another listener that counts events per user, so the core never changes. Edit history? A list of revisions, gated by the edit privilege. Closing a question as a duplicate? A small state enum on the question.
- votes on comments: Comment
- becomes a Post-like Votable
- bounties: a Bounty on a question
- paid on accept, a rules event
- badges: one more listener
- counting events per user
- edit history: Revision list,
- needs EDIT_ANY_POST
- close / duplicate: a state enum
- on Question (State pattern)
Testing
The full code is below the player. The demo registers four users, asks three questions and posts two answers. It shows a new user blocked from upvoting, a self vote rejected, a vote that is switched and then undone with exact numbers, an accept that moves back and forth, a comment blocked by low reputation, tag search with one and two tags, and the concurrent vote race. Each step checks its numbers, so a mistake fails loudly.
Rejected: new_dev needs 10 reputation
to upvote
Rejected: cannot vote on your own post
Same vote again undoes it: score 0
Accepted a1: java_helper(26), new_dev(8)
Rejected: quick_fixer needs 20
reputation to comment here
Tag java: [HashMap question [1],
size question [0]]
Concurrent: score -150, ledger -150 Follow-ups
Expect follow-ups. At scale, the ledger moves to a database table with a unique key on post and user, so the database also enforces one vote. A very hot post can keep its counter in several shards that are summed when read. If the rules change, recompute reputation by replaying the stored vote and accept events. Fraud, like one account voting for a friend again and again, is detected later and those votes are reversed with the same undo path.
- millions of votes per hour?
- ledger in a DB, unique
- key on post and user
- hot question: shard counters
- recompute reputation?
- replay the event log
- serial voting fraud?
- detect and reverse votes
- sort by hot: score with
- time decay, precomputed
Say it like this
The short version to say out loud. Question and Answer extend Post, which owns the score, the votes and the comments. Votes live in a map from user to vote, changed with one atomic compute, then we subtract the old effect and add the new one, which covers new votes, switches and undos. Points come from a rules strategy, powers from a privilege enum, and notifications go to observers.
- "Question and Answer extend Post,
- which owns score, votes and
- comments. Votes live in a map of
- user to vote, changed with an
- atomic compute: subtract the old
- effect, add the new. Points come
- from a rules Strategy, powers
- from a Privilege enum, and
- notifications are observers."