fib

Fibonacci

Prerequisites

Please design and implement a web based API that steps through the Fibonacci sequence.

The API must expose 3 endpoints that can be called via HTTP requests:

• current - returns the current number in the sequence
• next - returns the next number in the sequence
• previous - returns the previous number in the sequence

Example:

current -> 0
next -> 1
next -> 1
next -> 2
previous -> 1

Requirements:

• The API must be able to handle high throughput (~1k requests per second)
• The API should also be able to recover and restart if it unexpectedly crashes
• Use Go and any framework of your choice for the backend
• The submission should be sent in a GitHub repo

How you are doing the fibonacci?

Well, well.. here goes the story.. The whole strategy that I used is inspired from dynamic programming technique. Basically I combined this idea from here and here <- coincidentally or not they have a perfect example in the official go doc, found it when I was searching how to handle big numbers (more than 64 bits).

Based on those findings I just basically always stored (per client) the last fn-1 and fn-2 so it's easy for me to compose the next number. For previous I did the operations in reverse order.

So every client has it's on fib sequence generator, I thought there's no reason for a client to interfere to another client sequence generator, so we have a cache of caches if it makes sense.

Drawbacks to this approach is that I didn't take into consideration this. Which might be a valid way of going prev indefinitely into the sequence −8, 5, −3, 2, −1, 1, 0, 1, 1, 2, 3, 5, 8, Imagine, your current point is 0 and then you prev two time, you should get -1. Right now if current is 0 it will just return 0 on prev op.

How to run the service?

By go install, this will install and source it so it's available in bash everywhere if you sourced your $(go env GOPATH)/bin dir.

go install -v github.com/hoenirvili/fib/cmd/fib@latest

Or by just downloading the repo and running make

git clone https://github.com/hoenirvili/fib
make build
./fib -debug # if you want to run the service in debug mode

Tests

Nothing special, just go tests that can be run with this above command. I'm using testify in order to assert our tests. I could've used the standard library, but I'm accustomed to use this library, no other reasons.

go test -v ./...

Performance

We benchmark the service by using the wrk tool. If you don't have it in your system you can install it on mac with

brew install wrk

In wrk we have a feature to customize our benchmarking strategy. It didn't made any sense to benchmark just one endpoint individually, so I'm using this naive strategy to randomly select one endpoint at a time.

cat random.lua

paths = { "/next", "/pevious", "/current" }
wrk.path = paths[math.random(0, 3)]

Basically above I'm defining a lua table containing all path endpoints and randomly select it for a wrk execution.

The whole script execution is like this, basically we invoke wrk with 12 threads simulating 400 clients and the benchmark time length to be 120s.

wrk -t12 -c400 -d120s -s ./random.lua --latency http://127.0.0.1:8080

Running 2m test @ http://127.0.0.1:8080
  12 threads and 400 connections
  Thread Stats   Avg      Stdev     Max   +/- Stdev
    Latency    10.67ms   15.64ms 230.89ms   84.83%
    Req/Sec     2.71k     1.10k    7.17k    63.57%
  Latency Distribution
     50%    1.45ms
     75%   18.51ms
     90%   31.52ms
     99%   66.17ms
  3889339 requests in 2.00m, 19.49GB read
  Socket errors: connect 155, read 107, write 0, timeout 0
Requests/sec:  32386.02
Transfer/sec:    166.23MB

On my m1 macbook pro I'm getting 32k requests per second which is decent I suppose for this challenge.

How do you handle recovery?

Nothing special really, I just created a new Ticker which every 2 seconds it will flush all the internal caches into a file.

When the service starts again it will try to load the cache from file.