dylansp/miscd

A distributed, sharded key-value store for learning how to build distributed systems.

miscd's Issues

Implement sharding

Notes on REST API design

REST endpoints for clients:

• All under /api
• Key-value API under /api/kv
• Locks:
  • Could be in a separate namespace altogether, under /api/locks)
  • Could be separate routes under /api/kv, such as /api/kv/locks or /api/kv/:keyID/lock
  • Could be parameters used in the key-value API instead of separate routes, where a client could optionally lock a key as part of another request

If I use REST for Raft intra-cluster communication:

• Possibly run on a different port
• See #3 for notes on authentication
• All internal communication would go under /raft
• GET /raft/status - debugging, returns node state, any other metadata I want
• POST /raft/entries - AppendEntries RPC
• POST /raft/poll - RequestVote RPC

Implement log compaction

See section 7 of the Raft paper.

Build web-based visualizer

Should show Raft cluster state, provide key-value interface.

Notes for how to build a key-value store on top of a Raft cluster

https://notes.eatonphil.com/2023-05-25-raft.html

Lock down Raft routes to intra-cluster messaging only

Right now, the routes for Raft RPCS are planned to be publicly exposed, which is an obvious safety/security flaw. They should be locked down to only allow communication from other nodes in the cluster.

Note: this should only affect the endpoints for the RequestVote and AppendEntries RPCs. Information-only status endpoints should be publicly exposed.

Notes for how to use Raft as part of a larger datastore

https://notes.eatonphil.com/distributed-postgres.html

Fundamental ideas of the post/the linked hashicorp Raft library:

• Have an interface (FSM) that consumers of the Raft library should implement, providing an Apply() operation for applying a log entry to the local state machine (and optionally, Snapshot() and Restore() for optimization).
• Raft library exposes a function (NewRaft()) that takes an FSM implementation and a locally-determined (but globally-unique) server ID, and returns a local Raft instance.
• This Raft instance can be passed info on other remote nodes (their server ID and how to contact them) to add them to the Raft cluster.
• This Raft instance has an Apply() method (note - distinct from the FSM Apply() method) that takes application data as a byte array (opaque to the Raft library), and attempts to apply it to the Raft cluster's distributed log.
  • The Hashicorp implementation of this fails if the local node isn't the leader; the local node's state (leader/candidate/follower) should be checked first - see this example of usage in https://github.com/otoolep/hraftd. I think in this project, the ideal behavior of a miscd instance would be to redirect the API client to the last-known leader.

Other notes:

• An API client needs to know the addresses of all nodes. Per the Raft paper, section 8 ("Client interaction"):
  • "When a client first starts up, it connects to a randomly chosen server."
  • "If the client’s first choice is not the leader, that server will reject the client’s request and supply information about the most recent leader it has heard from."
  • "If the leader crashes, client requests will time out; clients then try again with randomly-chosen servers." (My note - this probably applies if the redirects from followers to last-known-leaders never lead to a valid leader)
• Executing read-only requests locally without forwarding to a leader can return stale data; even running them on a leader without appending anything to the log can have the same problem. The Raft paper seems to recommend solving this by having the leader run a blank AppendEntry command on read requests, only returning the data if that commits. See discussion at end of section 8.

Test with Jepsen library

https://github.com/jepsen-io/maelstrom for general testing

https://github.com/jepsen-io/etcd for etcd-specific stuff, if I implement that API

Implement persistent storage

v1 will store data purely in memory, causing data to be lost on restarts. Some later version should store data in local persistent storage, probably as a SQLite database.