findAccessKey cache

[ghost]

On every new connection findAccessKey tests every single user's key against the incoming data.

This isn't that much of an issue for TCP where the 'findAccessKey' time is much smaller that the overall TX time of the data.

But for UDP this is going to be a mess. UDP packets are small and frequent. Any application that sends large amounts of UDP is likely to waste many many cycles of CPU time.

Why not add a cache?

Because of NAT we need to have an array per ip and store all users who connect from that ip. We can go a step further and search users already bound to an ip last.

unbound_Users = { user1, user2, user3, user4 }
cache_ip_userlist = {}
cache_user_to_ip = {}

// user1 connection from ip1
findAccessKey [test keys for user in] cache_ip_userlist[ip1] - Nothing found
findAccessKey [test keys for user in] unbound_Users - found user1
unbound_Users.remove(user1)
cache_ip_userlist[ip1][user1] = expire_time;
cache_user_to_ip[user1] = ip1;

// user2 connection from ip1
findAccessKey [test keys for user in] cache_ip_userlist[ip1] - Nothing found
findAccessKey [test keys for user in] unbound_Users - found user2
unbound_Users.remove(user2)
cache_ip_userlist[ip1][user2] = expire_time;
cache_user_to_ip[user2] = ip1;

// user1 connection from ip1 (again)
findAccessKey [test keys for user in] cache_ip_userlist[ip1] - found user1
cache_ip_userlist[ip1][user1] = expire_time; // Refresh expire time

// user1 connects from ip2 (user1 was connecting from ip1, but changed to ip2)
findAccessKey [test keys for user in] cache_ip_userlist[ip2] - Nothing found
findAccessKey [test keys for user in] unbound_Users - Nothing found
findAccessKey [test keys for user in] all cache_ip_userlist's - found user1 in cache_ip_userlist[ip]
cache_ip_userlist[ cache_user_to_ip[user1] ].remove(user1) // Move user1 from cache_ip_userlist[ip1] -> cache_ip_userlist[ip2]
cache_ip_userlist[ip2][user1] = expire_time;
cache_user_to_ip[user1] = ip2;

cache_ip_userlist should also store an expire time, which should get updated on any match, and expired entries can be purged every time it's searched, and cache_user_to_ip along with it.

A long expire time will mean less key search time when clients don't send data often, while a short expire time will mean connections from new clients won't waste time searching disconnected clients.

In any case since it's per ip, worst case scenario is having to search all user's keys for every connection WHEN all users happen to connect from exactly the same IP.

[trevj]

@hay187 Thanks for the thoughtful report. I think @fortuna can best explain our current strategy.

[ghost]

Great, I'd love to hear your ideas about this. I read the proposals originally and all the talk about NAT| being an issue with cache etc, but that's easy to handle.

I looked closer at the code now, and in fact the udp association can cache the current user key for the src:port/dst:port connection, and if it fails then search all users again.

I've never programmed go (although it looks easy enough). Is it comparable in performance to C/C++ for sockets? how about libev?

My use case will have a lot of users (1000+ per server) so i'm looking for the best performance possible. AES encryption is very fast so i'm actually surprised 100-1000 iterations for ever single packet would even add that much latency. If the UDP situation can be handled it may be better to forgo the cache completely.

Interested in your thoughts.

EDIT: Also, have you looked at https://github.com/tidwall/evio at all?

[fortuna]

@hay187 Are you actually seeing latency issues with the existing code?

Please check the shadowsocks_time_to_cipher_ms metric. What numbers are you seeing?

To be clear, on every connection we put the successful cipher in the front of the list, so the time to find the cipher is O(active keys) rather than O(created keys). (see #12)

A cache has its own issues. It makes the code more complex and we need to deal with expiration and lock contention. That's significant work to get right and would like to avoid if it's not justified.

[fortuna]

@hay187 outline-ss-server actually performs better than shadowsocks-libev in my measurements. Please take a look at https://github.com/Jigsaw-Code/outline-ss-server#performance-testing on how you can run your own comparison tests.

[ghost]

I haven’t actually run any tests or run it under load, I was just looking at it in theory.

The active keys makes sense, but couldn’t you also Cache them by source ip too? That way you could check the users in the source ip list first. You could not bother with expiry at all. Just keep a record of the last ip array the user was in and remove it when they get inserted into a new ip cache array.

Originally I was thinking expiry because when users become inactive you’ll still end up searching them for that ip when a new user connects from it. But pushing the user to the top should reduce that to O(active keys from that ip) at worst if the ip is the same, and O(active keys) if it isn’t.

Locking may still be an issue - I don’t really know ‘go’ but program many other languages so am fairly experienced generally. I don’t really understand how go works in terms of concurrency etc.

EDIT: finally looked at the UDP code, of course we need to save the key for the 'connection' because we need to be able to encrypt when sending back to the client.
All things considered, you're probably right then to not bother with the cache for tcp either.

[fortuna]

@hay187 Thanks for the improvement suggestions. We'll consider it when the added latency actually becomes an issue.

[bemasc]

FYI, this optimization was added in #25. The topic is being discussed further at shadowsocks/shadowsocks-org#130.

[fortuna]

@bemasc, not quite the same optimization as requested in this issue. @hay187 effectively suggested having a ip -> cipher map, while you created a cipher -> ip map. I actually like your cipher -> ip solution better because it's simple: it doesn't introduce contention and the need to expire things.

In any case, the implemented solution is probably as effective if not more effective.