7 ms·

Is a federated Twitter even possible?

41 points by glhaynes 14y ago

rabidsnail 14y ago
http://en.wikipedia.org/wiki/Lamport_timestamps http://en.wikipedia.org/wiki/Lamport_timestamps Edit: More information on how to actually use Vector Clocks (which are sort of like multi-way Lamport Clocks) in a real system: http://basho.com/blog/technical/2010/04/05/why-vector-clocks-are-hard/ http://basho.com/blog/technical/2010/04/05/why-vector-clocks...
taybin 14y ago
Usenet was federated and seemed to have these properties.
- sp332 14y ago
  This is addressed at the bottom. I don't know if this is true but the problem seems to be, although the posts show up chronologically in each thread, the threads might be out of order with respect to each other.
- kennywinker 14y ago
  Depending on where you were connecting from, there could be serious delays in usenet. Like, some servers synced once a day kind of delays.
  - smacktoward 14y ago
    It's important to note though that hardware muscle and bandwidth were both much, much, much more scarce and expensive back then.
motoford 14y ago
FIDOnet
- michaelpinto 14y ago
  I'm so old that remember when the nickname for that was "Fight-o-net"
Lammy 14y ago
Isn't OStatus exactly this, or does it fail one of his criteria?
sp332 14y ago
If it was impossible for a federated network, it would also be impossible for Twitter. They can either guarantee that messages only show up at the top, or that messages always show up in order (meaning older posts get inserted into the middle of the timeline, as you eventually receive them).
- dwineman 14y ago
  Right, but since Twitter manages all of Twitter's servers (and the dedicated low-latency network via which they're presumably all connected) they can satisfy both of these constraints without sacrificing the third (immediacy). I'm speculating here, but I think that's why it takes a few seconds to post a tweet: it's propagating across the internal federation so that all the nodes have it before it "goes live."
  - sp332 14y ago
    To be specific, your tweet is not timestamped when you send it. It only gets an "official" timestamp when twitter decides to give it one, after receiving it. That means Twitter arbitrarily sets the timestamp whenever they get around to shoving it on top of your feed. So they do have the problem of tweets arriving out of order (due to network latency etc), they just hide it by rewriting timestamps! eta: I admit this is a smaller problem for a centralized service than a federated one, but I would argue that it can work "well enough".
  - fleitz 14y ago
    How is twitter immediate when it's down? Twitter doesn't solve the immediacy problem with any hard guarantees either. Most of the time email is on par with twitter.
    - dwineman 14y ago
      Huh? When Twitter's down, no one can post, so immediacy is meaningless. This is like saying "my car's faster than yours after yours hits a tree."
michaelpinto 14y ago
Is the web federated? Everyone hosts their own sites and there are several browsers -- I don't see why we can't have a social media version of this.
- rabidsnail 14y ago
  Who gets to host #beiberfever? You can build a distributed system that has hashtags (ex: by using a DHT to map tags to lists of nodes that act as clearinghouse for messages with those tags) but that system is not the web.
- lloeki 14y ago
  The web is not "federated": site A does not communicate with site B. Contrast with SMTP or XMPP which require federated servers to communicate with one another to establish dialog between two users. All of them are decentralized though.
  - rhizome 14y ago
    The routers do, though. Through BGP, AS's communicate location information to the routing infrastructure of other AS's. 15 years ago we saw the decline of "everybody knows everything" as the routing tables of core infrastructure simply became too unwieldy.
jimktrains2 14y ago
Isn't that what RSS was? I could make a post, and have it syndicated to whoever wanted to listen to me.
- rabidsnail 14y ago
  RSS doesn't guarantee global ordering, and has very high latency (because of polling). Both of these can be overcome, but require a new protocol.
  - jlogsdon 14y ago
    PubSub solves the problem of immediacy.
    - kelnos 14y ago
      ... and introduces the problems of scalability and reliability. (Not that those problems aren't solvable with PubSub, but it does add a lot of complexity.)
  - jimktrains2 14y ago
    I guess I feel that ordering should be up to the User Agent. This way I can sort things multiple ways depending on how I'm feeling. I also don't see the latency as an issue, but I'm not someone who needs to know exactly what everyone else is doing at all moments of the day.
joshhart 14y ago
It's both possible and necessary. Think about it - even a centralized service like twitter or facebook will have many distributed & disparate services that need to work together to provide a feed. Hence, there probably already is some kind of federation going on, you just don't know it. Source: I work @ LinkedIn on these types of problems.
- sophacles 14y ago
  Also, didn't twitter release as OSS some sort of piping mechanism for exactly this?
- dwineman 14y ago
  Author here: a few people have raised this point. Perhaps I should have made a distinction between "federated within the same data center" and "federated across the internet." They are two entirely different problems.
gojomo 14y ago
I doubt the single global ordering is as important as the author suggests. If nothing is in practice delayed for more than a short period, then either ordering-by-arrival or ordering-by-declared-time-with-'seen'-indicator both mostly work. It's whatever you get used to. And I've seen all sorts of micro-failures in Twitter's provision of global ordering: gaps in my display timeline in one client but not others; tweets seeming to appear below the 'topmost' position when revisiting the stream; difficulty reloading recent history that was already local at one point. A distributed/federated system might be a little fuzzier on some ordering behaviors... but make up for that in other dimensions.
icebraining 14y ago
your node can just wait until it’s received the latest content from every other node before displaying anything. "Every other node" just means the nodes where the people you follow are hosted, not every node in the network. For most people, that would probably be a very small number.
gojomo 14y ago
My hunch is that it's technically possible to go not just federated but radically distributed. However, there's more money to be made in centralization, creating defensible toll booths. And right now the sorts of developers and protocol/system architects who could make a radically distributed alternative are now fully overemployed doing other lucrative or beneficial things. So it's a little harder technically, and lot less lucrative, to make a radically distributed alternative. And whatever the abuses of the centralized proprietors, they're still not changing those tradeoffs -- most users and even platform participants can still make-do under centralization. A big tech bust freeing more talent to work on ideological (rather than pecuniary) projects, or enough heavy-handedness from the centralized proprietors, could change that balance.
- rabidsnail 14y ago
  You're right. Gnutella was developed in 2000, eDonkey in 2000, Freenet in 2000, BitTorrent in 2001.
Tichy 14y ago
I think Twitter also has users distributed on different servers, making it effectively federated.
rabble 14y ago
Back in the day, 2007 and 2008 there was live running federation between Twitter and Jaiku. I remember i was sitting in the room when Ralph and Blaine got it working, at 4am at a foo camp. Unfortunately Jaiku was bought by google and they spent a long time with it offline only to come out as Google Buzz which didn't take off. Many of the early twitter engineers like Blaine Cook and Alex Payne pushed hard for twitter to be more open and federated, but lost that argument and left or were pushed out. It's a business not a technology decision which makes twitter centralized.
pixelcort 14y ago
Most email IMAP servers provide both Date Sent and Date Received properties for each message, allowing the client to sort by either. Even in active mailing list threads, I've found that it's not that common for messages to get too out of order. Assuming federated social services keep track of Date Received, it'd probably be okay to just sort by that.
kniht 14y ago
Yes. http://dsandler.org/brdfdr/ http://dsandler.org/brdfdr/
kscaldef 14y ago
Personally, I'm willing to lose monotonicity. I mean, it's only Twitter. If I don't see every single message because I didn't scroll back far enough, I don't really care.
mparlane 14y ago
I think IRC does this type of mass node interconnection quite well.
forgotusername 14y ago
551 words spilled on a simple question, with a simple, obvious answer: E-mail. * Immediacy: if a post has been made by someone I follow, I can see it in my timeline right away (or close enough that I don’t notice the difference). "E-mail" * Chronology: posts always appear in order by time posted. "E-mail". Chronology as the author imagines it doesn't even occur for Twitter, likely their machines' timestamps are fuzzy +/- perhaps up to a minute or more. * Monotonicity: timelines grow only from the top; older posts are never retroactively inserted. So have your client mark a message by the time it's received, provide a second sort order. Ugh. "E-mail" There are genuine technical challenges to implementing a robust many-many federated messaging system, this post mentions none of them.
- alttab 14y ago
  A billion dollars to the first company that builds a federated twitter on top of existing gmail accounts. Go!
  - moe 14y ago
    For a 1% downpayment I will start tomorrow and deliver this year, email in profile.
    - alttab 14y ago
      Nice try. If you are successful, you won't need me to pay you. The world will.
deleted 14y ago
[deleted]
comex 14y ago
As the post says, with sufficiently slow servers it's impossible to maintain chronology plus monotonicity, and as it says, since chronology is really only important within a conversation, the best solution is to ensure each reply has an in-reply-to field (which tweets already have), then ensure that the original tweet is fetched before displaying the reply, and accept only approximately chronological ordering for "threads". But... that doesn't mean the UI has to change to look threaded, or that you should see an entire conversation if you're following the person who started it. That's a crazy leap. With such an algorithm it can still look exactly like Twitter and most people won't notice the difference. As an alternative, by the way, since these posts are so short, you could simply include the entire thread with each reply! A few kilobytes won't kill any servers. Also, one of the blog comments raises a good point: IRC has the same problem and it works fine.
thinkingisfun 14y ago
"violating monotonicity means you can’t assume you’ve seen everything once you’ve read to the top of your timeline." if that turns out to be such a problem, 1.) you can simply assume that everything fresher than 5 minutes is subject to change, so you ignore it until it's at least 5 minutes old. 2.) whatever site or app you're using could simply mark unread messages, and inform you of out-of-order messages.
moe 14y ago
It hurts a little when the author mentions Usenet - and then doesn't realize that yes, of course it could trivially emulate twitter. Regardless I don't find the notion of a federated twitter particularly interesting anyway. The future is P2P.
testestestes 14y ago
status.net already done. identi.ca etc.

41 points by glhaynes 14y ago

http://en.wikipedia.org/wiki/Lamport_timestamps http://en.wikipedia.org/wiki/Lamport_timestamps Edit: More information on how to actually use Vector Clocks (which are sort of like multi-way Lamport Clocks) in a real system: http://basho.com/blog/technical/2010/04/05/why-vector-clocks-are-hard/ http://basho.com/blog/technical/2010/04/05/why-vector-clocks...

taybin 14y ago

Usenet was federated and seemed to have these properties.

sp332 14y ago
This is addressed at the bottom. I don't know if this is true but the problem seems to be, although the posts show up chronologically in each thread, the threads might be out of order with respect to each other.
kennywinker 14y ago
Depending on where you were connecting from, there could be serious delays in usenet. Like, some servers synced once a day kind of delays.
- smacktoward 14y ago
  It's important to note though that hardware muscle and bandwidth were both much, much, much more scarce and expensive back then.

motoford 14y ago

FIDOnet

michaelpinto 14y ago
I'm so old that remember when the nickname for that was "Fight-o-net"

Lammy 14y ago

Isn't OStatus exactly this, or does it fail one of his criteria?

sp332 14y ago

If it was impossible for a federated network, it would also be impossible for Twitter. They can either guarantee that messages only show up at the top, or that messages always show up in order (meaning older posts get inserted into the middle of the timeline, as you eventually receive them).

dwineman 14y ago
Right, but since Twitter manages all of Twitter's servers (and the dedicated low-latency network via which they're presumably all connected) they can satisfy both of these constraints without sacrificing the third (immediacy). I'm speculating here, but I think that's why it takes a few seconds to post a tweet: it's propagating across the internal federation so that all the nodes have it before it "goes live."
- sp332 14y ago
  To be specific, your tweet is not timestamped when you send it. It only gets an "official" timestamp when twitter decides to give it one, after receiving it. That means Twitter arbitrarily sets the timestamp whenever they get around to shoving it on top of your feed. So they do have the problem of tweets arriving out of order (due to network latency etc), they just hide it by rewriting timestamps! eta: I admit this is a smaller problem for a centralized service than a federated one, but I would argue that it can work "well enough".
- fleitz 14y ago
  How is twitter immediate when it's down? Twitter doesn't solve the immediacy problem with any hard guarantees either. Most of the time email is on par with twitter.
  - dwineman 14y ago
    Huh? When Twitter's down, no one can post, so immediacy is meaningless. This is like saying "my car's faster than yours after yours hits a tree."

michaelpinto 14y ago

Is the web federated? Everyone hosts their own sites and there are several browsers -- I don't see why we can't have a social media version of this.

rabidsnail 14y ago
Who gets to host #beiberfever? You can build a distributed system that has hashtags (ex: by using a DHT to map tags to lists of nodes that act as clearinghouse for messages with those tags) but that system is not the web.
lloeki 14y ago
The web is not "federated": site A does not communicate with site B. Contrast with SMTP or XMPP which require federated servers to communicate with one another to establish dialog between two users. All of them are decentralized though.
- rhizome 14y ago
  The routers do, though. Through BGP, AS's communicate location information to the routing infrastructure of other AS's. 15 years ago we saw the decline of "everybody knows everything" as the routing tables of core infrastructure simply became too unwieldy.

jimktrains2 14y ago

Isn't that what RSS was? I could make a post, and have it syndicated to whoever wanted to listen to me.

rabidsnail 14y ago
RSS doesn't guarantee global ordering, and has very high latency (because of polling). Both of these can be overcome, but require a new protocol.
- jlogsdon 14y ago
  PubSub solves the problem of immediacy.
  - kelnos 14y ago
    ... and introduces the problems of scalability and reliability. (Not that those problems aren't solvable with PubSub, but it does add a lot of complexity.)
- jimktrains2 14y ago
  I guess I feel that ordering should be up to the User Agent. This way I can sort things multiple ways depending on how I'm feeling. I also don't see the latency as an issue, but I'm not someone who needs to know exactly what everyone else is doing at all moments of the day.

joshhart 14y ago

It's both possible and necessary. Think about it - even a centralized service like twitter or facebook will have many distributed & disparate services that need to work together to provide a feed. Hence, there probably already is some kind of federation going on, you just don't know it. Source: I work @ LinkedIn on these types of problems.

sophacles 14y ago
Also, didn't twitter release as OSS some sort of piping mechanism for exactly this?
dwineman 14y ago
Author here: a few people have raised this point. Perhaps I should have made a distinction between "federated within the same data center" and "federated across the internet." They are two entirely different problems.

gojomo 14y ago

I doubt the single global ordering is as important as the author suggests. If nothing is in practice delayed for more than a short period, then either ordering-by-arrival or ordering-by-declared-time-with-'seen'-indicator both mostly work. It's whatever you get used to. And I've seen all sorts of micro-failures in Twitter's provision of global ordering: gaps in my display timeline in one client but not others; tweets seeming to appear below the 'topmost' position when revisiting the stream; difficulty reloading recent history that was already local at one point. A distributed/federated system might be a little fuzzier on some ordering behaviors... but make up for that in other dimensions.

icebraining 14y ago

your node can just wait until it’s received the latest content from every other node before displaying anything. "Every other node" just means the nodes where the people you follow are hosted, not every node in the network. For most people, that would probably be a very small number.

gojomo 14y ago

My hunch is that it's technically possible to go not just federated but radically distributed. However, there's more money to be made in centralization, creating defensible toll booths. And right now the sorts of developers and protocol/system architects who could make a radically distributed alternative are now fully overemployed doing other lucrative or beneficial things. So it's a little harder technically, and lot less lucrative, to make a radically distributed alternative. And whatever the abuses of the centralized proprietors, they're still not changing those tradeoffs -- most users and even platform participants can still make-do under centralization. A big tech bust freeing more talent to work on ideological (rather than pecuniary) projects, or enough heavy-handedness from the centralized proprietors, could change that balance.

rabidsnail 14y ago
You're right. Gnutella was developed in 2000, eDonkey in 2000, Freenet in 2000, BitTorrent in 2001.

Tichy 14y ago

I think Twitter also has users distributed on different servers, making it effectively federated.

rabble 14y ago

Back in the day, 2007 and 2008 there was live running federation between Twitter and Jaiku. I remember i was sitting in the room when Ralph and Blaine got it working, at 4am at a foo camp. Unfortunately Jaiku was bought by google and they spent a long time with it offline only to come out as Google Buzz which didn't take off. Many of the early twitter engineers like Blaine Cook and Alex Payne pushed hard for twitter to be more open and federated, but lost that argument and left or were pushed out. It's a business not a technology decision which makes twitter centralized.

pixelcort 14y ago

Most email IMAP servers provide both Date Sent and Date Received properties for each message, allowing the client to sort by either. Even in active mailing list threads, I've found that it's not that common for messages to get too out of order. Assuming federated social services keep track of Date Received, it'd probably be okay to just sort by that.

kniht 14y ago

Yes. http://dsandler.org/brdfdr/ http://dsandler.org/brdfdr/

kscaldef 14y ago

Personally, I'm willing to lose monotonicity. I mean, it's only Twitter. If I don't see every single message because I didn't scroll back far enough, I don't really care.

mparlane 14y ago

I think IRC does this type of mass node interconnection quite well.

forgotusername 14y ago

551 words spilled on a simple question, with a simple, obvious answer: E-mail. * Immediacy: if a post has been made by someone I follow, I can see it in my timeline right away (or close enough that I don’t notice the difference). "E-mail" * Chronology: posts always appear in order by time posted. "E-mail". Chronology as the author imagines it doesn't even occur for Twitter, likely their machines' timestamps are fuzzy +/- perhaps up to a minute or more. * Monotonicity: timelines grow only from the top; older posts are never retroactively inserted. So have your client mark a message by the time it's received, provide a second sort order. Ugh. "E-mail" There are genuine technical challenges to implementing a robust many-many federated messaging system, this post mentions none of them.

alttab 14y ago
A billion dollars to the first company that builds a federated twitter on top of existing gmail accounts. Go!
- moe 14y ago
  For a 1% downpayment I will start tomorrow and deliver this year, email in profile.
  - alttab 14y ago
    Nice try. If you are successful, you won't need me to pay you. The world will.

deleted 14y ago

[deleted]

comex 14y ago

As the post says, with sufficiently slow servers it's impossible to maintain chronology plus monotonicity, and as it says, since chronology is really only important within a conversation, the best solution is to ensure each reply has an in-reply-to field (which tweets already have), then ensure that the original tweet is fetched before displaying the reply, and accept only approximately chronological ordering for "threads". But... that doesn't mean the UI has to change to look threaded, or that you should see an entire conversation if you're following the person who started it. That's a crazy leap. With such an algorithm it can still look exactly like Twitter and most people won't notice the difference. As an alternative, by the way, since these posts are so short, you could simply include the entire thread with each reply! A few kilobytes won't kill any servers. Also, one of the blog comments raises a good point: IRC has the same problem and it works fine.

thinkingisfun 14y ago

"violating monotonicity means you can’t assume you’ve seen everything once you’ve read to the top of your timeline." if that turns out to be such a problem, 1.) you can simply assume that everything fresher than 5 minutes is subject to change, so you ignore it until it's at least 5 minutes old. 2.) whatever site or app you're using could simply mark unread messages, and inform you of out-of-order messages.

moe 14y ago

It hurts a little when the author mentions Usenet - and then doesn't realize that yes, of course it could trivially emulate twitter. Regardless I don't find the notion of a federated twitter particularly interesting anyway. The future is P2P.

testestestes 14y ago

status.net already done. identi.ca etc.