4 ms·

Just playing, but "If you have n servers that take requests, and server Sᵢ can take a request every tᵢ seconds, and you need to distribute requests to them as e

Just playing, but "If you have n servers that take requests, and server Sᵢ can take a request every tᵢ seconds, and you need to distribute requests to them as efficiently as possible, how do you do it?" can be done very easily in Go. You have a shared channel which contains the pending requests, and a goroutine per server that simply loops doing: read from the shared channel, perform the request, wait for the sleep period, and continue the loop. And that's all. Each server will get requests as fast as it can consume them.

jnbiche 13y ago
Wow, I've really got to look into Go. Sounds so easy.
- eropple 13y ago
  What he's described is pretty trivially done in most modern languages/frameworks. I can write the same in C#, Scala or C++11--swapping greenlets for standard threads, which honestly is unlikely to be a perf concern--pretty trivially. The hardest of the above would be C++, because boost::threadpool isn't officially part of Boost--though it works fine--and otherwise you'd have to get a little creative with boost::thread_group (but in doing so it'd probably be only slightly more complex than the Go version). I mean, it's a nice feature, albeit bolted to a language with a lot of issues. But unless you have pressing reasons to look at Go, something like that sounding easy probably won't really trip your trigger. =)
  - millstone 13y ago
    You don’t need a thread pool or threads at all. Just schedule a timer for each server. You could do it in JavaScript. I’d even guess that a JavaScript implementation would be more efficient than Go. A goroutine has an overhead measured in kilobytes; a JavaScript timer is presumably smaller.
  - jnbiche 13y ago
    Yeah, I realize you can accomplish the same result in almost any language, but not nearly as easily. It's the syntactic sugar that impressed me, and the fact that's it's such an integral part of the language.
ajross 13y ago
Not to throw water on your thought process, but the abstraction you describe is hardly unique to Go. It's called a "semaphore", and has been pretty well described and implemented for several decades now.
eterm 13y ago
Yes, but how does Go do it. Google is probably more interested in hiring people who can answer that rather than your answer. "There's a library for that" is a great answer for 99.9% of businesses out there, but google's problems aren't that of the 99.9%. (Nor in fact are they in the 99.9% of the remaining 0.1%)
- AaronFriel 13y ago
  Although I don't work at Google, I feel like this just patently is not the case. I firmly believe the vast majority of devs at Google aren't writing the next massive distributed and concurrent datastore with strong guarantees on transaction sequencing, aka F1 on top of Spanner. The vast majority of people aren't writing the things that get, or would get if they were publicly available, research papers at Google. They're using those things, written by the 1% of the 1%, to do things really, really generic, like display advertisements or store emails. There are some people in language development (Dart, Go, probably some others and some DSLs), there are some people doing hardcore database design, they probably have some people working on hard problems in their datacenters, from reducing latency on commodity hardware to networking infrastructure. Are the majority of Google employees writing things that only the 0.1% of the 0.1% can solve? No, they don't even employ enough software engineers for that to be the case.
  - jrockway 13y ago
    I'm pretty sure that storing emails or displaying ads is not nearly as generic or as easy as you think. My justification for asking algorithmic interview questions is because I believe that engineers using libraries should understand exactly how they work, so they know what design compromises the implementation chose and how that affects their higher-level application. Just because you aren't going to be writing a database doesn't mean you shouldn't know the various levels of transaction isolation that exist.
nostrademons 13y ago
And that solution is isomorphic to the one the interviewer was looking for, where you put the requests in a priority queue keyed by their finish time and pull out the next one that'll be done. The only difference is that the priority queue in question is hidden in Go's scheduler. The reason interviewers ask these questions is so they get a sense of whether you'd be able to implement Go, starting from first principles. (Or actually, it's because before Go many servers and load-balancers were written in C++ using async callbacks, and so this is a very pragmatic question that comes up a lot in real-world usage.)
- JulianMorrison 13y ago
  It's isomorphic and better, because each goroutine performs a synchronous and easily understood acquire-perform-sleep looping operation with no hairy coordination. And even underneath, it's somewhat simpler, because neither Go nor the design I gave cares which of the runnable goroutines (the servers that have finished their work) takes the next request off the channel. Plus the blocking behaviour of channels gives you implicit backpressure if the requests are coming in too fast - the process putting them on the channel will stall.
  - cookingrobot 13y ago
    You probably should care which server gets the request. It's not explicitly said, but if one server can handle twice as many requests per second, then it might be completing each request faster. If that's the case, it's a better service to give more requests to the faster servers. Worth at least discussing to see if there are other aspects to the problem.
rybosome 13y ago
That's an easy solution in any language, frankly; have a shared queue of the requests, and the servers simply pull from the queue whenever they aren't processing a request. I'm sure that this is easier to implement in Go than a lot of other languages, but I think this actually defeats the purpose of the question. The hard part of the question is how to assign work to the servers rather than letting the servers pick the work themselves.
- JulianMorrison 13y ago
  Yeah, I just picked Go because it's one I know well and it's a 5 second solution that handles the question as asked. It would be just as easy to do in ruby for example, with EM::Queue. I actually intended this as a way to "assign work" rather than having the servers pull. Each goroutine "owns" a server and forwards all requests to it, but it's just part of the one load balancer process, and the load balancer does nothing but balance. IMO, defeating the purpose of a question is how you solve problems in real life. Now if you wanted a harder question, you could follow that with: OK, that solution will give the servers time to do their thing, but there's no guarantee it won't just end up dumping all the load on a few servers, straining infrastructure and under-using the other machines, because there's no guarantee Go's scheduler is fair. So please develop two competing solutions. First, a fair scheduler that spreads the load evenly. Second, as an alternative, an unfair scheduler that always fills 100% of the time on the first machine before moving on to the second, and so on, and reports how many machines it's using so we can take the others out of the pool and repurpose them.

jnbiche 13y ago

Wow, I've really got to look into Go. Sounds so easy.

eropple 13y ago
What he's described is pretty trivially done in most modern languages/frameworks. I can write the same in C#, Scala or C++11--swapping greenlets for standard threads, which honestly is unlikely to be a perf concern--pretty trivially. The hardest of the above would be C++, because boost::threadpool isn't officially part of Boost--though it works fine--and otherwise you'd have to get a little creative with boost::thread_group (but in doing so it'd probably be only slightly more complex than the Go version). I mean, it's a nice feature, albeit bolted to a language with a lot of issues. But unless you have pressing reasons to look at Go, something like that sounding easy probably won't really trip your trigger. =)
- millstone 13y ago
  You don’t need a thread pool or threads at all. Just schedule a timer for each server. You could do it in JavaScript. I’d even guess that a JavaScript implementation would be more efficient than Go. A goroutine has an overhead measured in kilobytes; a JavaScript timer is presumably smaller.
- jnbiche 13y ago
  Yeah, I realize you can accomplish the same result in almost any language, but not nearly as easily. It's the syntactic sugar that impressed me, and the fact that's it's such an integral part of the language.

ajross 13y ago

Not to throw water on your thought process, but the abstraction you describe is hardly unique to Go. It's called a "semaphore", and has been pretty well described and implemented for several decades now.

eterm 13y ago

Yes, but how does Go do it. Google is probably more interested in hiring people who can answer that rather than your answer. "There's a library for that" is a great answer for 99.9% of businesses out there, but google's problems aren't that of the 99.9%. (Nor in fact are they in the 99.9% of the remaining 0.1%)

AaronFriel 13y ago
Although I don't work at Google, I feel like this just patently is not the case. I firmly believe the vast majority of devs at Google aren't writing the next massive distributed and concurrent datastore with strong guarantees on transaction sequencing, aka F1 on top of Spanner. The vast majority of people aren't writing the things that get, or would get if they were publicly available, research papers at Google. They're using those things, written by the 1% of the 1%, to do things really, really generic, like display advertisements or store emails. There are some people in language development (Dart, Go, probably some others and some DSLs), there are some people doing hardcore database design, they probably have some people working on hard problems in their datacenters, from reducing latency on commodity hardware to networking infrastructure. Are the majority of Google employees writing things that only the 0.1% of the 0.1% can solve? No, they don't even employ enough software engineers for that to be the case.
- jrockway 13y ago
  I'm pretty sure that storing emails or displaying ads is not nearly as generic or as easy as you think. My justification for asking algorithmic interview questions is because I believe that engineers using libraries should understand exactly how they work, so they know what design compromises the implementation chose and how that affects their higher-level application. Just because you aren't going to be writing a database doesn't mean you shouldn't know the various levels of transaction isolation that exist.

nostrademons 13y ago

And that solution is isomorphic to the one the interviewer was looking for, where you put the requests in a priority queue keyed by their finish time and pull out the next one that'll be done. The only difference is that the priority queue in question is hidden in Go's scheduler. The reason interviewers ask these questions is so they get a sense of whether you'd be able to implement Go, starting from first principles. (Or actually, it's because before Go many servers and load-balancers were written in C++ using async callbacks, and so this is a very pragmatic question that comes up a lot in real-world usage.)

JulianMorrison 13y ago
It's isomorphic and better, because each goroutine performs a synchronous and easily understood acquire-perform-sleep looping operation with no hairy coordination. And even underneath, it's somewhat simpler, because neither Go nor the design I gave cares which of the runnable goroutines (the servers that have finished their work) takes the next request off the channel. Plus the blocking behaviour of channels gives you implicit backpressure if the requests are coming in too fast - the process putting them on the channel will stall.
- cookingrobot 13y ago
  You probably should care which server gets the request. It's not explicitly said, but if one server can handle twice as many requests per second, then it might be completing each request faster. If that's the case, it's a better service to give more requests to the faster servers. Worth at least discussing to see if there are other aspects to the problem.

rybosome 13y ago

That's an easy solution in any language, frankly; have a shared queue of the requests, and the servers simply pull from the queue whenever they aren't processing a request. I'm sure that this is easier to implement in Go than a lot of other languages, but I think this actually defeats the purpose of the question. The hard part of the question is how to assign work to the servers rather than letting the servers pick the work themselves.

JulianMorrison 13y ago
Yeah, I just picked Go because it's one I know well and it's a 5 second solution that handles the question as asked. It would be just as easy to do in ruby for example, with EM::Queue. I actually intended this as a way to "assign work" rather than having the servers pull. Each goroutine "owns" a server and forwards all requests to it, but it's just part of the one load balancer process, and the load balancer does nothing but balance. IMO, defeating the purpose of a question is how you solve problems in real life. Now if you wanted a harder question, you could follow that with: OK, that solution will give the servers time to do their thing, but there's no guarantee it won't just end up dumping all the load on a few servers, straining infrastructure and under-using the other machines, because there's no guarantee Go's scheduler is fair. So please develop two competing solutions. First, a fair scheduler that spreads the load evenly. Second, as an alternative, an unfair scheduler that always fills 100% of the time on the first machine before moving on to the second, and so on, and reports how many machines it's using so we can take the others out of the pool and repurpose them.