Order of request headers should be preserved when sent to origin server

#### Summary

If I made a request with code that looks like:

```
    requests.get(
        'http://127.0.0.1:8765/',
        headers=OrderedDict([
            ('X-Header-1', 'ignoreme'),
            ('X-Header-2', 'ignoreme'),
            ('X-Header-3', 'ignoreme'),
            ('X-Header-4', 'ignoreme'),
        ])
    )
```

I expect the recipient HTTP server to receive the X headers in the same order at they were listed in the code above. However I receive them in a random non-deterministic order.
#### Environment
- Requests 2.9.1
- Python 3.4.1
#### Repro Steps
- Download files in the following gist: https://gist.github.com/davidfstr/0dca5a133fa397cadd92
- Run reflect_server.py in terminal window 1.
- Run reflect_client.py in terminal window 2.
#### Expected Results
- Terminal window 1 shows a request made with the X headers in consecutive order from 1 to 4.
#### Actual Results
- Terminal window 1 shows a request made with the X headers in random non-deterministic order.
#### Notes

The following closed older issues suggest that preservation of order is indeed important:
- https://github.com/kennethreitz/requests/issues/284, https://github.com/kennethreitz/requests/issues/179
- https://github.com/kennethreitz/requests/issues/2668


FWIW, I don't think any of those issues actually indicate that preservation of order on the wire is important. It _is_, but not for any of those reasons. The reason it's important is that headers can in principle be split up into multiple instances if the header is a comma-separated list, and maintaining the order of those parts is important (or the header ends up taking on a different meaning).

The fundamental reason this doesn't work is because we store the headers in our `CaseInsensitiveDict`, which does not preserve order. At this point we may want to look harder at replacing our own implementation with the one from urllib3, which _does_ preserve order.

Thoughts @kennethreitz, @sigmavirus24?


You should be able to provide your headers as a list of tuples, and the order will be preserved. We do not support OrderedDict this way (though I wouldn't be against fixing this). 


@kennethreitz Nope, that got broken a _long_ time ago for headers. Back in 2012 it looks like.


Well, it's supposed to work :)


That code got pretty complicated. 


@kennethreitz We never had a test that enforces that invariant, which means that commit 366e8e849877aea44ce96abebd4f26f5bcce12fb didn't spot that we broke it in the rewrite for v2.0.


(Might be worth reading my summary above to understand _why_ it doesn't work.)


Yeah, it was always a "secret" feature, so I prob chose to abandon it during the refactor. 


I think this would be a nice feature to restore, but not worth complicating the codebase over. 


@kennethreitz We could always replace the `CaseInsensitiveDict` used in this place with the [`HTTPHeaderMap`](https://github.com/Lukasa/hyper/blob/development/hyper/common/headers.py) from hyper.


It would still require case-insensitivy, and have a `repr()` identical to a standard dict. 

I don't think swapping out core collections this far along in the project is a good idea, so we should lean towards "no" as this is lightly discussed. 


Fair enough. =)


Thank you for your consideration. It sounds like I should take a look at using the underlying urllib3 instead then.

In case you're curious, I'm writing a lightweight web service that forwards arbitrary HTTP requests to an origin HTTP server and caches+persists the responses. Effectively a caching HTTP proxy. Since the origin HTTP server could depend on all kinds of interesting properties of the original request, the proxy makes special efforts to change the original request and response as little as possible.


In case other readers are curious, it appears that urllib3 does in fact preserve the order of request headers.

Unfortunately it does not preserve the order of _response_ headers. https://github.com/shazow/urllib3/issues/821 😕


I have been monkey-patching requests to achieve ordering of request headers for over a year. For all my usecases it is enough just to change underlying `_store` of `CaseInsensitiveDict` from `dict` to `collections.OrderedDict`.

``` patch
class CaseInsensitiveDict(collections.MutableMapping):
    def __init__(self, data=None, **kwargs):
-        self._store = dict()
+        self._store = collections.OrderedDict()
```

Then I pass headers to request method as `OrderedDict`, just like OP in the example above. I would be nice if this become merged upstream. I don't see any problems or incompatibilities such a change can bring in.


@Lukasa if @piotrjurkiewicz's patch has no unintended side-effects, I'm +1 for incorporating this. 


I'm fine with it as well, would you like to raise a PR @piotrjurkiewicz?


For anyone interested, Akamai seems to block requests with the wrong order:
```
$ curl -v -H "$UA" -H "$ACCEPT" -H "$ENCODING" $URL |& grep '< HTTP'
< HTTP/1.1 403 Forbidden
$ curl -v -H "$ACCEPT" -H "$UA" -H "$ENCODING" $URL |& grep '< HTTP'
< HTTP/1.1 301 Moved Permanently
```

The problem seems to be still there I tried this code:
```
headers = collections.OrderedDict([('Host', "site.com"),
                  ('User-Agent', 'Mozilla/5.0 (Macintosh; Intel Mac OS X 10.11; rv:64.0) Gecko/20100101 Firefox/64.0'),
                  ('Accept', 'text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8'),
                  ('Accept-Language', 'it-IT,it;q=0.8,en-US;q=0.5,en;q=0.3'),
                  ('Accept-Encoding', 'gzip, deflate'),
                  ('DNT', '1'),
                  ('Connection', 'close'),
                  ('Upgrade-Insecure-Requests','1')])

r = requests.get("http://site.com", headers=headers, proxies=proxy)
```
And the request intercepted with Burp is:
```
GET / HTTP/1.1
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.11; rv:64.0) Gecko/20100101 Firefox/64.0
Accept-Encoding: gzip, deflate
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8
Connection: close
Host: site.com
Accept-Language: it-IT,it;q=0.8,en-US;q=0.5,en;q=0.3
DNT: 1
Upgrade-Insecure-Requests: 1
```
The order is not maintained. I am using python 3.7 and requests 2.21.0

I would be interested to know why the order is subtly changed as @AlessioCantina described above -- is it being automatically sorted into the correct order according to the user-agent?